Markov Chains

Markov Chains are a fundamental tool for modeling systems that transition between a finite number of states, where the future state depends only on the current state, not on the sequence of events that preceded it.

I. Core Definitions and Properties

The Markov Property

A sequence of random variables $X_1, X_2, X_3, \dots$ is a Markov Chain if it satisfies the Markov Property (or memoryless property): the conditional probability distribution of the next state, given the present state and all the past states, depends only on the present state.

Transition Matrix

For a discrete state space $\mathcal{X} = \{x_1, x_2, \dots, x_n\}$, the dynamics of the chain are governed by the $n \times n$ Transition Matrix $P$.

• Entry $P_{ij}$: The probability of transitioning from state $x_i$ to state $x_j$.
• Properties: Each entry $P_{ij} \in [0, 1]$, and the sum of entries for each row must total 1 (i.e., $\sum_{j=1}^n P_{ij} = 1$). This makes $P$ a stochastic matrix.
• $k$-step Transition: The probability of moving from state $i$ to state $j$ in $k$ steps is given by the $(i, j)$-th entry of the matrix $P^k$.

II. Classification of States and Chains

The long-term behavior of a Markov Chain is determined by the properties of its states.

III. Stationary Distribution and Long-Term Behavior

The Stationary Distribution $\pi = (\pi_1, \dots, \pi_n)$ is a probability vector that, once reached, remains unchanged by further transitions.

• Defining Equation:
  $$\pi = \pi P, \quad \sum_{i=1}^n \pi_i = 1$$
• Interpretation: $\pi_i$ is the long-run proportion of time the chain spends in state $x_i$. In finance, this can represent the long-run probability of a market being in a certain regime (e.g., high volatility).
• Existence and Uniqueness: A stationary distribution exists for any finite-state Markov Chain. It is unique if and only if the chain is irreducible.

IV. Absorbing Chains and Expected Hitting Time

An Absorbing State $x_i$ is a state from which the chain cannot leave (i.e., $P_{ii} = 1$). A chain is Absorbing if it has at least one absorbing state and every non-absorbing state can reach an absorbing state.

Expected Time to State (Expected Hitting Time)

To find the expected number of steps $\mu_i$ to reach a target state (often an absorbing state) starting from state $x_i$, we solve a system of linear equations.

For a target state $x_n$ (where $\mu_n = 0$):

• Example: To find the expected time to reach $x_3$ from $x_1$ in a $3 \times 3$ chain:
  $$\mu_1 = 1 + P_{11}\mu_1 + P_{12}\mu_2 + P_{13}\mu_3 \quad (\text{where } \mu_3 = 0)$$
  $$\mu_2 = 1 + P_{21}\mu_1 + P_{22}\mu_2 + P_{23}\mu_3 \quad (\text{where } \mu_3 = 0)$$

Gambler's Ruin Problem (A Classic Absorbing Chain)

This is a classic example of an absorbing Markov Chain where the states are the player's current capital, and the absorbing states are 0 (ruin) and $a+b$ (opponent's ruin).

• Fair Coin ($p=0.5$): The probability of ruin (reaching 0) starting with capital $a$ against an opponent with capital $b$ is:
  $$\mathbb{P}(\text{Ruin}) = \frac{b}{a+b}$$
  (Correction: The probability of ruin is $\frac{b}{a+b}$, not $\frac{a}{a+b}$ as stated in the original content. The probability of winning is $\frac{a}{a+b}$.)
• Unfair Coin ($p \ne 0.5$): Let $\rho = \frac{1-p}{p}$ (the odds ratio of losing to winning). The probability of ruin is:
  $$\mathbb{P}(\text{Ruin}) = \frac{\rho^a - \rho^{a+b}}{1 - \rho^{a+b}}$$
  (Correction: The original formula was for the probability of reaching state $a+b$ starting from $a$ in a slightly different formulation. The standard ruin probability is given above.)