Markov processes: formula sheet

Key formulas

Markov property (discrete time)

P(Xn+1 = j | X0 = i0, X1 = i1, ..., Xn = i) = P(Xn+1 = j | Xn = i)

Holds for all n, all states and all histories with non-zero probability. Only the current state matters.

Markov property (continuous time)

P(Xt = j | Xs1 = i1, ..., Xsn = in, Xs = i) = P(Xt = j | Xs = i), for s1 < ... < sn < s < t

Conditioning on the most recent known state is enough.

Transition probability (time-homogeneous chain)

pij = P(Xn+1 = j | Xn = i), independent of n

Time-homogeneous means the probabilities do not depend on when the step happens. This is an extra assumption, not part of the Markov property.

Memoryless property of the exponential

P(T > s + t | T > s) = P(T > t)

In a Markov jump process, holding times must be exponential, and the next state must depend only on the current state. The memoryless property means the time already spent in a state does not change the remaining time.

Two-step probability by conditioning

P(Xn+2 = k | Xn = i) = Σj pij pjk

Uses the Markov property and the law of total probability. This is the Chapman-Kolmogorov idea.

Markov property

P(Xₙ₊₁ = j | X₀, X₁, ..., Xₙ = i) = P(Xₙ₊₁ = j | Xₙ = i)

Future depends only on the present state.

One-step transition probability

p_ij(n) = P(Xₙ₊₁ = j | Xₙ = i)

For a time-homogeneous chain, p_ij does not depend on n.

Row sum rule

Σⱼ p_ij = 1 for every state i

Rows sum to 1. Columns need not.

n-step probability

p_ij⁽ⁿ⁾ = P(Xₘ₊ₙ = j | Xₘ = i) = (Pⁿ)_ij

Valid for time-homogeneous chains.

Chapman-Kolmogorov equations

p_ij⁽ᵐ⁺ⁿ⁾ = Σₖ p_ik⁽ᵐ⁾ × p_kj⁽ⁿ⁾

Sum over all intermediate states k. In matrix form, Pᵐ⁺ⁿ = Pᵐ Pⁿ.

Non-homogeneous multi-step matrix

P(m, m+n) = P(m, m+1) × P(m+1, m+2) × ... × P(m+n−1, m+n)

Keep the matrices in time order.

Distribution at time n

π⁽ⁿ⁾ = π⁽⁰⁾ Pⁿ

π is a row vector of state probabilities. Multiply on the left.

Stationary distribution equations

π = πP and Σ πⱼ = 1, with πⱼ ≥ 0

Write one equation per state. One equation is redundant, so drop one and use the sum equal to 1 instead.

Period of a state

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

If d(i) = 1 the state is aperiodic. Any state with pᵢᵢ > 0 has period 1.

Recurrence and transience

Recurrent if P(return to i | X₀ = i) = 1; transient if this is < 1

In a finite chain, closed classes are recurrent and non-closed classes are transient.

Uniqueness

Finite, irreducible chain ⇒ exactly one stationary distribution

If there are several closed classes, there are infinitely many stationary distributions. Each closed class has its own, and any mixture of them also works.

Convergence

Finite, irreducible, aperiodic ⇒ pᵢⱼ(n) → πⱼ as n → ∞ for all i

Every row of Pⁿ tends to π. This needs aperiodicity.

Mean recurrence time

E[return time to i | X₀ = i] = 1 ÷ πᵢ

Valid for a finite irreducible chain.

Visits to a transient state

If the return probability is r < 1, the number of visits (including the start) is geometric with mean 1 ÷ (1 − r)

Useful for expected time spent in a transient state.

Transition rate definition

P(X(t+h) = j | X(t) = i) = h·μij + o(h), for i ≠ j

Also pii(h) = 1 − h·λi + o(h), where o(h)/h → 0.

Total rate of leaving state i

λi = Σ(j≠i) μij

This is the parameter of the exponential holding time in state i.

Holding time distribution

Ti ~ Exp(λi); P(Ti > t) = e^(−λi t); E[Ti] = 1 ÷ λi

Valid for time-homogeneous (constant rate) processes. Var(Ti) = 1 ÷ λi².

Jump probabilities

P(next state is j | jump from i) = μij ÷ λi

These probabilities sum to 1 over j ≠ i.

Generator matrix

Aij = μij (i ≠ j); Aii = −λi; each row sums to 0

Check the row sums every time you build A.

Kolmogorov forward equations

d/dt pij(t) = Σ(k≠j) pik(t)·μkj − pij(t)·λj; matrix form: P′(t) = P(t)·A

Rate into j from other states, minus rate out of j. Starting state i is fixed.

Kolmogorov backward equations

d/dt pij(t) = Σ(k≠i) μik·pkj(t) − λi·pij(t); matrix form: P′(t) = A·P(t)

Here the end state j is fixed and you vary the starting state.

Solution for constant rates

P(t) = exp(tA), with P(0) = I

Useful for two-state models and for checking answers.

Occupancy probability

pii-bar(t) = P(stay in i throughout [0, t]) = e^(−λi t)

Different from pii(t), which allows leaving and returning.

Poisson process

P(N(t) = n) = e^(−λt)·(λt)^n ÷ n!; inter-arrival times ~ Exp(λ)

Increments over disjoint intervals are independent and stationary.

Definition of transition intensity

μij(t) = lim h→0 of P(X(t+h) = j | X(t) = i) ÷ h, for i ≠ j

