1.6. REVERSIBILITY AND TIME REVERSALS 15 In other words, if a chain (Xt) satisfies (1.30) and has stationary initial distribu- tion, then the distribution of (X0, X1, . . . , Xn) is the same as the distribution of (Xn, Xn−1, . . . , X0). For this reason, a chain satisfying (1.30) is called reversible. Example 1.20. Consider the simple random walk on a graph G. We saw in Example 1.12 that the distribution π(x) = deg(x)/2|E| is stationary. Since π(x)P (x, y) = deg(x) 2|E| 1{x∼y} deg(x) = 1{x∼y} 2|E| = π(y)P (x, y), the chain is reversible. (Note: here the notation 1A represents the indicator function of a set A, for which 1A(a) = 1 if and only if a ∈ A otherwise 1A(a) = 0.) Example 1.21. Consider the biased random walk on the n-cycle: a parti- cle moves clockwise with probability p and moves counterclockwise with probability q = 1 − p. The stationary distribution remains uniform: if π(k) = 1/n, then j∈Zn π(j)P (j, k) = π(k − 1)p + π(k + 1)q = 1 n , whence π is the stationary distribution. However, if p = 1/2, then π(k)P (k, k + 1) = p n = q n = π(k + 1)P (k + 1, k). The time reversal of an irreducible Markov chain with transition matrix P and stationary distribution π is the chain with matrix P (x, y) := π(y)P (y, x) π(x) . (1.33) The stationary equation π = πP implies that P is a stochastic matrix. Proposition 1.22 shows that the terminology “time reversal” is deserved. Proposition 1.22. Let (Xt) be an irreducible Markov chain with transition matrix P and stationary distribution π. Write (Xt) for the time-reversed chain with transition matrix P . Then π is stationary for P , and for any x0, . . . , xt ∈ Ω we have Pπ{X0 = x0, . . . , Xt = xt} = Pπ{X0 = xt, . . . , Xt = x0}. Proof. To check that π is stationary for P , we simply compute y∈Ω π(y)P (y, x) = y∈Ω π(y) π(x)P (x, y) π(y) = π(x). To show the probabilities of the two trajectories are equal, note that Pπ{X0 = x0, . . . , Xn = xn} = π(x0)P (x0, x1)P (x1, x2) ··· P (xn−1, xn) = π(xn)P (xn, xn−1) ··· P (x2, x1)P (x1, x0) = Pπ{ ˆ X 0 = xn, . . . , ˆ X n = x0}, since P (xi−1, xi) = π(xi)P (xi, xi−1)/π(xi−1) for each i. Observe that if a chain with transition matrix P is reversible, then P = P .

Purchased from American Mathematical Society for the exclusive use of nofirst nolast (email unknown) Copyright no copyright American Mathematical Society. Duplication prohibited. Please report unauthorized use to cust-serv@ams.org. Thank You! Your purchase supports the AMS' mission, programs, and services for the mathematical community.