A Markov chain on {1, 2, 3, 4} has rows p₁ = (0.5, 0.5, 0, 0), p₂ = (0.5, 0.5, 0, 0), p₃ = (0.25, 0.25, 0.25, 0.25), p₄ = (0, 0, 0, 1). Which statements are true?

{1, 2} is a closed recurrent class

A Markov chain moves deterministically 1 → 2 → 3 → 1. The period of state 1 is:

undefined, because the chain is deterministic

N(t) is a Poisson process with rate λ. Which statements are true?

The inter-arrival times are i.i.d. exponential with mean 1/λ

N(t) − N(s) ~ Poisson(λ(t − s)) for s < t

Merging N with an independent Poisson process of rate μ gives a Poisson process of rate λ + μ

The inter-arrival times are i.i.d. exponential with mean 1/λ

N(t) − N(s) ~ Poisson(λ(t − s)) for s < t

The time of the third arrival is exponentially distributed

Merging N with an independent Poisson process of rate μ gives a Poisson process of rate λ + μ

W(t) is a standard Brownian motion. Which statements are true?

W(t)/√t ~ N(0, 1) for every t > 0

For s < t, W(t) − W(s) is independent of W(s)

Its sample paths are differentiable with probability 1

W(t)/√t ~ N(0, 1) for every t > 0

For s < t, W(t) − W(s) is independent of W(s)

Stochastic Processes: Markov Chains, Classification of States, Stationary Distributions, the Poisson Process, Birth-and-Death Processes and Brownian Motion

Section 7 of the GATE Statistics paper, and the one no engineering paper asks: Markov chains with finite and countable state space, the classification of states, the limiting behaviour of n-step transition probabilities and the stationary distribution; the Poisson process; birth-and-death processes with their pure-birth and pure-death special cases; and Brownian motion with its basic properties. The examined skills are computational — an n-step probability from a matrix power, a stationary vector from πP = π, an absorption probability, a Poisson-process probability, a birth-and-death equilibrium — and the chapter works each with numbers.

1. Markov chains and n-step transition probabilities

(Xₙ) is a time-homogeneous Markov chain if P(Xₙ₊₁ = j | Xₙ = i, Xₙ₋₁, …, X₀) = p_ij: the future depends on the past only through the present. The transition matrix P = [p_ij] is stochastic (non-negative, rows summing to 1). The Chapman–Kolmogorov equations p_ij^(m+n) = Σ_k p_ik^(m) p_kj⁽ⁿ⁾ say P⁽ⁿ⁾ = Pⁿ, and if the initial distribution is the row vector μ₀, then Xₙ has distribution μ₀Pⁿ.

For P = [[0.7, 0.3], [0.4, 0.6]], p₁₁⁽²⁾ = 0.7 × 0.7 + 0.3 × 0.4 = 0.61. For a two-state chain with P = [[1 − α, α], [β, 1 − β]], Pⁿ = (1/(α + β))[[β, α], [β, α]] + ((1 − α − β)ⁿ/(α + β))[[α, −α], [−β, β]], so every row tends to (β, α)/(α + β) geometrically fast.

2. Classification of states

The vocabulary
Term	Meaning
j accessible from i	p_ij⁽ⁿ⁾ > 0 for some n ≥ 0
Communicating class	maximal set of states accessible from each other; the chain is irreducible if there is one class
Closed class, absorbing state	no exit from the class; an absorbing state has p_ii = 1
Recurrent / transient	return to i is certain (f_ii = 1) / not certain; recurrent iff Σₙ p_ii⁽ⁿ⁾ = ∞
Positive / null recurrent	mean return time μᵢ finite / infinite
Period	d(i) = gcd{n ≥ 1 : p_ii⁽ⁿ⁾ > 0}; aperiodic if d = 1

Recurrence, transience and the period are class properties: every state of a communicating class shares them.
A finite chain has at least one recurrent state and no null-recurrent state; a finite closed class is positive recurrent, and a class from which the chain can leave for ever is transient.
The simple symmetric random walk on ℤ is null recurrent (p₀₀⁽²ⁿ⁾ ~ 1/√(πn), whose sum diverges); with p ≠ 1/2 it is transient.