Holds for i ≠ j. Gives P(move i→j in time h) ≈ h × μij(t).

Total force of leaving a state

μi(t) = Σ over j ≠ i of μij(t)

Waiting time in state i is exponential with this rate if intensities are constant.

Probability of staying in a state

pii-bar(t, t+s) = exp(−∫ from t to t+s of μi(u) du)

This is staying continuously in i. It is not the same as pii(t, t+s), which allows leaving and returning.

Kolmogorov forward equations

∂/∂s pij(t, t+s) = Σ over k ≠ j of [pik(t, t+s) × μkj(t+s)] − pij(t, t+s) × μj(t+s)

Inflow into j minus outflow from j. Initial condition: pij(t, t) = 1 if i = j, else 0.

Kolmogorov backward equations

∂/∂t pij(t, t+s) = μi(t) × pij(t, t+s) − Σ over k ≠ i of [μik(t) × pkj(t, t+s)]

Less often used in exams, but you should recognise it.

Integrated form (healthy to sick)

pHS(t, t+s) = ∫ from 0 to s of pHH-bar(t, t+u) × μHS(t+u) × pSS-bar(t+u, t+s) du

Valid when no return from sick to healthy. Stay healthy, jump at time u, stay sick.

MLE of constant intensity

μ̂ij = Nij ÷ Vi

Nij = number of i→j transitions; Vi = total time spent in state i by all lives.

Variance of the MLE

Var(μ̂ij) ≈ μij ÷ E[Vi], estimated by μ̂ij ÷ Vi = Nij ÷ Vi²

Asymptotic result. Used for approximate confidence intervals: μ̂ ± 1.96 × √(μ̂² ÷ Nij).

Log-likelihood (constant intensities)

ln L = Σ over i≠j of [Nij × ln μij] − Σ over i of [μi × Vi]

Differentiate with respect to each μij separately. Terms for different transitions separate.

Quick revision

• Markov property: given the present state, the future is independent of the past.
• Every row of a transition matrix sums to 1; every row of a generator matrix sums to 0.
• Chapman-Kolmogorov: P(m+n) = P(m) × P(n), so n-step matrix is Pⁿ for a time-homogeneous chain.
• States that communicate form a class; a chain with one class is irreducible.
• A state is recurrent if return is certain, transient otherwise.
• Period of a state is the greatest common divisor of possible return times; period 1 means aperiodic.
• A stationary distribution π satisfies π = πP with Σπᵢ = 1.
• An irreducible, aperiodic finite chain has a unique stationary distribution that is also the limiting distribution.
• In a jump process, holding time in state i is exponential with rate λᵢ = −qᵢᵢ.
• Jump probabilities from i to j are qᵢⱼ ÷ λᵢ for j ≠ i.
• Kolmogorov forward: P′(t) = P(t)A. Backward: P′(t) = A P(t), where A is the generator.
• Stationary distribution of a jump process solves πA = 0 with Σπᵢ = 1.

Common mistakes

• Saying the Markov property means the past has no effect on the future. Fix: Say that the past affects the future only through the current state. Given the present state, extra history adds no information.
• Confusing Markov with time-homogeneous. Fix: Markov is about dependence on history. Time-homogeneous is about the transition probabilities not changing with time. A process can be Markov but not time-homogeneous.
• Rows that do not sum to 1, or reading the matrix by columns. Fix: Rows are from-states, columns are to-states. Check every row sums to 1 before doing anything else.
• Squaring each entry instead of using matrix multiplication. Fix: Pⁿ means P multiplied by itself n times with row-by-column multiplication. Entry (i, j) is Σₖ p_ik p_kj for n = 2.
• Using the column-sum form wrongly: solving Pπ = π instead of πP = π. Fix: Write the equation for each state j as πⱼ = Σᵢ πᵢpᵢⱼ. This sums down column j of P, with each term weighted by πᵢ.
• Forgetting the condition Σπⱼ = 1 and giving a vector that only satisfies πP = π. Fix: Always finish by normalising. The final line of working should be the sum equal to 1.
• Using the wrong diagonal entry in the generator, such as −μij for one arrow rather than the total rate out. Fix: Set Aii = −(sum of all other entries in row i). Confirm every row sums to zero.
• Mixing up forward and backward equations. Fix: In forward equations the rates μkj carry the target state j. In backward equations the rates μik carry the starting state i. Check which index the rate shares with the probability.
• Confusing pii(t, t+s) with the probability of staying continuously in state i. Fix: Use the exponential only when no return is possible or when the question says 'remains continuously'. Otherwise solve Kolmogorov.
• Leaving out an inflow or outflow term in the Kolmogorov equation. Fix: For each state, list all arrows in and all arrows out from the diagram before writing the equation.

Exam tips

• Always state both the time set and the state space. Examiners award separate marks for each.
• When asked to test the Markov property, write the defining equation and compare it to the conditional probability given the full history.
• Use examples from the question context, such as NCD levels or health states, in your answer.
• Keep Markov and time-homogeneous separate in your wording.
• In Paper B style tasks, define states and time steps clearly before building a transition matrix.
• Always state the states, the matrix and the Markov assumption. Examiners award marks for setup before any arithmetic.
• Check row sums at every stage. It catches most arithmetic and set-up errors quickly.
• In written answers, name the Chapman-Kolmogorov equations when you split an n-step probability at an intermediate time.