Discrete-time Markov chains

Part of Stochastic processes · 3 questions on this topic · What links here

Discrete-time Markov chains

Part Stochastic processes
Chapter 4 of 12 in this part
Previous Random walks and first passage
Next Classes, recurrence, and reversibility
Questions 3
Definitions Discrete-time Markov chain · Stationary distribution

The Markov property says that a well-chosen current state carries everything the next state needs from the past. It does not say that successive states are independent. For a queue, the number of customers present can be enough when arrivals and service are memoryless. Under a service law with memory, the elapsed service time has to sit in the state as well. That modelling choice is on Stochastic processes.

The finite-state definition, the Chapman–Kolmogorov product, simulation from a row of P, and the theorem that P^n settles to one row for an irreducible aperiodic chain are on Markov chains. Using a chain to sample from a target distribution is a different construction, on Markov chains, Gibbs sampling, and Metropolis–Hastings, where the invariant vector is called a stationary distribution. This page keeps the transition-matrix notation and goes further: hitting probabilities and mean hitting times, the two-state spectrum, doubly stochastic chains, and the separation between a stationary law and the distribution reached from one start.

Transition rules

Definition 1 (Discrete-time Markov chain) A process X_0,X_1,\ldots on a finite or countable state space S is a discrete-time Markov chain when

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

for every n and every choice of states. The chain is time-homogeneous when p_{ij} does not depend on n. The transition matrix P=(p_{ij}) has non-negative entries, and every row sums to 1.

Article: Discrete-time Markov chain →

The finite-state case of this definition is the one on Markov chains. Countable S is included here so that a branching process and an unbounded walk fit the same sentence.

If the row vector \mu_0 is the law of X_0, then \mu_n=\mu_0 P^n. The n-step probability is p_{ij}^{(n)}=(P^n)_{ij}. Conditioning on the state at time m splits a trip of length m+n into a trip of length m and a trip of length n:

p_{ij}^{(m+n)}=\sum_{k\in S} p_{ik}^{(m)} p_{kj}^{(n)}.

These are the Chapman–Kolmogorov equations. Matrix multiplication is the sum over every possible intermediate state.

Example 1 (Rain after two days) A two-state weather chain has states sunny and rainy, in that order, and

P=\begin{pmatrix} 0.8 & 0.2 \\ 0.3 & 0.7 \end{pmatrix}.

Question. Starting from sun, find the probability of rain two days later. Also find the probability of sun two days after rain.

Solution. The sunny-to-rainy entry of P^2 sums the two routes through the intermediate day:

(P^2)_{12}=0.8\cdot 0.2+0.2\cdot 0.7=0.30.

The rainy-to-sunny entry is

(P^2)_{21}=0.3\cdot 0.8+0.7\cdot 0.3=0.45.

The two numbers differ. A row-stochastic matrix need not be symmetric, and it need not be column-stochastic. Rows are the current state and columns are the next state. That orientation is the one used with row vectors \mu_n=\mu_0 P^n.

A diagram makes impossible moves visible. The chain

P=\begin{pmatrix} 0.7 & 0.3 & 0 \\ 0.2 & 0.5 & 0.3 \\ 0 & 0.4 & 0.6 \end{pmatrix}

moves only between neighbours, or stays. The one-step probability from state 1 to state 3 is 0. The two-step probability is (P^2)_{13}=0.3\cdot 0.3=0.09, through state 2. Reachability is a property of the powers of P, not only of the positive entries of P itself.

Hitting questions use the same principle

The first-step analysis on Random walks and first passage extends from a path graph to any transition matrix. For a target set A\subset S, let T_A=\inf\{n\ge 0: X_n\in A\}. For disjoint targets A and B, write h_i=\mathbb{P}_i(T_A<T_B). Conditioning on the first step gives

h_i=\sum_j p_{ij} h_j \quad(i\notin A\cup B), \qquad h_i=1\ (i\in A), \qquad h_i=0\ (i\in B).

If the mean hitting time of A is finite, e_i=\mathbb{E}_i T_A solves

e_i=1+\sum_j p_{ij} e_j \quad(i\notin A), \qquad e_i=0\ (i\in A).

