Markov chains

Noah is more likely to win a sparring round after a round he won, so his rounds are not independent. When each step of a random process depends only on the step before, what can be said about where it goes in the long run?

Where you are 4 in Limit theorems

Why this exists

Every limit theorem so far in this course assumed independent trials. At the dojo, Noah wins a sparring round with probability \tfrac35 after a win and only \tfrac14 after a loss. His rounds are dependent, so the law of large numbers and the central limit theorem, as proved, say nothing about them. What his rounds do have is a short memory: the next round depends on the past only through the last one.

A Markov chain is a process with exactly this memory, the simplest dependence that still allows exact computation. Its long run is described by one vector, the stationary distribution; the matrix side is Matrix powers, dynamical systems and steady states.

Definition

In plain words: a Markov chain moves among states in steps, and the chance of each next state depends only on the present state, not on how the chain got there.

Let S be a finite or countable set, the state space. Random variables X_0, X_1, X_2, \dots with values in S form a Markov chain with transition probabilities p_{ij} if, for every n \ge 0, all states i, j and every event H = \{X_{n-1} = i_{n-1}, \dots, X_0 = i_0\} about the earlier states,

P(X_{n+1} = j \mid X_n = i,\, H) = p_{ij}

whenever the condition has positive probability. Two assumptions are packed in: the past before time n does not matter (the Markov property), and p_{ij} does not depend on n (time-homogeneity).

