Key Concepts of Markov Chains

Why This Matters

Markov chains are the backbone of stochastic modeling in engineering—they show up everywhere from reliability analysis and queueing systems to machine learning algorithms and communication networks. When you're being tested on Markov chains, you're really being tested on your ability to model systems where the future depends only on the present, not the entire history. This memoryless property is what makes these models both mathematically tractable and practically powerful.

The concepts here connect to broader themes you'll encounter throughout probability: long-term behavior of random processes, convergence properties, and computational methods for complex distributions. Don't just memorize definitions—understand what each concept tells you about how a system evolves over time and when different analytical tools apply. If you can explain why a chain converges to a unique stationary distribution (or why it doesn't), you've mastered the core ideas.

---

Foundational Structure

Every Markov chain is built on the same basic architecture: a set of possible states and rules governing how the system moves between them. The Markov property—that the future depends only on the present—is what distinguishes these processes from more complex stochastic systems.

Definition of Markov Chains

• Markov property (memorylessness)—the probability of transitioning to any future state depends only on the current state, not on how you got there
• State space can be finite or countably infinite, with transitions occurring in either discrete time (fixed steps) or continuous time (any moment)
• Stochastic process framework means we're tracking random evolution over time—essential for modeling uncertainty in engineering systems

State Space and Transition Probabilities

• State space $S$ defines all possible configurations the system can occupy—must be clearly specified before any analysis
• Transition probability $P_{ij}$ gives the likelihood of moving from state $i$ to state $j$ in one time step
• Row sums equal 1—from any state, the system must go somewhere (including possibly staying put), so $\sum_j P_{ij} = 1$

Transition Matrix

• Square matrix $P$ organizes all transition probabilities with rows representing current states and columns representing next states
• Matrix powers $P^n$ give $n$-step transition probabilities—this is why linear algebra is central to Markov chain analysis
• Stochastic matrix properties (non-negative entries, rows summing to 1) ensure valid probability distributions at each step

---

Multi-Step Behavior

Understanding how a Markov chain behaves over multiple time steps requires connecting single-step transitions to longer-term evolution. The Chapman-Kolmogorov equations formalize this connection through matrix multiplication.

Chapman-Kolmogorov Equations

• $P_{ij}^{(m+n)} = \sum_k P_{ik}^{(m)} P_{kj}^{(n)}$—the probability of going from $i$ to $j$ in $m+n$ steps equals the sum over all intermediate states $k$
• Matrix form: $P^{(m+n)} = P^{(m)} P^{(n)}$—this is just matrix multiplication, making computation straightforward
• Foundational for long-term analysis—these equations let you compute $n$-step probabilities and analyze convergence behavior

---

State Classification

Not all states in a Markov chain behave the same way over time. Classifying states reveals which parts of the system are visited repeatedly, which are eventually abandoned, and which trap the process forever.

Classification of States (Recurrent, Transient, Absorbing)

• Recurrent states are revisited infinitely often with probability 1—once you enter, you're guaranteed to return
• Transient states have positive probability of never returning—the system eventually leaves them permanently
• Absorbing states satisfy $P_{ii} = 1$—once entered, the process stays there forever (critical for reliability and game-ending scenarios)

Irreducibility and Periodicity

• Irreducible chain means every state can be reached from every other state—the chain forms a single communicating class
• Period $d$ of a state is the GCD of all return times; aperiodic means $d = 1$, allowing returns at any sufficiently large time
• Both properties affect convergence—irreducibility ensures a unique stationary distribution exists; aperiodicity ensures the chain actually converges to it

---

Long-Term Behavior

The most powerful applications of Markov chains involve predicting where the system spends its time in the long run. Stationary and limiting distributions capture this asymptotic behavior, while the ergodic theorem connects time averages to probability averages.

Stationary Distribution

• Vector $\pi$ satisfying $\pi P = \pi$—the distribution that remains unchanged after applying the transition matrix
• Interpretation: $\pi_j$ represents the long-run proportion of time spent in state $j$ (for ergodic chains)
• Existence guaranteed for finite irreducible chains; uniqueness requires irreducibility; convergence requires aperiodicity

Limiting Distribution

• $\lim_{n \to \infty} P_{ij}^{(n)}$ describes state probabilities as time approaches infinity
• Equals stationary distribution for irreducible, aperiodic chains—this is the key convergence result
• May not exist for periodic chains (probabilities oscillate) or may depend on initial state for reducible chains

Ergodic Theorem

• Time average equals space average—for irreducible, aperiodic chains, the fraction of time in state $j$ converges to $\pi_j$
• Ergodic = irreducible + aperiodic + positive recurrent—these three conditions guarantee the strongest convergence properties
• Practical importance: allows estimation of stationary probabilities from a single long simulation run

---

Time Frameworks

Markov chains come in two flavors depending on how time is modeled. The choice between discrete and continuous time affects both the mathematical formulation and the analytical techniques required.

Discrete-Time vs. Continuous-Time Markov Chains

• Discrete-time uses transition probability matrix $P$ with updates at fixed intervals $n = 0, 1, 2, \ldots$
• Continuous-time uses transition rate matrix $Q$ where $q_{ij}$ gives the rate of jumping from $i$ to $j$; time between jumps is exponentially distributed
• Analysis differs: discrete uses matrix powers; continuous uses matrix exponentials $P(t) = e^{Qt}$ and differential equations $\frac{dP}{dt} = QP$

---

Applications and Computational Methods

Markov chains aren't just theoretical—they're workhorses for modeling real systems and solving computational problems. MCMC methods leverage Markov chain convergence to sample from distributions that would otherwise be intractable.

Applications of Markov Chains

• Queueing theory models customer arrivals and service; reliability engineering tracks system degradation and failure
• PageRank algorithm treats web surfing as a random walk—Google's original breakthrough was a Markov chain application
• Hidden Markov Models (HMMs) in speech recognition and bioinformatics extend the framework to partially observed systems

Markov Chain Monte Carlo (MCMC) Methods

• Construct a chain with desired stationary distribution—then samples from the chain approximate samples from the target distribution
• Metropolis-Hastings algorithm accepts/rejects proposed moves to achieve any target distribution; Gibbs sampling updates one variable at a time
• Convergence diagnostics are critical—you need the chain to reach stationarity before samples are valid (burn-in period)

---

Quick Reference Table

---

Self-Check Questions

1. What three conditions must a Markov chain satisfy for the limiting distribution to equal the stationary distribution? Why does each condition matter?

2. Compare recurrent and transient states: how would you determine which classification applies to a given state, and what does each tell you about long-term system behavior?

3. If you're given a transition matrix and asked to find the stationary distribution, what equation do you solve? What additional condition ensures a unique solution?

4. How do discrete-time and continuous-time Markov chains differ in their mathematical formulation? When would you choose one framework over the other for an engineering application?

5. Explain how MCMC methods exploit Markov chain convergence properties. If an FRQ asks you to design a sampler for a complex distribution, what key property must your constructed chain have?