Lecture 18: Markov Chains III

What this lecture covers

This lecture first shows how steady-state probabilities let you approximate long-horizon transition probabilities and reasons about how quickly a chain "mixes." It then applies Markov chains to a classic real-world design problem: how many phone lines a community needs so that callers rarely get a busy signal, a problem originally solved by Erlang before Markov chains existed as a named theory.

The second half introduces two new calculations for chains with transient states: the probability of eventually being absorbed into a particular recurrent class starting from a given state, and the expected number of steps until absorption (or until first reaching a target state). Both are solved by setting up linear equations that condition on the first transition, extending the divide-and-conquer approach used throughout the Markov chains unit.

Key ideas

• Steady-state independence: as n grows large, X_n becomes approximately independent of the initial state X_0, which is why r_ij(n) can be approximated by pi_j for large n.
• Mixing time: how large n needs to be before the steady-state approximation is accurate depends on how quickly the chain forgets its initial state; chains with small transition probabilities between regions mix slowly and need much larger n.
• The Erlang phone-line problem: phone calls arrive as a Poisson process with rate lambda, and call durations are exponential with rate mu, giving a birth-death Markov chain over the number of busy lines from 0 to B.
• Blocking probability: the probability an arriving call finds all B lines busy is the steady-state probability pi_B, which a system designer wants to keep small (e.g. around 1%) by choosing B appropriately larger than the average number of simultaneous calls lambda/mu.
• Absorption probabilities: for a chain with transient states leading into one of several recurrent classes, the probability a_i of eventually being absorbed into a specific class, starting from transient state i, satisfies a linear system a_i = sum_j p_ij * a_j with known boundary values at the recurrent states.
• Expected time to absorption: the expected number of steps mu_i to reach an absorbing state from transient state i satisfies mu_i = 1 + sum_j p_ij * mu_j, derived by conditioning on the first transition.
• First-passage and recurrence time: the expected time to first reach a specific state s, and the mean recurrence time (starting at s, the expected time to return to s), are computed with the same conditioning technique, distinguishing whether the count starts before or after the first step.

Walkthrough

Steady-state approximation and mixing time (0:37)

The lecture reviews that for a chain with a single, aperiodic recurrent class, X_n becomes approximately independent of the starting state as n grows, justifying the approximation r_ij(n) ~ pi_j. Using the familiar two-state example, it shows how to approximate probabilities like being at a state at both time 100 and time 200, then contrasts a fast-mixing chain with a slow-mixing one (transition probabilities like 0.001) to illustrate that the required n for a good approximation depends on the chain's internal transition rates.

Setting up the Erlang phone-line model (15:04)

The lecture poses the classic problem of dimensioning B phone lines for a community so that calls rarely get blocked. Call arrivals are modeled as a Poisson process with rate lambda, and call durations as exponential with rate mu. Time is discretized into small slots to build a discrete-time birth-death Markov chain whose state is the number of currently busy lines, with upward transition probability lambda*delta and downward probability i*mu*delta from state i.

Solving for blocking probability (24:44)

Using the cut argument for birth-death chains from the previous lecture, the lecture derives a recursion for the steady-state probabilities pi_i and shows that the probability of a new call finding the system busy is pi_B. A numerical example with lambda=30 calls/minute and mean call duration 3 minutes (so about 90 calls active on average) shows that achieving roughly a 1% blocking probability requires about 106 lines, more than the naive average-based estimate.

Absorption probabilities (22:44) and worked example (26:11)

Returning to the general theory, the lecture defines a_i, the probability of eventually being absorbed into a particular recurrent state or class starting from transient state i, and derives the linear equation a_i = sum_j p_ij * a_j by conditioning on the first transition. A worked example with three transient states sets up and solves the resulting system, and the lecture notes that a recurrent class with multiple states can be treated as a single lumped state for this calculation.

Expected time to absorption (33:46)

For chains with a single absorbing state, the lecture defines mu_i, the expected number of steps to absorption from state i, and derives mu_i = 1 + sum_j p_ij * mu_j using the same conditioning approach, illustrated with a small numerical example. It notes that multiple absorbing states can again be lumped into one for this calculation.

First-passage time and mean recurrence time (48:01)

The lecture closes by distinguishing two related quantities: the expected time to first reach a target state s from any other state, and the mean recurrence time, the expected time to return to s given that the chain starts there. Both are solved with the same first-transition conditioning technique, with the key difference being whether the starting state already counts as having reached s.

Before you watch

• Watch the previous two lectures on Markov chain basics and the steady-state convergence theorem, including birth-death processes and the cut argument.
• Review the Poisson process and exponential distribution, since the phone-line model relies on both.
• Be comfortable setting up and solving small linear systems of equations.

Check your understanding

1. Why does a chain with very small transition probabilities between regions require a much larger n before the steady-state approximation becomes accurate?
2. In the Erlang phone-line model, why is the blocking probability equal to the steady-state probability of state B?
3. How is the absorption probability equation a_i = sum_j p_ij * a_j derived from conditioning on the first transition?
4. Why can multiple recurrent classes, or multiple absorbing states, be lumped into a single state when calculating absorption probabilities or expected absorption times?
5. What is the key difference between the expected first-passage time to a state s and its mean recurrence time?