Markov chains: formula sheet

Key formulas

Stochastic process

{X_t : t ∈ T}, with X_t taking values in state space S

Always state S and T when asked to describe or classify a process.

Markov property (discrete time)

P(X_n+1 = j | X_0 = i_0, ..., X_n = i_n) = P(X_n+1 = j | X_n = i_n)

Holds for all n and all states and histories with non-zero probability.

Markov property (general)

P(X_t ∈ A | X_s1 = x_1, ..., X_sn = x_n, X_s = x) = P(X_t ∈ A | X_s = x), for s1 < ... < sn < s < t

Use this form for continuous time. A is any subset of the state space.

Time-homogeneity

P(X_s+t = j | X_s = i) = P(X_t = j | X_0 = i) for all s ≥ 0

Transition probabilities depend only on the elapsed time t.

One-step transition probability

p_ij = P(X_n+1 = j | X_n = i)

Used for a time-homogeneous Markov chain. Each row sums to 1: Σ_j p_ij = 1.

One-step transition probability

p_ij = P(X_{n+1} = j | X_n = i)

Holds for all n if the chain is time-homogeneous. Each row of P sums to 1.

Markov property

P(X_{n+1} = j | X_n = i, X_{n-1} = i_{n-1}, ..., X_0 = i_0) = P(X_{n+1} = j | X_n = i)

Future depends only on the present state.

Chapman-Kolmogorov equations

p_ij^(m+n) = Σ_k p_ik^(m) × p_kj^(n)

Sum over all states k. Valid for any non-negative integers m and n.

Matrix form

P^(n) = P^n

Entry (i, j) of P^n is the n-step probability from i to j. Use for time-homogeneous chains.

Distribution after n steps

π_n = π_0 P^n

π_0 is a row vector of the initial distribution.

Row-sum check

Σ_j p_ij = 1 for each i

Use to check P and also to check P^n.

Stationary distribution equations

π = πP, that is π_j = Σ_i π_i p_ij, with Σ_j π_j = 1 and π_j ≥ 0

One balance equation is redundant, so drop one and use Σπ = 1 instead.

Period of a state

d(i) = gcd{ n ≥ 1 : p_ii(n) > 0 }

If d(i) = 1 the state is aperiodic. Any state with p_ii > 0 is aperiodic.

Communication

i ↔ j if i → j and j → i

Communicating classes partition the state space.

Recurrence and transience

Recurrent: P(return to i | start at i) = 1. Transient: P(return) < 1

In a finite chain, closed class means recurrent. A class that is not closed is transient.

Mean recurrence time

m_i = 1 ÷ π_i

Applies to an irreducible chain with a stationary distribution. It is the expected number of steps to return to i. A recurrent state is positive recurrent if this expected return time is finite. In a finite chain every recurrent state is positive recurrent.

Convergence condition

Finite, irreducible and aperiodic ⇒ p_ij(n) → π_j for all i, j

Without aperiodicity the limit may not exist.

Detailed balance (check for reversibility)

π_i p_ij = π_j p_ji for all i, j

If this holds with Σπ = 1, then π is stationary. Detailed balance is sufficient but not necessary for π to be stationary; a stationary distribution need not satisfy detailed balance.

Markov property

P(X(n+1) = j | X(n) = i, X(n−1), ..., X(0)) = P(X(n+1) = j | X(n) = i)

The future depends on the present only. Time-homogeneous means these probabilities do not change with n.

Chapman-Kolmogorov

P(n+m) = P(n) × P(m), so P(n) = Pⁿ

Use matrix powers for n-step probabilities. In a time-homogeneous chain, the n-step matrix is the nth power of P.

Stationary distribution

π = πP and Σ π(i) = 1

Solve the equations, drop one redundant equation, and use the sum to 1 condition. It is the long-run distribution for an irreducible, aperiodic chain with finitely many states.

Long-run average premium

Σ π(i) × premium(i)

Premium at each level is full premium × (1 − discount).

Simple random walk mean and variance

E[X(n)] = X(0) + n(p − q); Var[X(n)] = 4npq

Steps are +1 with probability p and −1 with probability q, independent.

Gambler's ruin, p ≠ q

P(reach N before 0 | start i) = (1 − (q/p)^i) ÷ (1 − (q/p)^N)