Absorption: with absorbing states, hᵢ = P(absorbed in A | start i) solves hᵢ = Σ_j p_ijh_j with h = 1 on A and 0 on the other absorbing states. In the gambler’s ruin on {0, …, N} with up-probability p and r = q/p ≠ 1, P(reach N | start i) = (1 − rⁱ)/(1 − r^N); for p = 1/2 it is i/N. With p = 0.6, i = 2, N = 4: (1 − 4/9)/(1 − 16/81) = 9/13 ≈ 0.69.

3. Stationary distributions and limiting behaviour

π is stationary if πP = π with πᵢ ≥ 0 and Σπᵢ = 1: started from π, the chain stays in π. An irreducible chain has a stationary distribution iff it is positive recurrent, and then it is unique with πᵢ = 1/μᵢ, the reciprocal of the mean return time. If in addition the chain is aperiodic, p_ij⁽ⁿ⁾ → π_j for every i: Pⁿ converges to a matrix whose rows are all π. A periodic chain still has a stationary π, but Pⁿ oscillates.

Two states: π = (β, α)/(α + β). For P = [[0.7, 0.3], [0.4, 0.6]], π = (4/7, 3/7).
P = [[0.5, 0.5, 0], [0.25, 0.5, 0.25], [0, 0.5, 0.5]]: π₁ = 0.5π₁ + 0.25π₂ gives π₂ = 2π₁, symmetry gives π₃ = π₁, so π = (1/4, 1/2, 1/4) and the mean return time to state 1 is 4.
A doubly stochastic P (columns also sum to 1) on k states has the uniform stationary distribution 1/k.
Detailed balance πᵢp_ij = π_jp_ji is sufficient for stationarity and is the quick route for birth-and-death chains.

4. The Poisson process

A counting process N(t) with N(0) = 0 is a Poisson process of rate λ if it has independent increments and N(t + s) − N(s) ~ Poisson(λt) for all s, t ≥ 0. Equivalently: the inter-arrival times are i.i.d. Exp(λ), so the n-th arrival time Sₙ ~ Gamma(n, λ). With λ = 3 per hour, P(N(2) = 4) = e⁻⁶6⁴/4! = 0.134 and P(no arrival in 20 minutes) = e⁻¹ = 0.368.

Superposition: independent Poisson processes of rates λ and μ merge into one of rate λ + μ, and each arrival comes from the first with probability λ/(λ + μ).
Thinning: if each arrival is kept independently with probability p, the kept arrivals form a Poisson process of rate λp, independent of the discarded ones. With λ = 10 per hour and p = 0.4, the first kept arrival comes after half an hour with probability e^{−4 × 0.5} = e⁻² = 0.135.
Conditional uniformity: given N(t) = n, the arrival times are distributed as the order statistics of n i.i.d. U(0, t). So given N(1) = 3, N(0.5) ~ Bin(3, 1/2) and P(N(0.5) = 1) = 3/8.

5. Birth-and-death, pure-birth and pure-death processes

A birth-and-death process is a continuous-time Markov chain on {0, 1, 2, …} that moves n → n + 1 at rate λₙ and n → n − 1 at rate μₙ. Its probabilities Pₙ(t) obey the forward equations P′ₙ = λₙ₋₁Pₙ₋₁ − (λₙ + μₙ)Pₙ + μₙ₊₁Pₙ₊₁. Setting the derivatives to zero and using balance across each cut gives the equilibrium πₙ = π₀ ∏_k=1ⁿ λ_k−1/μ_k, normalised to sum to 1 (possible iff the series converges).

M/M/1 queue: λₙ = λ, μₙ = μ, ρ = λ/μ < 1 gives πₙ = (1 − ρ)ρⁿ, P(empty) = 1 − ρ, mean number ρ/(1 − ρ). With λ = 2, μ = 3, the mean number in the system is 2.
Finite chain: states 0, 1, 2 with λ₀ = 2, λ₁ = 1, μ₁ = 1, μ₂ = 2: π₁ = 2π₀, π₂ = π₁ × 1/2 = π₀, so π = (1/4, 1/2, 1/4).
Pure birth (μₙ = 0): with λₙ = λ it is the Poisson process; with λₙ = nλ (Yule) started from one individual, N(t) is geometric with P(N(t) = n) = e^−λt(1 − e^−λt)ⁿ⁻¹ and E N(t) = e^λt.
Pure death (λₙ = 0): with μₙ = nμ from N(0) = N, each individual survives to t independently with probability e^−μt, so N(t) ~ Bin(N, e^−μt).

