Markov chains §

Why the property is powerful. Without the Markov property, the probability of a path of length $n$ would require conditioning on the entire history $(x_0, \dots, x_{n-1})$ — an object that grows with $n$ . The Markov property says that conditioning on the history is redundant: the last state $x_{n-1}$ already carries all the information the future needs. That is what makes chains computable and simulable.

Concrete example: a weather chain. Let $S = \{\text{Sunny}, \text{Rainy}\}$ . Suppose

• if today is Sunny, tomorrow is Sunny with probability $0.8$ and Rainy with $0.2$ ;
• if today is Rainy, tomorrow is Sunny with probability $0.5$ and Rainy with $0.5$ .

The Markov assumption is that “tomorrow’s weather depends on today’s weather, not on the whole week so far.” The probability of the specific 3-day path Sunny → Sunny → Rainy is

one initial probability times two one-step factors — no need to remember the day before.

The simulation above runs a 4-state chain. Each Step applies one transition; the bar chart tracks how often each state has been visited, and you can watch those empirical frequencies settle onto the theoretical stationary distribution $\pi$ (Section 3).

Authoritative sources.

Authoritative sources

• A. A. Markov, On the theory of probabilities (1906)
• J. G. Kemeny & J. L. Snell, Finite Markov Chains (1960)

Example problem.

Reading the matrix. $P_{ij}$ is the probability of leaving $i$ and arriving at $j$ in one step. Because from state $i$ you must go somewhere, $\sum_j P_{ij} = 1$ . A diagonal entry $P_{ii}$ is the probability of staying put.

Why $P^n$ works. The $(i, j)$ entry of $P^2$ is $\sum_k P_{ik} P_{kj}$ : go from $i$ to some intermediate $k$ , then from $k$ to $j$ . This is exactly the Chapman–Kolmogorov equation with $m = n = 1$ , and it is just the chain rule of conditional probability plus the law of total probability. Matrix multiplication is doing the “sum over the forgotten intermediate state” for you.

Concrete example. Take the weather chain of Section 1, with $S = \{\text{Sunny}, \text{Rainy}\}$ and

The probability of being Rainy two days from now, given it is Sunny today, is $(P^2)_{12}$ :

The intermediate day is Sunny with probability $0.8$ (contributing $0.8 \cdot 0.2$ ) or Rainy with probability $0.2$ (contributing $0.2 \cdot 0.5$ ).

Authoritative sources.

Authoritative sources

• Chapman–Kolmogorov equations
• J. G. Kemeny & J. L. Snell, Finite Markov Chains (1960)

Example problem.

What “stationary” means. If the chain starts in $\pi$ — that is, $\mathbb{P}(X_0 = i) = \pi_i$ — then it stays in $\pi$ forever: $\mathbb{P}(X_{t+1} = j) = \sum_i \pi_i P_{ij} = (\pi P)_j = \pi_j$ . The distribution is a fixed point of the update rule.

Existence and uniqueness. For a finite chain, irreducibility (every state reachable from every other) guarantees that a stationary distribution exists and is unique. Aperiodicity (no deterministic “clock” forcing returns to a fixed rhythm) guarantees that the chain actually converges to it rather than oscillating. The rate of convergence is governed by the second-largest eigenvalue of $P$ in magnitude — the Perron–Frobenius theory.

Concrete example. For the weather chain, solve $\pi P = \pi$ with $\pi_1 + \pi_2 = 1$ :

From the first equation, $0.2\,\pi_1 = 0.5\,\pi_2$ , so $\pi_1 = 2.5\,\pi_2$ . With $\pi_1 + \pi_2 = 1$ this gives $\pi_2 = 1/3.5 \approx 0.286$ and $\pi_1 \approx 0.714$ . So in the long run it is Sunny about $71\%$ of the time. You can verify in the simulation that the empirical bars settle near the theoretical $\pi$ .

Authoritative sources.

Authoritative sources

• Stationary distribution
• Perron–Frobenius theorem

Example problem.

