A stochastic process is a family of random variables \(\{X_t, t \in T\}\) defined on a common probability space, indexed by a parameter \(t\) (usually representing time). The index set \(T\) can be discrete (\(T = \{0, 1, 2, \ldots\}\)) or continuous (\(T = [0, \infty)\)).
The fundamental challenge in studying stochastic processes lies in understanding three key aspects:
The full joint distribution of a stochastic process is specified by all finite-dimensional distributions:
\[ P(X_{t_1} \leq x_1, X_{t_2} \leq x_2, \ldots, X_{t_k} \leq x_k) \quad \text{for all } k \geq 1 \text{ and } t_1 < t_2 < \cdots < t_k \]
In general, characterising these distributions is intractable. Markov chains offer a powerful simplification by imposing a specific dependence structure that makes the analysis feasible.
The Markov property (or memoryless property) states that the conditional distribution of the future state, given the entire past and present, depends only on the present state. Formally, for all \(n \geq 0\) and all states \(i_0, i_1, \ldots, i_n, j\):
\[ P(X_{n+1} = j \mid X_n = i_n, X_{n-1} = i_{n-1}, \ldots, X_0 = i_0) = P(X_{n+1} = j \mid X_n = i_n) \]
This means that once we know the present state \(X_n\), the past history \(X_0, X_1, \ldots, X_{n-1}\) provides no additional information for predicting the future. The process "forgets" how it arrived at its current state.
Intuition: Think of a chess game — the next move depends on the current board position, not on the sequence of moves that led to it. Or consider the weather: a simple Markov model would predict tomorrow's weather based solely on today's, ignoring last week's pattern.
The Markov property dramatically simplifies analysis: instead of needing all finite-dimensional distributions, the entire process is determined by the initial distribution and the one-step transition probabilities.
A discrete-time Markov chain (DTMC) is a stochastic process \(\{X_n, n = 0, 1, 2, \ldots\}\) satisfying the Markov property, where the state space \(S\) is countable (finite or countably infinite).
The transition probability from state \(i\) to state \(j\) is:
\[ p_{ij} = P(X_{n+1} = j \mid X_n = i) \]
When these probabilities do not depend on \(n\), the chain is called time-homogeneous (we assume this throughout). The transition probabilities are collected in the transition matrix \(\mathbf{P}\):
\[ \mathbf{P} = \begin{pmatrix} p_{00} & p_{01} & p_{02} & \cdots \\ p_{10} & p_{11} & p_{12} & \cdots \\ p_{20} & p_{21} & p_{22} & \cdots \\ \vdots & \vdots & \vdots & \ddots \end{pmatrix} \]
This is a stochastic matrix: all entries are non-negative and each row sums to 1:
\[ p_{ij} \geq 0 \quad \text{and} \quad \sum_{j \in S} p_{ij} = 1 \quad \text{for all } i \in S \]
A discrete-time Markov chain is fully specified by two objects:
From these, any finite-dimensional distribution can be computed:
\[ P(X_0 = i_0, X_1 = i_1, \ldots, X_n = i_n) = \mu_{i_0} \cdot p_{i_0 i_1} \cdot p_{i_1 i_2} \cdots p_{i_{n-1} i_n} \]
Consider a simple weather model with states \(S = \{0 \text{ (Rain)}, 1 \text{ (Sun)}\}\) and transition matrix:
\[ \mathbf{P} = \begin{pmatrix} 0.7 & 0.3 \\ 0.4 & 0.6 \end{pmatrix} \]
If it's raining today, there is a 70% chance of rain tomorrow and 30% chance of sun. If it's sunny, there is a 40% chance of rain tomorrow and 60% chance of sun.
The \(n\)-step transition probability is the probability of going from state \(i\) to state \(j\) in exactly \(n\) steps:
\[ p_{ij}^{(n)} = P(X_{m+n} = j \mid X_m = i) \]
The Chapman-Kolmogorov equations express how multi-step transitions decompose. For any \(0 \leq r \leq n\):
\[ p_{ij}^{(n)} = \sum_{k \in S} p_{ik}^{(r)} \cdot p_{kj}^{(n-r)} \]
This says: to go from \(i\) to \(j\) in \(n\) steps, we can go from \(i\) to some intermediate state \(k\) in \(r\) steps, then from \(k\) to \(j\) in the remaining \(n-r\) steps, and sum over all possible intermediates.
In matrix form, this takes the elegant form:
\[ \mathbf{P}^{(n)} = \mathbf{P}^n \]
That is, the \(n\)-step transition matrix is simply the \(n\)-th power of the one-step transition matrix. This is one of the most useful computational results in the theory.
For our two-state weather chain, the 2-step transition matrix is:
\[ \mathbf{P}^2 = \mathbf{P} \cdot \mathbf{P} = \begin{pmatrix} 0.7 & 0.3 \\ 0.4 & 0.6 \end{pmatrix} \begin{pmatrix} 0.7 & 0.3 \\ 0.4 & 0.6 \end{pmatrix} = \begin{pmatrix} 0.61 & 0.39 \\ 0.52 & 0.48 \end{pmatrix} \]
So if it rains today, the probability of rain two days from now is 0.61.
State \(j\) is accessible from state \(i\) (written \(i \to j\)) if there exists \(n \geq 0\) such that \(p_{ij}^{(n)} > 0\). Two states \(i\) and \(j\) communicate (written \(i \leftrightarrow j\)) if \(i \to j\) and \(j \to i\).
Communication is an equivalence relation, partitioning the state space into communicating classes. A chain is irreducible if there is only one communicating class — i.e., every state can reach every other state.
Let \(f_i\) denote the probability of ever returning to state \(i\), starting from \(i\):
\[ f_i = P(\text{return to } i \mid X_0 = i) = P\left(\bigcup_{n=1}^{\infty} \{X_n = i\} \mid X_0 = i\right) \]
An equivalent characterisation uses the expected number of visits:
\[ \sum_{n=0}^{\infty} p_{ii}^{(n)} = \begin{cases} \infty & \text{if } i \text{ is recurrent} \\ < \infty & \text{if } i \text{ is transient} \end{cases} \]
Key facts:
The period of state \(i\) is defined as:
\[ d(i) = \gcd\{n \geq 1 : p_{ii}^{(n)} > 0\} \]
where \(\gcd\) denotes the greatest common divisor. If \(d(i) = 1\), the state is aperiodic; if \(d(i) > 1\), it is periodic with period \(d(i)\).
Intuition: A periodic chain with period \(d\) can only return to a state at times that are multiples of \(d\). For example, in a random walk on a bipartite graph, the chain alternates between two sets of states, giving period 2.
Periodicity is a class property: all states in a communicating class share the same period. A chain is aperiodic if all its states are aperiodic.
Sufficient condition for aperiodicity: If \(p_{ii} > 0\) for some state \(i\), then \(d(i) = 1\). Self-loops guarantee aperiodicity.
The central question in Markov chain theory: does the chain settle into a long-run equilibrium? The answer is given by the Ergodic Theorem.
For an irreducible, aperiodic, positive recurrent Markov chain, the limit:
\[ \lim_{n \to \infty} p_{ij}^{(n)} = \pi_j \]
exists and is independent of the initial state \(i\). The limiting distribution \(\boldsymbol{\pi} = (\pi_1, \pi_2, \ldots)\) is the unique probability distribution satisfying:
\[ \boldsymbol{\pi} \mathbf{P} = \boldsymbol{\pi} \qquad \text{and} \qquad \sum_{j \in S} \pi_j = 1 \]
Such \(\boldsymbol{\pi}\) is called the stationary distribution (or equilibrium distribution, or invariant measure).
\(\pi_j\) represents the long-run proportion of time the chain spends in state \(j\). It is also the reciprocal of the mean return time:
\[ \pi_j = \frac{1}{E[T_j \mid X_0 = j]} \]
If a chain starts with distribution \(\boldsymbol{\pi}\) (i.e., \(P(X_0 = j) = \pi_j\)), then \(P(X_n = j) = \pi_j\) for all \(n\) — the distribution is preserved over time.
For our two-state chain, we solve \(\boldsymbol{\pi} \mathbf{P} = \boldsymbol{\pi}\):
\[ (\pi_0, \pi_1) \begin{pmatrix} 0.7 & 0.3 \\ 0.4 & 0.6 \end{pmatrix} = (\pi_0, \pi_1) \]
This gives \(0.7\pi_0 + 0.4\pi_1 = \pi_0\) and \(\pi_0 + \pi_1 = 1\). Solving: \(\pi_0 = 4/7 \approx 0.571\) and \(\pi_1 = 3/7 \approx 0.429\). In the long run, it rains about 57% of the time.
The Gambler's Ruin is a classic application of Markov chains. A gambler starts with \(i\) dollars and repeatedly bets \$1. At each play, they win with probability \(p\) and lose with probability \(q = 1 - p\). The game ends when the gambler's capital reaches \(0\) (ruin) or \(N\) (target).
Let \(X_n\) denote the gambler's capital at time \(n\). Then \(\{X_n\}\) is a Markov chain on \(S = \{0, 1, 2, \ldots, N\}\) with transition probabilities:
\[ P(X_{n+1} = i+1 \mid X_n = i) = p, \quad P(X_{n+1} = i-1 \mid X_n = i) = 1-p \quad \text{for } 1 \leq i \leq N-1 \]
States 0 and \(N\) are absorbing: once reached, the chain stays there forever (\(p_{00} = p_{NN} = 1\)).
Let \(r_i = P(\text{ruin} \mid X_0 = i)\) be the probability of reaching 0 starting from \(i\). By first-step analysis:
\[ r_i = p \cdot r_{i+1} + (1-p) \cdot r_{i-1}, \quad 1 \leq i \leq N-1 \]
with boundary conditions \(r_0 = 1\) and \(r_N = 0\). Solving this second-order linear recurrence:
\[ r_i = \begin{cases} \dfrac{(q/p)^i - (q/p)^N}{1 - (q/p)^N} & \text{if } p \neq 1/2 \\[12pt] 1 - \dfrac{i}{N} & \text{if } p = 1/2 \end{cases} \]
When the game is fair (\(p = 1/2\)), ruin probability decreases linearly with initial capital. When \(p < 1/2\) (unfair game), ruin is almost certain as \(N \to \infty\).
In a continuous-time Markov chain (CTMC), transitions can occur at any time \(t \in [0, \infty)\). The Markov property becomes:
\[ P(X(t+s) = j \mid X(s) = i, \{X(u), 0 \leq u < s\}) = P(X(t+s) = j \mid X(s) = i) \]
A CTMC can be decomposed into:
The dynamics are governed by the generator matrix (or rate matrix) \(\mathbf{Q}\):
\[ q_{ij} \geq 0 \text{ for } i \neq j, \qquad q_{ii} = -\sum_{j \neq i} q_{ij} \]
The relationship between \(\mathbf{Q}\) and the transition function \(\mathbf{P}(t)\) is given by the Kolmogorov forward equation:
\[ \mathbf{P}'(t) = \mathbf{P}(t) \mathbf{Q} \]
A birth-death process is a CTMC on \(S = \{0, 1, 2, \ldots\}\) where transitions only occur between neighbouring states:
Applications include queueing systems (M/M/1 queue: \(\lambda_i = \lambda\), \(\mu_i = \mu\)), population dynamics, and chemical kinetics.
Markov chains are the foundation for several fundamental stochastic processes:
The Poisson process \(\{N(t), t \geq 0\}\) is a continuous-time Markov chain counting events that occur at a constant rate \(\lambda\). It is a pure birth process with \(\lambda_i = \lambda\) for all \(i\). Key properties:
Brownian motion (Wiener process) can be viewed as the continuous-state, continuous-time limit of a random walk — itself a discrete Markov chain. If \(X_n\) is a symmetric random walk with step size \(\Delta x\) and time step \(\Delta t\), then as \(\Delta x, \Delta t \to 0\) with \((\Delta x)^2 / \Delta t \to \sigma^2\):
\[ X_{\lfloor t/\Delta t \rfloor} \xrightarrow{d} B(t) \]
where \(B(t)\) is a Brownian motion with variance \(\sigma^2 t\). Brownian motion satisfies the (continuous) Markov property and is the basis for stochastic calculus, diffusion processes, and financial mathematics.