6. Brownian motion

Standard Brownian motion W(t) has W(0) = 0, independent increments, W(t) − W(s) ~ N(0, t − s) for s < t, and continuous paths. Consequences: Cov(W(s), W(t)) = min(s, t), so Var(W(2) + W(3)) = 2 + 3 + 2 × 2 = 9; the scaling W(ct)/√c is again a standard Brownian motion; the paths are continuous but nowhere differentiable and of unbounded variation. The reflection principle gives P(max_0≤s≤t W(s) ≥ a) = 2P(W(t) ≥ a) for a > 0: for t = 4 and a = 2, 2(1 − Φ(1)) = 0.3174.

⚠️ Covariance is the minimum, not the product

W(s) and W(t) are strongly correlated: W(t) = W(s) + (an independent increment). So Cov(W(s), W(t)) = Var W(s) = s for s < t. Treating W(2) and W(3) as independent gives Var(W(2) + W(3)) = 5 instead of 9.

Key takeaways

P⁽ⁿ⁾ = Pⁿ (Chapman–Kolmogorov); the distribution at time n is μ₀Pⁿ.
Recurrence, transience and period are class properties; a finite chain has no null-recurrent states; recurrence ⇔ Σp_ii⁽ⁿ⁾ = ∞.
Irreducible positive recurrent ⇒ unique π with πᵢ = 1/μᵢ; add aperiodicity and every row of Pⁿ → π. Two states: π = (β, α)/(α + β).
Poisson process: N(t) ~ Poisson(λt), Exp(λ) gaps, Gamma(n, λ) arrival times; superposition adds rates, thinning multiplies by p, and given N(t) = n the arrivals are uniform.
Birth-and-death equilibrium: πₙ = π₀∏λ_k−1/μ_k; M/M/1 has πₙ = (1 − ρ)ρⁿ; Yule mean e^λt.
Brownian motion: Cov = min(s, t), continuous nowhere-differentiable paths, P(max ≥ a) = 2P(W(t) ≥ a).

Practice questions (17)

Attempt each one before opening the answer. Every explanation names the tempting wrong option as well as the right one, because that is where marks are lost.