The transition matrix P has p_{ij} in row i, column j. Its entries are \ge 0 and each row adds to 1, since a conditional probability is a probability (Conditioning and Bayes' rule, rigorously, Result 1). Distributions are row vectors: \mu_n(j) = P(X_n = j), and \mu_0 is the initial distribution. The transpose P^{T} is a column-stochastic matrix as in Matrix powers, dynamical systems and steady states.

A stationary distribution is a row vector \pi with \pi_j \ge 0, \sum_j \pi_j = 1 and \pi P = \pi, that is, \sum_i \pi_i p_{ij} = \pi_j for every j.

The chain is irreducible if for all i, j there is an n \ge 1 with (P^n)_{ij} > 0, and regular if one power P^N has every entry positive; a regular chain is irreducible. The hitting time of j is T_j = \min\{n \ge 1 : X_n = j\} (\infty if there is none), the return time when X_0 = j, and m_{ij} = E(T_j \mid X_0 = i).

Intuition

Picture a crowd of copies of the chain, a fraction \pi_i in each state i. In one step the fraction arriving in j is \sum_i \pi_i p_{ij}, and \pi P = \pi says this inflow is again \pi_j. One copy followed for a long time spends a fraction \pi_j of its steps in j (Result 6), so it returns to j on average every \displaystyle \frac{1}{\pi_j} steps (Result 4). Whether P(X_n = j) itself settles is a separate question (Result 5 and Boundaries).

Results

Result 1 (paths). (a) For all states i_0, \dots, i_n,

\begin{aligned} &P(X_0 = i_0, X_1 = i_1, \dots, X_n = i_n) \\ &\quad = \mu_0(i_0)\, p_{i_0 i_1} p_{i_1 i_2} \cdots p_{i_{n-1} i_n}. \end{aligned}

(b) Let A be determined by X_0, \dots, X_m (a union of events \{X_0 = i_0, \dots, X_m = i_m\}), with P(A \cap \{X_m = i\}) > 0. Then for all states j_1, \dots, j_k,

\begin{aligned} &P(X_{m+1} = j_1, \dots, X_{m+k} = j_k \mid A \cap \{X_m = i\}) \\ &\quad = p_{i j_1} p_{j_1 j_2} \cdots p_{j_{k-1} j_k}. \end{aligned}

Given the present state i, the future runs as a fresh chain started at i, whatever the past.

Result 2 (n-step probabilities). If P(X_m = i) > 0, then P(X_{m+n} = j \mid X_m = i) = (P^n)_{ij}. Hence \mu_n = \mu_0 P^n, and P^{m+n} = P^m P^n gives the Chapman-Kolmogorov equations (P^{m+n})_{ij} = \sum_k (P^m)_{ik} (P^n)_{kj}.

Result 3 (stationary distributions). (a) If \mu_0 = \pi is stationary, then \mu_n = \pi for every n. (b) If S is finite and \mu_n(j) \to \nu_j for every j, then \nu is stationary.

Result 4 (return times). Let S be finite and the chain irreducible. Then every m_{ij} is finite, the first-step equations

m_{ij} = 1 + \sum_{k \ne j} p_{ik}\, m_{kj}

hold, and every stationary distribution has \pi_j = \dfrac{1}{m_{jj}}. So there is at most one, and its entries are positive.

Result 5 (existence and convergence, stated without proof). Let S be finite. (a) An irreducible chain has a stationary distribution. (b) If the chain is regular, then (P^n)_{ij} \to \pi_j for all i, j, so \mu_n \to \pi whatever \mu_0.

Result 6 (long-run fractions). Let S be finite and the chain regular, and let N_j(n) count the steps k = 1, \dots, n with X_k = j. For every initial distribution and every \varepsilon > 0,

\lim_{n \to \infty} P\left(\left|\frac{N_j(n)}{n} - \pi_j\right| \ge \varepsilon\right) = 0.
Why it is true

Result 1. (a) By the multiplication rule (Conditioning and Bayes' rule, rigorously, Result 2), the probability is \mu_0(i_0) times the factors P(X_k = i_k \mid X_{k-1} = i_{k-1}, \dots, X_0 = i_0), each p_{i_{k-1} i_k} by the definition. If some P(X_0 = i_0, \dots, X_k = i_k) is 0, take the least such k: the left side is 0, and so is the right, whose first k + 1 factors multiply to that probability by the case just proved.

(b) A \cap \{X_m = i\} is the disjoint union of the path events in A ending at i. By (a), such a path followed by j_1, \dots, j_k has the path’s probability times p_{i j_1} \cdots p_{j_{k-1} j_k}. Add over the paths and divide by P(A \cap \{X_m = i\}).

Result 2. By 1(b) with A = \{X_m = i\}, P(X_{m+n} = j \mid X_m = i) is the sum of p_{i j_1} p_{j_1 j_2} \cdots p_{j_{n-1} j} over j_1, \dots, j_{n-1}, which is the (i, j) entry of P^n written out (for countable S the terms are nonnegative, so order does not matter). The law of total probability (Conditioning and Bayes' rule, rigorously, Result 3) over X_0 gives \mu_n = \mu_0 P^n. Chapman-Kolmogorov is associativity of matrix multiplication.

Result 3. (a) \mu_n = \pi P^n = \pi. (b) Each \nu_j \ge 0 and \sum_j \nu_j = \lim_n \sum_j \mu_n(j) = 1; letting n \to \infty in the finite sum \mu_{n+1}(j) = \sum_i \mu_n(i)\, p_{ij} gives \nu P = \nu.

Result 4. Finite means. Fix j. Each state a has an n_a \ge 1 with (P^{n_a})_{aj} > 0; let N = \max_a n_a and \delta = \min_a (P^{n_a})_{aj} > 0. From every state the chain visits j within N steps with probability at least \delta. Splitting \{T_j > kN\}, which is determined by X_0, \dots, X_{kN}, by the value of X_{kN} and applying 1(b) to each piece,

\begin{aligned} &P(T_j > (k + 1)N \mid X_0 = i) \\ &\quad \le (1 - \delta)\, P(T_j > kN \mid X_0 = i), \end{aligned}

so P(T_j > kN \mid X_0 = i) \le (1 - \delta)^k and T_j is finite with probability 1. For T with values 1, 2, \dots, E(T) = \sum_n n P(T = n) = \sum_{t \ge 0} P(T > t), a reordering of nonnegative terms. The N terms with kN \le t < (k + 1)N are each at most (1 - \delta)^k, so \displaystyle m_{ij} \le N \sum_k (1 - \delta)^k = \frac{N}{\delta}.

First-step equations. Given X_0 = i, condition on X_1, as in Example 7 of Conditional expectation. On \{X_1 = j\}, T_j = 1. On \{X_1 = k\}, k \ne j, 1(b) says X_1, X_2, \dots runs as the chain from k, so T_j has conditional mean 1 + m_{kj}. The tower rule (Conditional expectation, Result 1) gives m_{ij} = p_{ij} + \sum_{k \ne j} p_{ik}(1 + m_{kj}), the stated equation since row i adds to 1.

The formula for \pi. Multiply the equation by \pi_i and add over i. As \sum_i \pi_i = 1 and \sum_i \pi_i p_{ik} = \pi_k,

\sum_i \pi_i\, m_{ij} = 1 + \sum_{k \ne j} \pi_k\, m_{kj}.

All terms are finite and the sums agree except for i = j on the left, so \pi_j m_{jj} = 1.

Result 5 is not proved here. Part (a) is part of the Perron-Frobenius theorem: 1 is always an eigenvalue (Matrix powers, dynamical systems and steady states), and the content of (a) is that some solution of \pi P = \pi has no negative entries. Part (b) is proved in Section 11.4 of Grinstead and Snell’s Introduction to Probability, and (a) is derived from it in Section 11.3. Example 6 proves (b) for one chain.

Result 6. Let I_k = \mathbf{1}_{\{X_k = j\}}, so \displaystyle \frac{N_j(n)}{n} = \frac1n \sum_{k=1}^n I_k, and fix \eta > 0. Result 5(b) gives an M with |(P^m)_{aj} - \pi_j| < \eta for all m \ge M and all a, and P(X_m = j) = \sum_a \mu_0(a) (P^m)_{aj}, an average of these, is then within \eta of \pi_j too.

Mean. By Expectation, linearity and indicators, Results 2 and 3, \displaystyle E\big(\frac{N_j(n)}{n}\big) is the average of the P(X_k = j), all but M of them within \eta of \pi_j, so it is within \displaystyle \eta + \frac{M}{n} of \pi_j.

Variance. For k < l, Result 2 gives E(I_k I_l) = P(X_k = j) (P^{l-k})_{jj}, so

\begin{aligned} &\operatorname{Cov}(I_k, I_l) \\ &\quad = P(X_k = j)\big((P^{l-k})_{jj} - P(X_l = j)\big). \end{aligned}

When l - k \ge M, both numbers in the bracket are within \eta of \pi_j, so |\operatorname{Cov}(I_k, I_l)| < 2\eta. The fewer than 2Mn ordered pairs with |k - l| < M have covariances of size at most 1. By Variance and covariance, Result 4,

\begin{aligned} \operatorname{Var}\Big(\frac{N_j(n)}{n}\Big) &= \frac{1}{n^2} \sum_{k, l} \operatorname{Cov}(I_k, I_l) \\ &\le \frac{2M}{n} + 2\eta. \end{aligned}

As \eta is arbitrary, the mean tends to \pi_j and the variance to 0, and the mean-square test, Result 1 of The law of large numbers, gives the limit.

Worked examples

Example 1

Noah’s next rounds

Noah’s rounds form a Markov chain on \{W, L\} (win, loss) with p_{WW} = \tfrac35 and p_{LW} = \tfrac14. He lost round 0. Find the probability that he wins rounds 1 and 2 and loses round 3, and find P(X_2 = W \mid X_0 = L).

Solution

The rows add to 1, so in the order W, L

P = \begin{bmatrix} \tfrac35 & \tfrac25 \\[2pt] \tfrac14 & \tfrac34 \end{bmatrix}.

By Result 1(b), the path L, W, W, L has probability p_{LW}\, p_{WW}\, p_{WL} = \tfrac14 \cdot \tfrac35 \cdot \tfrac25 = \tfrac{3}{50}. By Result 2, P(X_2 = W \mid X_0 = L) = (P^2)_{LW}, a sum over the middle round:

\begin{aligned} (P^2)_{LW} &= p_{LW}\, p_{WW} + p_{LL}\, p_{LW} \\ &= \tfrac{3}{20} + \tfrac{3}{16} = \tfrac{27}{80}. \end{aligned}
Example 2

Jenny’s opening drill

Jenny opens each class with kata (K), pad work (D) or light sparring (S), following the chain of Figure 1 (order K, D, S):

P = \begin{bmatrix} 0 & \tfrac12 & \tfrac12 \\[2pt] \tfrac14 & \tfrac14 & \tfrac12 \\[2pt] \tfrac12 & \tfrac14 & \tfrac14 \end{bmatrix}.

Find the stationary distribution, show the chain is regular, and describe the long run.

K D S
\displaystyle \frac{1}{2}
\displaystyle \frac{1}{4}
\displaystyle \frac{1}{2}
\displaystyle \frac{1}{2}
\displaystyle \frac{1}{2}
\displaystyle \frac{1}{4}
\displaystyle \frac{1}{4}
\displaystyle \frac{1}{4}
Figure 1The transition diagram of Jenny’s opening drill in Example 2. Each arrow carries a one-step probability p_{ij}, and the arrows leaving a state add to 1. There is no loop at K, since kata is never repeated.
Solution

Write \pi = (x, y, z). Column by column, \pi P = \pi reads

\begin{aligned} x &= \tfrac14 y + \tfrac12 z, \\ y &= \tfrac12 x + \tfrac14 y + \tfrac14 z, \\ z &= \tfrac12 x + \tfrac12 y + \tfrac14 z. \end{aligned}

As the rows of P add to 1, the equations sum to an identity, so x + y + z = 1 replaces one. The first two give 4x = y + 2z and 3y = 2x + z, so z = 3y - 2x and 8x = 7y. Then y = \tfrac87 x, z = \tfrac{10}{7} x, and the total \tfrac{25}{7} x = 1 gives

\pi = \left(\tfrac{7}{25}, \tfrac{8}{25}, \tfrac25\right).

Row K of P^2 is \tfrac12 row D plus \tfrac12 row S, and so on:

P^2 = \begin{bmatrix} \tfrac38 & \tfrac14 & \tfrac38 \\[2pt] \tfrac{5}{16} & \tfrac{5}{16} & \tfrac38 \\[2pt] \tfrac{3}{16} & \tfrac38 & \tfrac{7}{16} \end{bmatrix}.

Every entry is positive, so the chain is regular although p_{KK} = 0, and \pi is its only stationary distribution (Result 4). The chance that class n opens with sparring tends to \tfrac25 whatever the first drill (Result 5(b)), and so does the fraction of classes opening with sparring, in probability (Result 6).

Example 3

Waiting for kata

In Example 2, find the mean number of classes until Jenny next opens with kata, from each drill, and check Result 4.

Solution

Write m_K, m_D, m_S for m_{KK}, m_{DK}, m_{SK}, finite by Result 4. The first-step equations with j = K leave out the terms with k = K:

\begin{aligned} m_D &= 1 + \tfrac14 m_D + \tfrac12 m_S, \\ m_S &= 1 + \tfrac14 m_D + \tfrac14 m_S. \end{aligned}

So 3m_D = 4 + 2m_S and 3m_S = 4 + m_D. Substituting m_D = 3m_S - 4 gives 7m_S = 16: m_S = \tfrac{16}{7} \approx 2.29 and m_D = \tfrac{20}{7} \approx 2.86. Then

\begin{aligned} m_K &= 1 + \tfrac12 m_D + \tfrac12 m_S \\ &= 1 + \tfrac{10}{7} + \tfrac87 = \tfrac{25}{7}, \end{aligned}

and \displaystyle \frac{1}{m_K} = \tfrac{7}{25} = \pi_K, as Result 4 says.

Example 4

Detailed balance on the challenge ladder

Prove that if a distribution \pi satisfies \pi_i\, p_{ij} = \pi_j\, p_{ji} for all i, j (detailed balance), then \pi is stationary. Apply it to the dojo’s challenge ladder, places 1 (bottom) to 4 (top): each week Noah moves up one place with probability \tfrac13 unless at the top, down one with probability \tfrac16 unless at the bottom, and otherwise stays. Find his long-run share of weeks at the top and the mean time between his visits to the bottom.

Solution

For each j, detailed balance and then the sum of row j give

\begin{aligned} (\pi P)_j &= \sum_i \pi_i\, p_{ij} = \sum_i \pi_j\, p_{ji} \\ &= \pi_j \sum_i p_{ji} = \pi_j. \end{aligned}

So \pi is stationary.

On the ladder p_{ij} = p_{ji} = 0 when |i - j| \ge 2, so detailed balance asks only \tfrac13 \pi_i = \tfrac16 \pi_{i+1}, that is, \pi_{i+1} = 2\pi_i. With total 1,

\pi = \left(\tfrac{1}{15}, \tfrac{2}{15}, \tfrac{4}{15}, \tfrac{8}{15}\right).

Each place can be held for a week and any two are at most 3 moves apart, so P^3 is positive and the chain is regular. By Result 6 his share of weeks at the top tends to \tfrac{8}{15}, and by Result 4 the mean time between visits to the bottom is \displaystyle \frac{1}{\pi_1} = 15 weeks.

Example 5

First to lead by two

Jenny and Noah spar until one leads by two points. Each exchange is Jenny’s with probability \tfrac35, independently. Her lead X_n is a chain on \{-2, -1, 0, 1, 2\} that stays at \pm 2 (Figure 2). From a level start, find the probability that Jenny wins and the mean number T of exchanges, and find every stationary distribution.

−2 −1 0 1 2
\displaystyle \frac{3}{5}
\displaystyle \frac{2}{5}
\displaystyle \frac{3}{5}
\displaystyle \frac{2}{5}
\displaystyle \frac{3}{5}
\displaystyle \frac{2}{5}
1 1
Figure 2The chain of Jenny’s lead in Example 5. The states -2 and 2 are absorbing; once there, the chain stays.
Solution

Let h_i be the probability of reaching 2 before -2 from i, with h_2 = 1 and h_{-2} = 0. Conditioning on the first exchange (the law of total probability with Result 1(b)),

\begin{aligned} h_1 &= \tfrac35 + \tfrac25 h_0, \qquad h_{-1} = \tfrac35 h_0, \\ h_0 &= \tfrac35 h_1 + \tfrac25 h_{-1}. \end{aligned}

So h_0 = \tfrac{9}{25} + \tfrac{12}{25} h_0 and h_0 = \tfrac{9}{13}. The chain is not irreducible, so Result 4 does not apply. Instead, from 0 two exchanges end the bout with probability \tfrac{9}{25} + \tfrac{4}{25} = \tfrac{13}{25} and otherwise return to 0, so by Result 1(b) T is twice a \operatorname{Geometric}(\tfrac{13}{25}) count and E(T) = \tfrac{50}{13} \approx 3.85.

For stationarity, the only flow into 1 is from 0, so \pi_1 = \tfrac35 \pi_0, and likewise \pi_{-1} = \tfrac25 \pi_0. Then \pi_0 = \tfrac35 \pi_{-1} + \tfrac25 \pi_1 = \tfrac{12}{25} \pi_0 forces \pi_0 = \pi_{\pm 1} = 0, while the equations at \pm 2 hold for any weights. The stationary distributions are (1 - t, 0, 0, 0, t) for 0 \le t \le 1. From a level start \mu_n \to (\tfrac{4}{13}, 0, 0, 0, \tfrac{9}{13}), the one with t = \tfrac{9}{13} (Result 3(b)); another start leads to another.

Example 6

Wins in a hundred rounds

For Noah’s chain in Example 1, find P(X_n = W \mid X_0 = L) for every n, and the expected number of wins in rounds 1 to 100 after a loss in round 0.

Solution

Detailed balance \tfrac25 \pi_W = \tfrac14 \pi_L gives \pi = (\tfrac{5}{13}, \tfrac{8}{13}), stationary by Example 4. A left eigenvector does the rest:

(1, -1)P = \left(\tfrac35 - \tfrac14,\ \tfrac25 - \tfrac34\right) = \tfrac{7}{20}(1, -1).

As \mu_0 = (0, 1) = \pi - \tfrac{5}{13}(1, -1), Results 2 and 3(a) give \mu_n = \pi - \tfrac{5}{13}(\tfrac{7}{20})^n (1, -1), so

P(X_n = W \mid X_0 = L) = \tfrac{5}{13}\left(1 - \left(\tfrac{7}{20}\right)^n\right).

For n = 2 this is \tfrac{5}{13} \cdot \tfrac{351}{400} = \tfrac{27}{80}, as in Example 1. The gap to \pi_W shrinks by the factor \tfrac{7}{20} = 1 - \tfrac25 - \tfrac14 each round (Figure 3), the second eigenvalue in the two-place formula of Matrix powers, dynamical systems and steady states.

0 2 4 6 8 n 0 0.5 1
\displaystyle \frac{5}{13}
after a win after a loss
Figure 3Example 6. The probability P(X_n = W) that Noah wins round n, after an opening win (upper) and after an opening loss (lower). Each gap to \pi_W = \tfrac{5}{13} (dashed) is multiplied by \tfrac{7}{20} every round.

By linearity, E(N_W(100)) = \sum_{k=1}^{100} P(X_k = W), and with \lambda = \tfrac{7}{20}, \displaystyle \frac{\lambda}{1 - \lambda} = \tfrac{7}{13}, the geometric sum gives

\begin{aligned} E(N_W(100)) &= \tfrac{500}{13} - \tfrac{35}{169}\left(1 - \left(\tfrac{7}{20}\right)^{100}\right) \\ &\approx 38.25, \end{aligned}

where (\tfrac{7}{20})^{100} < 10^{-45}. The opening loss costs Noah only about \tfrac{35}{169} \approx 0.21 wins in expectation, and by Result 6 his fraction of wins tends to \tfrac{5}{13} \approx 0.3846.

Boundaries

The Markov property is a modeling assumption. A process whose next step depends on its last two is not a Markov chain (Exercise 7), but its pairs of consecutive states form one.

Without irreducibility, uniqueness can fail. The bout of Example 5 has a stationary distribution for every t in [0, 1].

Convergence needs more than irreducibility. For P = \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}, \pi = (\tfrac12, \tfrac12) is the only stationary distribution, but P^n alternates between I and P. Returns happen only at even times: the chain has period 2. A finite irreducible chain is regular exactly when the greatest common divisor of its return times is 1; this, and Result 6 for every finite irreducible chain, hold with proofs beyond this lesson.

Infinite state spaces. The simple random walk on the integers, steps \pm 1 with probability \tfrac12 each, is irreducible but has no stationary distribution. Its equation \pi_j = \tfrac12 \pi_{j-1} + \tfrac12 \pi_{j+1} makes \pi an arithmetic sequence, which, being nonnegative on all integers, is constant, and a constant cannot add to 1.

Where this goes next

Time averages along a regular chain obey a central limit theorem too. Markov chain Monte Carlo samples from a complicated \pi by running a chain with \pi in detailed balance. For large chains, P^n comes from Diagonalization.

Exercises

Paths and n-step probabilities

  1. Jenny opens each round in orthodox (O) or southpaw (U) stance, a chain with p_{OO} = \tfrac45 and p_{UO} = \tfrac12. Find P(X_1 = O, X_2 = U, X_3 = U \mid X_0 = O), (P^2)_{OU} and the stationary distribution.
  2. For the chain of Exercise 1, find P(X_n = U \mid X_0 = O) for every n, and the expected number of southpaw rounds among rounds 1 to 50 after an orthodox round 0.
  3. Noah moves among three mats with P = \begin{bmatrix} \tfrac12 & \tfrac12 & 0 \\[2pt] \tfrac13 & 0 & \tfrac23 \\[2pt] 0 & \tfrac12 & \tfrac12 \end{bmatrix}. Find row 1 of P^2. If \mu_0 is uniform, find \mu_1 and P(X_0 = 2 \mid X_1 = 3).

Stationary distributions and the long run

  1. For the mats of Exercise 3, find the stationary distribution, show that P^2 is positive, and find the mean return times. About how many of 900 steps does Noah spend on mat 3?
  2. For the mats of Exercise 3, find m_{13} and m_{23} from the first-step equations, and use them to check m_{33}.
  3. From the heavy bag (1) or the speed bag (3) Noah always goes to the mirror (2), and from the mirror to either bag with probability \tfrac12. Find the stationary distribution, (P^n)_{11} for every n \ge 1, and the mean return times. Is the chain regular?
  4. Jenny wins a round with probability \tfrac34 after two wins, \tfrac12 after a loss then a win, \tfrac13 after a win then a loss, \tfrac14 after two losses. With states the pairs (previous, current) in the order WW, WL, LW, LL, write the transition matrix, find the stationary distribution and her long-run fraction of wins. For the stationary chain, find the probability that she wins a round given that she won the one before, and compare it with \tfrac34.

Absorption

  1. Noah’s belt grading has three stages. Each attempt at a stage passes with probability \tfrac23, independently. Passing stage 1 or 2 moves him up, and passing stage 3 earns the belt. Failing stage 1 ends the grading without the belt; failing stage 2 or 3 sends him back a stage. From stage 1, find the probability that he earns the belt and the mean number of attempts.
  2. Jenny and Noah, evenly matched, spar until one leads by three points, each exchange won by either with probability \tfrac12. Find the mean number of exchanges from leads of 0, 1 and 2, and Jenny’s chance of winning from a lead of 1.

Proofs

  1. Let n \ge 1 and P(X_n = b) > 0. Prove that, given X_n = b, the events \{X_{n-1} = a\} and \{X_{n+1} = c\} are independent.
  2. Prove that every stationary distribution of a chain with two states satisfies detailed balance.
  3. Let S have r states and the columns of P also add to 1. Prove that the uniform distribution is stationary, and that if the chain is irreducible, every mean return time is r.
  4. Let a chain on r \ge 2 states be irreducible with p_{kk} > 0 for some k. Prove that P^{2(r-1)} is positive.
  5. Refute: “every stationary distribution satisfies detailed balance.”
  6. Prove that a stationary \pi of P is stationary for \tfrac12(I + P).
Answers
  1. P = \begin{bmatrix} \tfrac45 & \tfrac15 \\[2pt] \tfrac12 & \tfrac12 \end{bmatrix}. The path has probability \tfrac45 \cdot \tfrac15 \cdot \tfrac12 = \tfrac{2}{25}, and (P^2)_{OU} = \tfrac45 \cdot \tfrac15 + \tfrac15 \cdot \tfrac12 = \tfrac{13}{50}. Detailed balance \tfrac15 \pi_O = \tfrac12 \pi_U gives \pi = (\tfrac57, \tfrac27) (Example 4).
  2. (1, -1)P = \tfrac{3}{10}(1, -1) and (1, 0) = \pi + \tfrac27 (1, -1), so P(X_n = U \mid X_0 = O) = \tfrac27\big(1 - (\tfrac{3}{10})^n\big). Summing, the expected count is \tfrac{100}{7} - \tfrac{6}{49}\big(1 - (\tfrac{3}{10})^{50}\big) \approx 14.16.
  3. Row 1 of P^2 is \tfrac12 row 1 plus \tfrac12 row 2: (\tfrac{5}{12}, \tfrac14, \tfrac13). \mu_1 is \tfrac13 times the column sums, (\tfrac{5}{18}, \tfrac13, \tfrac{7}{18}). By Bayes’ rule, \displaystyle P(X_0 = 2 \mid X_1 = 3) = \frac{\frac13 \cdot \frac23}{\frac{7}{18}} = \tfrac47.
  4. Detailed balance, \tfrac12 \pi_1 = \tfrac13 \pi_2 and \tfrac23 \pi_2 = \tfrac12 \pi_3, gives \pi = (\tfrac29, \tfrac13, \tfrac49). Rows 2 and 3 of P^2 are (\tfrac16, \tfrac12, \tfrac13) and (\tfrac16, \tfrac14, \tfrac{7}{12}), so with row 1 all entries are positive. By Result 4 the mean return times are \tfrac92, 3 and \tfrac94. By Result 6, about 400 steps.
  5. m_{13} = 1 + \tfrac12 m_{13} + \tfrac12 m_{23} and m_{23} = 1 + \tfrac13 m_{13} give m_{13} = \tfrac92 and m_{23} = \tfrac52. Then \displaystyle m_{33} = 1 + \tfrac12 m_{23} = \tfrac94 = \frac{1}{\pi_3}.
  6. Balance gives \pi_1 = \pi_3 = \tfrac12 \pi_2, so \pi = (\tfrac14, \tfrac12, \tfrac14). From 1 the chain is at 2 after each odd number of steps and at 1 or 3, equally likely, after each even number, so (P^n)_{11} is 0 for odd n and \tfrac12 for even n \ge 2. By Result 4 the mean return times are 4, 2, 4. Not regular: (P^n)_{11} = 0 for odd n and (P^n)_{12} = 0 for even n.
  7. The rows are WW: (\tfrac34, \tfrac14, 0, 0); WL: (0, 0, \tfrac13, \tfrac23); LW: (\tfrac12, \tfrac12, 0, 0); LL: (0, 0, \tfrac14, \tfrac34). Then \pi P = \pi gives \pi_{WW} = 2\pi_{LW}, \pi_{WL} = \pi_{LW}, \pi_{LL} = \tfrac83 \pi_{LW}, so \pi = (\tfrac{3}{10}, \tfrac{3}{20}, \tfrac{3}{20}, \tfrac25). The chain is irreducible with p_{WW,WW} > 0, so regular (Exercise 13), and by Result 6 the fraction of wins tends to \pi_{WW} + \pi_{LW} = \tfrac{9}{20}. Stationary, \displaystyle P(\text{win} \mid \text{won before}) = \frac{3/10}{9/20} = \tfrac23, but \tfrac34 given two wins before: the win and loss sequence is not a Markov chain.
  8. With h_i the chance of the belt from stage i: h_1 = \tfrac23 h_2, h_2 = \tfrac23 h_3 + \tfrac13 h_1, h_3 = \tfrac23 + \tfrac13 h_2, so h_3 = \tfrac{14}{15}, h_2 = \tfrac45 and h_1 = \tfrac{8}{15}. For the attempts, e_1 = 1 + \tfrac23 e_2, e_2 = 1 + \tfrac23 e_3 + \tfrac13 e_1, e_3 = 1 + \tfrac13 e_2 give e_2 = \tfrac{18}{5} and e_1 = \tfrac{17}{5}. The means are finite as in the proof of Result 4: from any stage, three passes end the grading.
  9. The equations e_{\pm 3} = 0, e_i = 1 + \tfrac12 e_{i-1} + \tfrac12 e_{i+1} make the differences e_{i+1} - e_i fall by 2 each step, so they have one solution, e_i = 9 - i^2: 9, 8 and 5 exchanges. Likewise \displaystyle h_i = \frac{i + 3}{6}, and h_1 = \tfrac23. Means are finite as in Exercise 8.
  10. Write B = \{X_n = b\}, E = \{X_{n-1} = a\}, F = \{X_{n+1} = c\}. If P(E \cap B) = 0, both sides are 0. Otherwise Result 1(b) with A = E at time n gives P(F \mid E \cap B) = p_{bc}. Multiplying by P(E \cap B) and dividing by P(B) gives P(E \cap F \mid B) = P(E \mid B)\, p_{bc}, and p_{bc} = P(F \mid B) by Result 2.
  11. With states 1 and 2, the stationary equation for state 1 is \pi_1 = \pi_1 p_{11} + \pi_2 p_{21}. Since 1 - p_{11} = p_{12}, it says \pi_1 p_{12} = \pi_2 p_{21}, detailed balance for the only pair of different states; for i = j it is trivial.
  12. (\pi P)_j = \sum_i \tfrac1r p_{ij} = \tfrac1r, as column j adds to 1. If the chain is irreducible, Result 4 gives \displaystyle m_{jj} = \frac{1}{\pi_j} = r.
  13. Fix i, j. A shortest positive-probability path from i to k repeats no state (a repeat could be cut out), so its length a is at most r - 1, with a = 0 if i = k; likewise a path from k to j of length b \le r - 1. Follow the first, stay at k for 2(r - 1) - a - b \ge 0 steps, then follow the second. This path of length 2(r - 1) has positive probability by Result 1(a), and by Result 2 (P^{2(r-1)})_{ij} is at least that probability.
  14. Take 1 \to 2 \to 3 \to 1 with certainty. Each column has one entry 1, so \pi = (\tfrac13, \tfrac13, \tfrac13) is stationary (Exercise 12), but \pi_1 p_{12} = \tfrac13 while \pi_2 p_{21} = 0.
  15. \pi \cdot \tfrac12(I + P) = \tfrac12 \pi + \tfrac12 \pi P = \pi.
math.wiki · CC-BY-SA-4.0