Markov Chains

Memoryless transitions: where you go next depends only on where you are.

A Markov chain is a sequence of states $X_0, X_1, X_2, \dots$ with the memoryless property:

P(X_{n+1} = j \mid X_n = i, X_{n-1}, \dots, X_0) = P(X_{n+1} = j \mid X_n = i) = p_{ij}

All the future-relevant information sits in the current state. The transition matrix $P = (p_{ij})$ encodes the dynamics.

Two key facts:

After $n$ steps, the state distribution is $\pi_0 P^n$ , where $\pi_0$ is the initial distribution treated as a row vector.An irreducible aperiodic chain on a finite state space has a unique stationary distribution that's the long-run limit of $\pi_0 P^n$ .

In finance, Markov chains model credit rating migration (today's rating depends only on yesterday's), hidden regime models for volatility, and the random-walk hypothesis for prices. PageRank, the original engine behind Google search, is also a stationary distribution of a Markov chain — applied to the web's hyperlink graph.