A Markov chain on states {1, 2} has transition matrix P = [[0.7, 0.3], [0.4, 0.6]]. P(X₂ = 1 | X₀ = 1), correct to two decimal places, is ____.
Numerical answer — type the value.
Show answer
Answer: 0.61
p₁₁⁽²⁾ = p₁₁p₁₁ + p₁₂p₂₁ = 0.49 + 0.12 = 0.61, the (1, 1) entry of P². Squaring the entry, 0.7² = 0.49, forgets the path 1 → 2 → 1.
For the chain with P = [[0.7, 0.3], [0.4, 0.6]], the stationary probability of state 1, correct to three decimal places, is ____.
Numerical answer — type the value.
Show answer
Answer: 0.571
π₁ = 0.7π₁ + 0.4π₂ gives 0.3π₁ = 0.4π₂, so π = (4/7, 3/7) and π₁ = 0.5714 → 0.571. The formula β/(α + β) with α = 0.3 (leaving 1) and β = 0.4 (entering 1) is the same; using α/(α + β) = 3/7 swaps them.
A Markov chain on {1, 2, 3} has P = [[0.5, 0.5, 0], [0.25, 0.5, 0.25], [0, 0.5, 0.5]]. Starting from state 1, the expected number of steps until the chain first returns to state 1 is ____.
Numerical answer — type the value.
Show answer
Answer: 4
The chain is irreducible and finite. πP = π: π₁ = 0.5π₁ + 0.25π₂ ⇒ π₂ = 2π₁, and by symmetry π₃ = π₁, so π = (1/4, 1/2, 1/4). The mean return time is μ₁ = 1/π₁ = 4. Answering 2 gives the return time to state 2.
A Markov chain on {1, 2, 3, 4} has rows p₁ = (0.5, 0.5, 0, 0), p₂ = (0.5, 0.5, 0, 0), p₃ = (0.25, 0.25, 0.25, 0.25), p₄ = (0, 0, 0, 1). Which statements are true?
1. State 4 is absorbing
2. State 3 is transient
3. {1, 2} is a closed recurrent class
4. The chain is irreducible
Show answer
Answer: A — State 4 is absorbing; B — State 3 is transient; C — {1, 2} is a closed recurrent class
(A) p₄₄ = 1. (B) From 3 the chain leaves with probability 3/4 each step and can never come back (no state leads to 3), so return is not certain. (C) 1 and 2 communicate and nothing leaves {1, 2}; a finite closed class is recurrent. (D) False: 3 is not accessible from 1, 2 or 4.
A Markov chain moves deterministically 1 → 2 → 3 → 1. The period of state 1 is:
1. 3
2. 1
3. 2
4. undefined, because the chain is deterministic
Show answer
Answer: A — 3
Returns to 1 happen only at times 3, 6, 9, …, so d = gcd{3, 6, 9, …} = 3. Such a chain has the stationary distribution (1/3, 1/3, 1/3), but Pⁿ cycles and never converges — the reason the convergence theorem needs aperiodicity.
A gambler starts with 2 units and bets 1 unit at a time, winning each bet with probability 0.6. She stops on reaching 4 units or 0. The probability that she reaches 4, correct to two decimal places, is ____.
Numerical answer — type the value.
Show answer
Answer: 0.69
With r = q/p = 2/3: P = (1 − r²)/(1 − r⁴) = (1 − 4/9)/(1 − 16/81) = (5/9)/(65/81) = 9/13 = 0.692 → 0.69. First-step check: h₂ = 0.6h₃ + 0.4h₁, h₁ = 0.6h₂, h₃ = 0.6 + 0.4h₂ gives h₂ = 0.36/0.52 = 9/13. The fair-game answer i/N = 0.5 ignores the edge.
Customers arrive as a Poisson process at 3 per hour. The probability of exactly 4 arrivals in 2 hours, correct to three decimal places, is ____.
Numerical answer — type the value.
Show answer
Answer: 0.134
N(2) ~ Poisson(6): e⁻⁶ × 6⁴/4! = 0.002479 × 54 = 0.1339 → 0.134. Using λ = 3 without scaling by the 2 hours gives e⁻³3⁴/24 = 0.168.
Arrivals form a Poisson process of rate 3 per hour. The probability of no arrival in a 20-minute interval, correct to three decimal places, is ____.
Numerical answer — type the value.
Show answer
Answer: 0.368
20 minutes is 1/3 hour, so N ~ Poisson(1) and P(N = 0) = e⁻¹ = 0.3679 → 0.368. Using 20 as the time in hours gives e⁻⁶⁰ ≈ 0.
For a Poisson process, it is given that exactly 3 arrivals occurred in [0, 1]. The probability that exactly 1 of them occurred in [0, 0.5], correct to three decimal places, is ____.
Numerical answer — type the value.
Show answer
Answer: 0.375
Given N(1) = 3, the three arrival times are i.i.d. U(0, 1) in distribution, so the number in [0, 0.5] is Bin(3, 1/2): 3 × (1/2)³ = 0.375. The rate λ cancels. Computing an unconditional Poisson probability requires a rate the question never gave.
Customers arrive as a Poisson process of rate 10 per hour, and each is independently female with probability 0.4. The probability that the first female customer arrives after 30 minutes, correct to three decimal places, is ____.
Numerical answer — type the value.
Show answer
Answer: 0.135
Thinning: female arrivals are Poisson with rate 10 × 0.4 = 4 per hour. P(none in 0.5 h) = e^{−4 × 0.5} = e⁻² = 0.1353 → 0.135. Using the full rate 10 gives e⁻⁵ = 0.007.
An M/M/1 queue has arrival rate λ = 2 and service rate μ = 3. In equilibrium, the expected number of customers in the system is ____.
Numerical answer — type the value.
Show answer
Answer: 2
ρ = 2/3 and πₙ = (1 − ρ)ρⁿ, a geometric distribution on {0, 1, …} with mean ρ/(1 − ρ) = (2/3)/(1/3) = 2. Answering 2/3, the utilisation, gives P(server busy), not the mean number.
A birth-and-death process on {0, 1, 2} has birth rates λ₀ = 2, λ₁ = 1 and death rates μ₁ = 1, μ₂ = 2. The equilibrium probability of state 0, correct to two decimal places, is ____.
Numerical answer — type the value.
Show answer
Answer: 0.25
Balance across each cut: λ₀π₀ = μ₁π₁ ⇒ π₁ = 2π₀; λ₁π₁ = μ₂π₂ ⇒ π₂ = π₁/2 = π₀. So π₀(1 + 2 + 1) = 1 and π₀ = 0.25. Putting the rates the wrong way round (π₁ = (μ₁/λ₀)π₀) gives π₁ = π₀/2 and a different answer.
W(t) is a standard Brownian motion. Var(W(2) + W(3)) is ____.
Numerical answer — type the value.
Show answer
Answer: 9
Var W(2) + Var W(3) + 2Cov(W(2), W(3)) = 2 + 3 + 2 min(2, 3) = 9. Equivalently W(2) + W(3) = 2W(2) + (W(3) − W(2)), with variance 4 × 2 + 1 = 9. Treating the two as independent gives 5.
W(t) is a standard Brownian motion. Using Φ(1) = 0.8413, P(max_0≤s≤4 W(s) ≥ 2), correct to four decimal places, is ____.
Numerical answer — type the value.
Show answer
Answer: 0.3174
Reflection principle: P(max ≥ a) = 2P(W(t) ≥ a) = 2P(Z ≥ 2/√4) = 2(1 − 0.8413) = 0.3174 (0.3173 with Φ(1) unrounded). Forgetting the factor 2 gives P(W(4) ≥ 2) = 0.1587, which counts only paths that end above 2, not those that touched 2 and came back.
N(t) is a Poisson process with rate λ. Which statements are true?
1. The inter-arrival times are i.i.d. exponential with mean 1/λ
2. N(t) − N(s) ~ Poisson(λ(t − s)) for s < t
3. The time of the third arrival is exponentially distributed
4. Merging N with an independent Poisson process of rate μ gives a Poisson process of rate λ + μ
Show answer
Answer: A — The inter-arrival times are i.i.d. exponential with mean 1/λ; B — N(t) − N(s) ~ Poisson(λ(t − s)) for s < t; D — Merging N with an independent Poisson process of rate μ gives a Poisson process of rate λ + μ
(A), (B) are equivalent definitions of the process. (C) False: S₃ is the sum of three i.i.d. Exp(λ) gaps, so S₃ ~ Gamma(3, λ). (D) Independent increments survive the merge, and Poisson(λt) + Poisson(μt) = Poisson((λ + μ)t).
W(t) is a standard Brownian motion. Which statements are true?
1. Cov(W(s), W(t)) = min(s, t)
2. Its sample paths are differentiable with probability 1
3. W(t)/√t ~ N(0, 1) for every t > 0
4. For s < t, W(t) − W(s) is independent of W(s)
Show answer
Answer: A — Cov(W(s), W(t)) = min(s, t); C — W(t)/√t ~ N(0, 1) for every t > 0; D — For s < t, W(t) − W(s) is independent of W(s)
(A) Cov(W(s), W(s) + (W(t) − W(s))) = Var W(s) = s. (B) False: the paths are continuous but nowhere differentiable almost surely — the difference quotient has variance 1/h → ∞. (C) W(t) ~ N(0, t). (D) Independent increments over the disjoint intervals [0, s] and [s, t].
In a Yule (linear pure-birth) process with birth rate λ per individual, started from one individual, E[N(t)] equals:
1. e^λt
2. 1 + λt
3. λt
4. e^−λt
Show answer
Answer: A — e^{λt}
m(t) = E N(t) satisfies m′ = λm with m(0) = 1, so m = e^λt; equivalently N(t) is geometric with success probability e^−λt, mean e^λt. 1 + λt is the answer for a constant birth rate (a Poisson process started at 1), where the population does not feed its own growth.