Markov Chains

A Markov chain is a mathematical model for a system that transitions between a set of states according to probabilistic rules, with one critical restriction: the probability of moving to any particular state depends only on the current state, not on the sequence of states that preceded it. This is called the Markov property (or memorylessness).

Formally, a discrete-time Markov chain {X₀, X₁, X₂, ...} satisfies:

P(X_n+1 = j | X_n = i, X_n-1 = i_n-1, ..., X₀ = i₀) = P(X_n+1 = j | X_n = i)

The conditional dependence on the full history collapses to dependence on only the current state. This simplification makes Markov chains mathematically tractable while still being powerful enough to model many real-world systems.

Examples of systems modeled as Markov chains include random walks, board games (Monopoly, Snakes and Ladders), weather patterns, credit rating transitions, and market regime switching models used in quantitative finance.

A Markov chain with n states is fully described by its transition probability matrix P, where entry P_ij is the probability of moving from state i to state j:

Each row sums to 1 (you must go somewhere). The matrix can be multiplied by itself to compute multi-step probabilities: P^k_ij gives the probability of being in state j after k steps, starting from state i.

Key properties:

• Stationary distribution (π): A probability distribution that is unchanged by the transition matrix: πP = π. If the chain is ergodic (irreducible and aperiodic), it converges to this unique stationary distribution regardless of the starting state.
• Absorbing states: A state that, once entered, cannot be left (P_ii = 1). Absorbing Markov chains model processes with permanent endpoints, like gambler's ruin (you either go broke or reach a target).
• Expected hitting time: The expected number of steps to reach a particular state from a given starting state. Computed by setting up a system of linear equations from the transition probabilities.
• Recurrence and transience: A state is recurrent if the chain returns to it with probability 1; transient if there's a positive probability of never returning.

The gambler's ruin problem is the most famous Markov chain application and a classic interview question.

Problem: A gambler starts with $3 and repeatedly bets $1 on a fair coin flip (50/50). The game ends when the gambler reaches $5 (wins) or $0 (goes bust). What is the probability of winning?

Setup: States are {0, 1, 2, 3, 4, 5}. States 0 and 5 are absorbing. From any other state i, P(i → i+1) = 0.5 and P(i → i-1) = 0.5.

Solution: Let p_i = probability of reaching $5 starting from state i.

• Boundary conditions: p₀ = 0 (already bust), p₅ = 1 (already won).
• Recurrence: p_i = 0.5 × p_i+1 + 0.5 × p_i-1 for i = 1, 2, 3, 4.

For a fair coin, the solution is linear: p_i = i/5.

So p₃ = 3/5 = 60%.

Expected duration: The expected number of bets until the game ends, starting from $3, can also be computed via a system of equations. The answer is i × (N - i) = 3 × 2 = 6 bets.

For a biased coin (probability p of winning each bet), the solution changes to: p_i = (1 - (q/p)ⁱ) / (1 - (q/p)^N), where q = 1 - p.

Markov chains have several important applications in quantitative finance:

• Credit rating transitions: Rating agencies model the probability of a company moving between credit ratings (AAA, AA, A, BBB, ..., D) using a Markov chain transition matrix estimated from historical data. This is fundamental to credit risk modeling and bond pricing.
• Regime switching models: Financial markets alternate between "regimes" (e.g., low-volatility trending vs. high-volatility mean-reverting). Hidden Markov Models (HMMs) treat the regime as a hidden Markov chain and infer the current regime from observed data. This is used for dynamic strategy allocation at quant hedge funds.
• Random walks: A simple random walk on integers is the simplest Markov chain — and the foundation for modeling stock prices. Brownian motion is the continuous-time, continuous-space limit of a random walk.
• Monte Carlo Markov Chain (MCMC): Algorithms like Metropolis-Hastings and Gibbs sampling use Markov chains to sample from complex probability distributions, enabling Bayesian inference in high-dimensional models.
• Interview questions: Random walk, gambler's ruin, and expected stopping time problems are staples of quant interviews. Understanding Markov chains gives you a systematic framework for solving them.