Recurrent vs transient, intuitively. A recurrent state is one you are doomed to revisit; a transient state is one you may visit a few times and then abandon forever. In a finite chain, irreducibility forces every state to be recurrent (you cannot “escape to infinity” when there are only finitely many states). Transience only appears in infinite chains, e.g. the simple random walk on $\mathbb{Z}^3$ is transient.

The return-probability criterion. The cleanest test is $f_i$ : compute the probability of ever returning to $i$ after leaving it. If it is $1$ , the state is recurrent; otherwise transient. Equivalently, a state is recurrent iff the expected number of visits to it (starting from itself) is infinite.

Periodicity, intuitively. A state with period $d > 1$ can only be revisited at times that are multiples of $d$ — the chain is trapped on a $d$ -cycle. Example: a chain that alternates deterministically between two states has period $2$ . Aperiodicity ($d = 1$ ) is what lets the chain “forget its phase” and converge to a single stationary distribution; a periodic chain instead oscillates. A single self-loop ($P_{ii} > 0$ ) is the easiest way to guarantee aperiodicity.

Concrete example. Consider a 3-state chain where $1 \to 2$ and $2 \to 1$ happen with probability $1$ , and state $3$ is reachable from $1$ but never returns. Then $3$ is transient (once you leave $3$ you never come back, and you can even fail to reach it), while $\{1, 2\}$ form a closed, period-$2$ class.

Authoritative sources.

Authoritative sources

• Recurrent and transient states
• J. G. Kemeny & J. L. Snell, Finite Markov Chains (1960)

Example problem.

Why the linear system. If $i \in A$ you have already arrived, so $h_i = 0$ . If $i \notin A$ , you spend one step (the leading $1$ ) and then, having moved to $j$ with probability $P_{ij}$ , still need $h_j$ more steps on average. Taking expectation over the next state gives $h_i = 1 + \sum_j P_{ij} h_j$ . This is a system of linear equations in the unknowns $h_i$ for $i \notin A$ , and it has a unique solution whenever $A$ is reachable from every state.

Gambler’s ruin — the canonical example. A gambler with $i$ dollars bets $1$ dollar at a time, winning with probability $p$ and losing with probability $q = 1 - p$ , until reaching $0$ (broke) or $N$ (goal). The states are $\{0, 1, \dots, N\}$ with $P_{i,i+1} = p$ , $P_{i,i-1} = q$ . The expected duration $h_i$ solves $h_i = 1 + p\,h_{i+1} + q\,h_{i-1}$ with $h_0 = h_N = 0$ . For the fair game $p = q = 1/2$ the solution is the parabola $h_i = i(N - i)$ .

Connection to martingales. The fair gambler’s fortune is a martingale; the optional stopping theorem gives the probability of reaching $N$ before $0$ in one line, while the hitting-time duration above comes from the squared fortune, which is a submartingale.

Authoritative sources.

Authoritative sources

• Gambler’s ruin
• J. G. Kemeny & J. L. Snell, Finite Markov Chains (1960)

Example problem.

• PageRank. The web is a directed graph; a “random surfer” who follows links at random is a Markov chain on pages. PageRank is its stationary distribution $\pi$ (with a damping factor to keep the chain irreducible and aperiodic). The most important pages are the ones the surfer occupies most often in the long run.
• MCMC (Metropolis–Hastings). To sample from a hard-to-normalize target distribution, one builds a Markov chain whose stationary distribution is exactly the target, runs it, and reads off samples. Ergodicity (Section 3) guarantees the samples converge to the target.
• Ehrenfest urn. Two urns exchange one of $N$ particles at random each step — the 1911 model of gas diffusion. It is a birth–death chain whose stationary distribution is binomial, and it is the discrete precursor of Brownian motion.
• Queues. The number of customers in a queue evolves as a Markov chain (a birth–death process); its stationary distribution gives the long-run occupancy and waiting times.

Authoritative sources.

Authoritative sources

• PageRank
• Markov chain Monte Carlo
• Ehrenfest urn model

A 3-state chain has transition matrix

(a) Find the stationary distribution $\pi$ . (b) Starting from state $1$ , find the expected hitting time of state $3$ .