1.4. RANDOM WALKS ON GRAPHS 9 Fortunately, a simple modification can repair periodicity problems. Given an arbitrary transition matrix P , let Q = I+P 2 (here I is the |Ω|×|Ω| identity matrix). (One can imagine simulating Q as follows: at each time step, flip a fair coin. If it comes up heads, take a step in P if tails, then stay at the current state.) Since Q(x, x) 0 for all x Ω, the transition matrix Q is aperiodic. We call Q a lazy version of P . It will often be convenient to analyze lazy versions of chains. Example 1.8 (The n-cycle, revisited). Recall random walk on the n-cycle, defined in Example 1.4. For every n 1, random walk on the n-cycle is irreducible. Random walk on any even-length cycle is periodic, since gcd{t : P t(x, x) 0} = 2 (see Figure 1.3). Random walk on an odd-length cycle is aperiodic. The transition matrix Q for lazy random walk on the n-cycle is Q(j, k) = ⎪1/4 ⎪1/4 if k j + 1 (mod n), 1/2 if k j (mod n), if k j 1 (mod n), 0 otherwise. (1.12) Lazy random walk on the n-cycle is both irreducible and aperiodic for every n. Remark 1.9. Establishing that a Markov chain is irreducible is not always trivial see Example B.5, and also Thurston (1990). 1.4. Random Walks on Graphs Random walk on the n-cycle, which is shown in Figure 1.3, is a simple case of an important type of Markov chain. A graph G = (V, E) consists of a vertex set V and an edge set E, where the elements of E are unordered pairs of vertices: E {{x, y} : x, y V, x = y}. We can think of V as a set of dots, where two dots x and y are joined by a line if and only if {x, y} is an element of the edge set. When {x, y} E, we write x y and say that y is a neighbor of x (and also that x is a neighbor of y). The degree deg(x) of a vertex x is the number of neighbors of x. Given a graph G = (V, E), we can define simple random walk on G to be the Markov chain with state space V and transition matrix P (x, y) = 1 deg(x) if y x, 0 otherwise. (1.13) That is to say, when the chain is at vertex x, it examines all the neighbors of x, picks one uniformly at random, and moves to the chosen vertex. Example 1.10. Consider the graph G shown in Figure 1.4. The transition matrix of simple random walk on G is P = 0 1 2 1 2 0 0 1 3 0 1 3 1 3 0 1 4 1 4 0 1 4 1 4 0 1 2 1 2 0 0 0 0 1 0 0 .
Previous Page Next Page