Lecture 17: Markov Chains II

What this lecture covers

This lecture asks whether the state probabilities of a Markov chain always settle to a fixed steady-state value as time goes on, and if so, whether that value depends on where the chain started. Building on the previous lecture's definitions of transition probabilities, recurrence, and transience, it identifies the two conditions needed for steady-state convergence: a single recurrent class and no periodicity.

After stating the steady-state convergence theorem and deriving the balance equations that the steady-state probabilities must satisfy, the lecture reinterprets those probabilities as long-run visit frequencies. It then specializes to birth-death processes, a structured subclass of chains that includes queueing systems, and derives a closed-form geometric solution for a simple, heavily loaded or unloaded queue.

Key ideas

• Time homogeneity: a Markov chain's transition probability p_ij is the same every time the chain is at state i, regardless of when or how it got there.
• Steady-state convergence theorem: if a chain has a single recurrent class and is not periodic, the n-step transition probabilities r_ij(n) converge to a limit pi_j that does not depend on the starting state i.
• Periodicity: a chain is periodic if its states can be grouped into clusters such that transitions always move to the next cluster in a fixed cycle; any self-transition immediately rules out periodicity.
• Balance equations: taking the limit of the n-step recursion gives pi_j = sum_k pi_k * p_kj, a linear system solved together with the normalization condition sum_j pi_j = 1.
• Frequency interpretation: pi_j can be understood as the long-run fraction of time the chain spends at state j, and the balance equations express that the frequency of transitions into j equals the frequency of being at j.
• Birth-death process: a chain whose states form a line, where each transition moves up by one, down by one, or stays put, modeling queues, populations, or epidemics.
• Cut argument for birth-death chains: because crossings between adjacent states i and i+1 must balance in the long run, pi_i * p_i = pi_(i+1) * q_(i+1) gives a simple recursion for the steady-state probabilities.
• Load factor rho = p/q: for a constant-rate birth-death chain, rho determines whether the state distribution is uniform (rho=1), or, for rho<1 and unbounded state space, a geometric distribution pi_i = (1-rho) * rho^i.

Walkthrough

Review and the n-step recursion (0:00)

The lecture recaps the Markov chain definition, time homogeneity, and the recursive formula for n-step transition probabilities, then works two short examples: computing the probability of a specific multi-step trajectory by multiplying transition probabilities along the path, and contrasting a brute-force enumeration of trajectories with the more efficient recursive approach.

Recurrent classes and periodicity (11:20)

The lecture reviews recurrent and transient states from the previous lecture, explains that multiple separate recurrent classes make the initial state matter permanently, and introduces periodicity: a chain is periodic if its states split into clusters that are visited in a fixed cyclic order. It gives the practical shortcut that any self-transition rules out periodicity.

The steady-state convergence theorem (18:39)

The lecture states that when a chain has a single recurrent class and no periodicity, the n-step transition probabilities converge to steady-state values pi_j independent of the starting state, and gives the intuitive argument: two copies of the chain started at different states will eventually collide at the same state due to randomness, after which their futures are identical.

Deriving and interpreting the balance equations (25:15)

Taking the limit of the n-step recursion produces the balance equations pi_j = sum_k pi_k * p_kj, solved alongside the normalization condition since the raw system is singular. The lecture then reinterprets pi_j as a long-run visiting frequency, showing that the balance equations express a matching of the frequency of transitions into a state with the frequency of being at that state, and reworks the previous lecture's two-state example to confirm pi_1 = 2/7, pi_2 = 5/7.

Birth-death processes (33:35)

The lecture introduces birth-death processes: chains whose states form a line and whose transitions only move one step up, one step down, or stay put, giving examples such as queue lengths, active phone calls, and disease counts in an epidemic model.

Solving birth-death chains with a cut argument (39:14)

Rather than solving the full balance equations, the lecture uses a cut between adjacent states to argue that upward and downward crossing frequencies must match, giving a simple recursion pi_(i+1) = pi_i * p_i / q_(i+1) that, combined with normalization, yields all the steady-state probabilities.

The constant-rate queueing model (42:20)

Specializing to constant up- and down-transition probabilities with ratio rho = p/q, the lecture shows that rho=1 gives a uniform distribution over states (the symmetric random walk), while for rho<1 and an unbounded state space, the distribution becomes geometric, pi_i = (1-rho)*rho^i, with expected queue length growing large as rho approaches 1.

Before you watch

• Watch the previous lecture on Markov chain basics, transition probabilities, and recurrent versus transient states.
• Be comfortable with geometric series, since the birth-death process solution relies on summing one.
• Review the total probability theorem, used to derive both the n-step recursion and the balance equations.

Check your understanding

1. Why does a single recurrent class with no periodicity guarantee that the initial state is eventually forgotten?
2. How do the balance equations follow from taking the limit of the n-step transition recursion?
3. Why does any self-transition in a chain's diagram rule out periodicity?
4. How does the cut argument for birth-death chains avoid solving the full system of balance equations?
5. What happens to the expected number of customers in the queueing model as the load factor rho approaches 1, and why?