Basics
| Item | Description |
|---|
Markov Property: P(X_t+1 | X_t, X_t-1, ...) = P(X_t+1 | X_t) | Future state depends only on current state, not history |
State Space | Set of all possible states — finite or countable |
Transition Probability: p_ij = P(X_t+1 = j | X_t = i) | Probability of moving from state i to state j in one step |
Transition Matrix P | Square matrix where entry (i,j) = p_ij — rows sum to 1 |
n-Step Transition: P^(n) | Probability after n steps — multiply matrix by itself n times |
Chapman-Kolmogorov: P^(m+n) = P^(m) * P^(n) | Multi-step transitions can be composed |
Classification of States
| Item | Description |
|---|
Recurrent | Process returns to state with probability 1 — visited infinitely often |
Transient | Process eventually leaves and never returns — finite visits |
Absorbing | Once entered, cannot leave — p_ii = 1 |
Periodic | Can only return at multiples of period d (e.g., pendulum) |
Ergodic | Aperiodic + positive recurrent — unique steady state exists |
Communicating | States i and j reach each other — in the same class |
Steady State
| Item | Description |
|---|
pi = pi * P (pi is row vector) | Steady state: probability distribution that doesn't change after transition |
Solving: pi*(I - P + ones_matrix) = ones_vector | Solve linear system for pi (also pi is left eigenvector of P with eigenvalue 1) |
Interpretation of pi_i | Long-run proportion of time spent in state i |
Convergence: P^n -> 1*pi as n -> infinity | For ergodic chains, n-step transitions converge to steady state |
Existence Condition | Finite, irreducible, aperiodic chain has unique steady state |
Mixing Time | How long until distribution is close to steady state — key for MCMC |
PageRank & Applications
| Item | Description |
|---|
Random Surfer Model | PageRank: P = (1-d)/n * ones + d * A (where A is normalized adjacency) |
Damping Factor d (typically 0.85) | Probability surfer follows a link vs jumping randomly |
Steady State = PageRank Scores | Higher score = more important page in the web graph |
Markov Decision Processes (MDP) | Add actions and rewards to Markov chains — foundation of RL |
Hidden Markov Models (HMM) | States are hidden — observed through emissions; Viterbi algorithm for decoding |
Pro Tip: The Markov property means 'the future depends only on the present, not the past.' If your system has memory beyond the current state, use higher-order Markov chains instead.