Markov chains

Summary

A Markov state retains the information needed to specify the next-state law without consulting older history. For finite states with row-stochastic transition matrix $P$, row-vector marginals evolve as ${\mu }_{t+1}={\mu }_{t}P$.

Use $P_{ij}=P(X_{t+1}=j\mid X_t=i)$: each row is nonnegative and sums to one. For the illustrated teaching chain,

Right multiplication gives ${\mu }_1=(0.8,0.2)$, ${\mu }_2=(0.72,0.28)$, and ${\mu }_3=(0.688,0.312)$. Every update preserves total mass, but these finite-time distributions still depend on the initial state.

Stationary distribution

A stationary distribution satisfies $\pi P=\pi$, a fixed-point condition rather than a promise of convergence. Every finite row-stochastic matrix has at least one stationary distribution. Finite irreducibility makes it unique; adding aperiodicity ensures convergence from every initial distribution:

For the fixture, $0.2{\pi }_A=0.4{\pi }_B$ and ${\pi }_A+{\pi }_B=1$ give $\pi =(2/3,1/3)$. Writing $a_t={\mu }_t(A)$ yields $a_{t+1}=0.4+0.4a_t$. Thus $a_t-2/3=(1/3)(0.4{)}^t$ for this start, explicitly showing contraction. Nontrivial eigenvalue magnitudes govern asymptotic contraction for finite irreducible reversible chains. Bounds also depend on the starting distribution; a positive absolute spectral gap excludes periodic oscillation.

Detailed balance and reversibility

A chain is reversible if there is a $\pi$ such that

Summing the balance equality over $i$ gives ${\sum }_i{\pi }_i{P}_{ij}={\pi }_j{\sum }_i{P}_{ji}={\pi }_j$. Detailed balance therefore implies stationarity, but stationarity does not imply detailed balance. The fixture’s two cross-flows both equal $(2/3)(1/5)=2/15$. Metropolis-Hastings can construct a target-invariant reversible chain; valid convergence still requires additional conditions.

Change the Requirement

Remove Holding Probabilities

New task: Replace the fixture matrix with $\left[\begin{array}{cc}0& 1\\ 1& 0\end{array}\right]$.

Picture and change: Mass alternates between states instead of contracting.

Check: $(1/2,1/2)$ is the unique stationary distribution, but starting at A gives alternating point masses forever.

Use when: Transition structure can create periodicity; uniqueness alone is insufficient for marginal convergence.

Higher-order chains

New task: Let the next-state probability depend on the previous state as well as the current state.

Picture and change: Use ordered pairs as states, preserving the history that changes transition probabilities.

Check: From (A,B), move to (B,A) with probability $0.9$ and (B,B) with $0.1$. From (B,B), let those probabilities be $0.1$ and $0.9$ instead; a current-token-only B cannot represent both rows.

Use when: A specified older observation still changes the next-state law. A $k$-order token chain becomes first-order over $k$-tuples, potentially increasing the state space substantially.