The 1 is the step just taken. The sum is the expected remaining time from the next state. On a finite state space these are linear equations, one unknown per state outside the target.

Stationary distributions

Definition 2 (Stationary distribution) A probability row vector \pi is a stationary distribution of P when \pi P=\pi. If X_0 has law \pi, then X_n has law \pi at every time n.

Article: Stationary distribution →

For the weather chain, \pi_S+\pi_R=1 and the balance of probability across the two off-diagonal entries is 0.2\pi_S=0.3\pi_R. Hence \pi_S=1.5\pi_R, and \pi=(0.6,0.4). The initial state affects short-run probabilities. It does not appear in the stationary equation.

If P is doubly stochastic, every column sums to 1 as well as every row. On a finite set with m states the uniform row (1/m,\ldots,1/m) then satisfies

(\pi P)_j=\sum_{i=1}^m \frac{1}{m} p_{ij}=\frac{1}{m},

because column j sums to 1. Uniformity is stationary. Doubly stochastic is a sufficient condition, not a necessary one: the weather chain has a stationary distribution and its columns do not sum to 1.

Multiplying by P moves a probability distribution forward one step. A stationary distribution is a fixed point of that map. Whether an arbitrary starting distribution approaches the fixed point is a separate question. The sampling use of the same fixed-point equation is the stationary distribution of a Monte Carlo chain.

Spectral view for two states

Let

P=\begin{pmatrix} 1-a & a \\ b & 1-b \end{pmatrix}, \qquad a,b>0.

The eigenvalues are 1 and 1-a-b. The stationary law is

\pi=\Bigl(\frac{b}{a+b},\frac{a}{a+b}\Bigr).

The second eigenvalue controls the decay of a deviation from \pi. Write a starting row as \pi plus a multiple of the left eigenvector for 1-a-b. After n steps that deviation is multiplied by (1-a-b)^n. Whenever |1-a-b|<1, which holds as soon as a and b are not both 0 or both 1 in the alternating way below, P^n approaches the matrix with every row equal to \pi.

At a=b=1 the second eigenvalue is -1. The chain swaps states at every step, P^n alternates between P and I, and the powers have no limit. A stationary distribution still exists: \pi=(1/2,1/2). This is the same two-state alternation as the periodic example on Markov chains. The eigenvalue makes the oscillation visible: magnitude 1, and not equal to the eigenvalue 1.

The Markov assumption as a chosen state

Suppose tomorrow’s weather depends on today’s weather and also on whether it has already rained for three days. Two states cannot store a run of length three. A state such as (\text{today's weather},\text{current run length}) can. The state space gets larger, and the transition rule becomes local in time again. Compressing the past into a state makes the one-step calculation possible. Compressing too far drops information the next step uses.

Time homogeneity is a separate assumption. A chain can be Markov at every time with a matrix P_n that changes with n, for example a morning matrix and an evening matrix. The law is then

\mu_n=\mu_0 P_0 P_1\cdots P_{n-1},

not a power of one matrix. Solving \pi P=\pi for a single matrix does not describe that process.

Stationarity and the law from one start

If the chain starts from \pi, every later marginal equals \pi. The path still moves. Stationarity is a statement about marginal distributions, not a claim that the chain freezes.

If the chain starts in a single state i, the law \mu_0 P^n may take time to approach \pi. In a periodic chain it may fail to approach \pi at individual times, even though \pi exists. The class structure, the period, and the conditions that turn a stationary law into a limit from every start are on Classes, recurrence, and reversibility. The limit theorem for an irreducible aperiodic finite chain, with the stepping-stone calculation, is on Markov chains.

Key idea

One row of P is the law of the next state given the current state. Hitting probabilities and mean hitting times solve first-step equations with boundary values on the target. A vector \pi=\pi P is unchanged by one step. Convergence of P^n to that vector needs more than the equation \pi P=\pi.

Questions on this topic

Open a question to attempt it. Its worked answer is folded away at the bottom of the page.

Question Answer
Two steps and the stationary law ✓
A deterministic three-cycle ✓
A doubly stochastic matrix ✓

See also