Absorbing barriers at 0 and N, start 0 ≤ i ≤ N. The probability of ruin is 1 minus this.

Gambler's ruin, p = q = ½

P(reach N before 0 | start i) = i ÷ N

Use this when the walk is fair. The general formula gives 0 ÷ 0 here.

Estimating transition probabilities

p̂(i,j) = n(i,j) ÷ n(i), where n(i) = Σ over j of n(i,j)

This is the maximum likelihood estimate. n(i,j) counts observed moves from i to j. Count only transitions, so the final observation has no next move. Approximate variance is p̂(1 − p̂) ÷ n(i).

Testing the Markov assumption

χ² = Σ (Observed − Expected)² ÷ Expected over triples (i,j,k)

Compare counts of consecutive triples with those expected under a first-order chain. With m states and all transitions possible, the degrees of freedom are m(m−1)².

Quick revision

• Markov property: P(X_(n+1) = j | X_n = i, X_(n-1), ..., X_0) = P(X_(n+1) = j | X_n = i).
• Each row of the transition matrix P sums to 1, and every entry is between 0 and 1.
• Chapman-Kolmogorov: p_ij^(n+m) = Σ_k p_ik^(n) p_kj^(m), so P^(n+m) = P^(n) P^(m).
• For a time-homogeneous chain, the n-step matrix is P^n.
• State j is accessible from i if p_ij^(n) > 0 for some n ≥ 0. States communicate if each is accessible from the other.
• A chain is irreducible if all states form one communicating class.
• The period of state i is the greatest common divisor of all n with p_ii^(n) > 0. Period 1 means aperiodic.
• A state is recurrent if the chain returns to it with probability 1, and transient otherwise. In a finite chain, a closed class is recurrent.
• A stationary distribution π satisfies πP = π with Σπ_i = 1 and π_i ≥ 0.
• A finite irreducible chain has a unique stationary distribution. If it is also aperiodic, p_ij^(n) → π_j as n → ∞.
• An absorbing state has p_ii = 1.
• Simple random walk: steps +1 with probability p and -1 with probability 1 - p. It is irreducible with period 2 on the integers.

Common mistakes

• Saying the Markov property means the future is independent of the past. Fix: Say the future is independent of the past given the present. Past and future can still be strongly dependent overall.
• Treating Markov and time-homogeneous as the same thing. Fix: Check them separately. Markov concerns dependence on history. Time-homogeneity concerns whether probabilities change with time.
• Multiplying entries of P together element by element instead of doing matrix multiplication. Fix: Use row-by-column multiplication. Entry (i, j) of P² is Σ_k p_ik p_kj.
• Multiplying in the wrong order, such as P π0 instead of π0 P. Fix: In this course the distribution is a row vector on the left: π_n = π_0 P^n. Check the dimensions.
• Calling a class recurrent just because it is a class, or calling every state in a reducible chain recurrent. Fix: Look for any arrow leaving the class. If there is one, the class is transient in a finite chain.
• Claiming a chain is aperiodic because it is irreducible. Fix: Check the period separately. A chain that alternates between two groups of states has period 2, even though it is irreducible.
• Writing rows that do not sum to 1, or filling the matrix by columns Fix: After writing P, add each row. At the top level, a no-claim stays at the top, so it adds to the staying probability.
• Using πP = π with columns instead of rows, or forgetting Σπ = 1 Fix: Write π as a row vector, multiply on the left, and always use the sum condition to scale the solution.

Exam tips

• In definition questions, write the Markov property as an equation and also in words, with the phrase given the present.
• When asked to classify a process, always give both the state space type and the time set type. Marks are usually split between them.
• If a process is not Markov, show why with a concrete dependence on earlier values. Then say how redefining the state could fix it.
• Check that every row of a transition matrix sums to 1 before using it. This catches arithmetic slips.
• In Paper B, set out the state space and time-homogeneity assumption in a comment or a line of text before you code a chain.
• Write the matrix with row and column labels. Most lost marks come from reading the wrong row or column.
• In written questions, quote the Chapman-Kolmogorov equation before you use it, then show each product term.
• For n = 2 or 3 to a single target state, the row-vector method is faster and less error-prone than finding the full P^n.