Periodicity and Lazy Random Walks

Return Times and Period

A random walk can have a stationary distribution and still fail to settle toward it at each time step. One reason is periodicity: the walk may be forced to alternate between groups of vertices. Bipartite graphs provide the basic example. Allowing the walk to stay at its current vertex with positive probability breaks this alternation, while leaving the stationary distribution unchanged.

Throughout, graphs are finite and simple. We consider a connected graph \(G=(V,E)\) with at least two vertices, so every vertex has positive degree. A transition matrix \(P\) has entries \(P(u,v)\), the probability of moving from \(u\) to \(v\) in one step; each row sums to \(1\). We use row distributions, so the distribution after one step is obtained by multiplying on the right by \(P\). The entry \(P^k(u,v)\) is the probability of being at \(v\) after \(k\) steps when starting at \(u\).

Definition: For a state \(v\), its return-time set is \(\{k\ge1:P^k(v,v)>0\}\). The period of \(v\) is the greatest common divisor of this set. A state with period \(1\) is called aperiodic. A chain is irreducible if every state can reach every other state in some finite number of steps with positive probability.

For the simple random walk on \(G\), the walk moves at each step to a uniformly chosen neighbor, so \(P(u,v)=1/\deg(u)\) when \(uv\in E\), and \(P(u,v)=0\) otherwise. A positive-probability return in \(k\) steps is exactly a closed walk of length \(k\) starting at the state in question: each such walk has positive probability, and a return must follow such a walk.

A graph is bipartite if its vertices can be partitioned into two sets so that every edge joins different sets. Along a walk in a bipartite graph, the part changes at every step. Therefore a walk that returns to its starting vertex must have even length. In a connected graph with at least two vertices, each vertex also has a neighbor, and going to that neighbor and back gives a return in two steps. These observations already indicate why the period is exactly two, rather than merely even.

Period of the Simple Random Walk

Theorem: If \(G\) is connected and has at least two vertices, then every state of its simple random walk has period \(2\) when \(G\) is bipartite, and period \(1\) when \(G\) is not bipartite.

Proof. Fix a vertex \(v\). If \(G\) is bipartite, every closed walk has even length, because each step changes parts. Thus every positive return time at \(v\) is even. Since \(v\) has a neighbor \(u\), the walk \(v,u,v\) has positive probability and length \(2\). The greatest common divisor of a set of even positive integers containing \(2\) is \(2\), so the period of \(v\) is \(2\).

Now suppose \(G\) is not bipartite. We first justify that \(G\) contains an odd cycle. In any connected graph with no odd cycle, choose a root \(r\) and assign each vertex the parity of its distance from \(r\). If an edge \(xy\) joined vertices with distances of the same parity, a shortest path from \(r\) to \(x\), the edge \(xy\), and a shortest path from \(y\) back to \(r\) would form an odd closed walk. Every odd closed walk contains an odd cycle: if a closed walk repeats a vertex other than its coincident first and last vertices, split it at that repetition into two shorter closed walks. Their lengths sum to the original odd length, so one is odd; repeating this reduction eventually gives an odd cycle. Hence no such edge \(xy\) exists, and the two distance-parity classes would be a bipartition. This contradicts the assumption that \(G\) is not bipartite.

Let an odd cycle have length \(q\), and choose a shortest path of length \(a\) from \(v\) to a vertex \(x\) on that cycle. Travel from \(v\) to \(x\), go once around the cycle, and return along the path in reverse. This is a closed walk at \(v\) of length \(2a+q\), which is odd. Also, as before, there is a return of length \(2\). The period of \(v\) divides both \(2\) and the odd integer \(2a+q\), so it is \(1\). Since \(v\) was arbitrary, the conclusion holds at every state. \(\square\)

The walk is irreducible because the graph is connected: a path between any two vertices has positive probability of being followed. The theorem concerns return times, not the stationary distribution. A stationary distribution is a probability row vector \(\pi\) satisfying \(\pi P=\pi\); periodicity can affect how the distribution changes from step to step even when such a vector exists.

Worked Example: Alternation on a 4-Cycle

Let \(G\) have vertex set \(V=\{1,2,3,4\}\) and edge set \(E=\{12,23,34,41\}\). This is a connected bipartite graph, with parts \(\{1,3\}\) and \(\{2,4\}\). Every vertex has degree \(2\), so each available move has probability \(1/2\).

Starting at vertex \(1\), the distribution at time \(0\), then after one, two, and three steps, is as follows. At each step, probability at a vertex is divided equally between its two neighbors:

\begin{aligned} \mu_0&=(1,0,0,0),\\ \mu_1&=(0,\tfrac12,0,\tfrac12),\\ \mu_2&=(\tfrac12,0,\tfrac12,0),\\ \mu_3&=(0,\tfrac12,0,\tfrac12). \end{aligned}

For example, at time \(2\), the probability at \(1\) is \(\tfrac12\cdot\tfrac12+\tfrac12\cdot\tfrac12=\tfrac12\), from the two routes \(1,2,1\) and \(1,4,1\). The probability at \(3\) is also \(\tfrac12\), from \(1,2,3\) and \(1,4,3\). There is no probability at \(2\) or \(4\) at that time. The distribution alternates between the two parts, and the return times are even. A return at time \(2\) has probability \(\tfrac12\), since the two length-two routes back each have probability \((\tfrac12)(\tfrac12)=\tfrac14\).

Check: The distribution at each displayed time sums to \(1\). For instance, at time \(2\), \(\tfrac12+0+\tfrac12+0=1\). The graph is bipartite, and a return at time \(2\) is possible, so its period is \(2\), as the theorem states.

Adding a Holding Probability

Definition: For \(0<\alpha<1\), the \(\alpha\)-lazy random walk has transition matrix \(P_\alpha=\alpha I+(1-\alpha)P\), where \(I\) is the identity matrix and \(P\) is the simple random-walk transition matrix. At each step it stays at its current vertex with probability \(\alpha\), and otherwise makes a simple random-walk move.

The strict bounds on \(\alpha\) matter. If \(\alpha=0\), the walk is not modified and a bipartite graph still gives period \(2\). If \(\alpha=1\), the walk never moves; on a graph with at least two vertices it is not irreducible. When \(0<\alpha<1\), holding creates a one-step return, while every edge still has positive transition probability.

Theorem: For a connected graph with at least two vertices and \(0<\alpha<1\), the \(\alpha\)-lazy random walk is irreducible and every state has period \(1\). If \(\pi\) is stationary for \(P\), then it is stationary for \(P_\alpha\).

Proof. For each edge \(uv\), \(P(u,v)=1/\deg(u)>0\), so \(P_\alpha(u,v)=(1-\alpha)P(u,v)>0\). Every path in the connected graph can therefore still be followed with positive probability, proving irreducibility. Also \(P_\alpha(v,v)\ge\alpha>0\), so a one-step return is possible at every vertex. The return-time set contains \(1\), and its greatest common divisor is therefore \(1\).

For stationarity, use \(\pi P=\pi\) and \(\pi I=\pi\). Then \(\pi P_\alpha=\pi\bigl(\alpha I+(1-\alpha)P\bigr)=\alpha\pi+(1-\alpha)\pi=\pi\). Thus the same distribution remains stationary. \(\square\)

For the simple random walk on an undirected graph, the stationary distribution is proportional to degree. To check the formula, write \(m=|E|\) and set \(\pi(v)=\deg(v)/(2m)\). The sum of all degrees is \(2m\), because each edge contributes one to the degree of each endpoint, so \(\pi\) is a probability distribution. For any vertex \(w\),

\sum_{v\in V}\pi(v)P(v,w) =\sum_{v:\,vw\in E}\frac{\deg(v)}{2m}\frac{1}{\deg(v)} =\frac{\deg(w)}{2m} =\pi(w).

The middle sum has one term \(1/(2m)\) for each neighbor of \(w\), and there are \(\deg(w)\) such neighbors. This verifies stationarity directly. The laziness theorem then shows that this degree-proportional distribution is also stationary for the lazy walk.

Worked Example: Laziness on a Path

Let \(G\) have vertex set \(V=\{1,2,3\}\) and edge set \(E=\{12,23\}\). Its degrees are \(1,2,1\), and \(m=2\). The simple random-walk transition matrix, with rows and columns ordered \(1,2,3\), is

P= \begin{pmatrix} 0&1&0\\ \tfrac12&0&\tfrac12\\ 0&1&0 \end{pmatrix}.

The stationary distribution is \(\pi=(\tfrac14,\tfrac12,\tfrac14)\), since the degree formula gives \((1/4,2/4,1/4)\). Now take \(\alpha=\tfrac13\), so \(1-\alpha=\tfrac23\). Applying \(P_\alpha=\tfrac13 I+\tfrac23P\) gives

P_\alpha= \begin{pmatrix} \tfrac13&\tfrac23&0\\ \tfrac13&\tfrac13&\tfrac13\\ 0&\tfrac23&\tfrac13 \end{pmatrix}.

Each entry comes from scaling the corresponding entry of \(P\) by \(\tfrac23\), then adding \(\tfrac13\) on the diagonal. To check stationarity, compute each coordinate of \(\pi P_\alpha\): the first is \((\tfrac14)(\tfrac13)+(\tfrac12)(\tfrac13)+(\tfrac14)(0)=\tfrac1{12}+\tfrac16=\tfrac14\); the second is \((\tfrac14)(\tfrac23)+(\tfrac12)(\tfrac13)+(\tfrac14)(\tfrac23)=\tfrac16+\tfrac16+\tfrac16=\tfrac12\); the third is \((\tfrac14)(0)+(\tfrac12)(\tfrac13)+(\tfrac14)(\tfrac13)=\tfrac16+\tfrac1{12}=\tfrac14\). Thus \(\pi P_\alpha=\pi\). Each diagonal entry is \(\tfrac13\), so a one-step return is possible at every vertex and the period is \(1\).

Check: The stationary probabilities sum to \(\tfrac14+\tfrac12+\tfrac14=1\). The transition matrix has row sums \(\tfrac13+\tfrac23=1\), \(\tfrac13+\tfrac13+\tfrac13=1\), and \(\tfrac23+\tfrac13=1\), as required.

Worked Example: A Non-Bipartite Walk

Let \(G\) have vertex set \(V=\{1,2,3\}\) and edge set \(E=\{12,23,31\}\), the triangle. Each vertex has degree \(2\), and the graph is not bipartite because its three edges form an odd cycle. Starting at \(1\), a return in two steps has probability \(\tfrac12\): the two possible routes are \(1,2,1\) and \(1,3,1\), each with probability \((\tfrac12)(\tfrac12)=\tfrac14\).

A return in three steps has probability \(\tfrac14\). The only returning routes are \(1,2,3,1\) and \(1,3,2,1\), each with probability \((\tfrac12)^3=\tfrac18\), giving \(\tfrac18+\tfrac18=\tfrac14\). Since the period divides both \(2\) and \(3\), it is \(1\). The stationary distribution is uniform: each vertex has degree \(2\), so each probability is \(2/(2\cdot3)=\tfrac13\).

Check: The two positive return probabilities were computed from all possible routes of the indicated lengths. Since the greatest common divisor of \(2\) and \(3\) is \(1\), the period is \(1\), in agreement with the theorem.

Common Pitfall: Laziness Does Not Make Every Stationary Distribution Uniform

Adding a holding probability preserves the stationary distribution; it does not generally replace it with the uniform distribution. The path example demonstrates the distinction. Its stationary probabilities are \((\tfrac14,\tfrac12,\tfrac14)\), not \((\tfrac13,\tfrac13,\tfrac13)\), because the middle vertex has twice the degree of either endpoint.

For a concrete wrong calculation, start the lazy path walk with the uniform row distribution and use the matrix above. The first coordinate after one step is \((\tfrac13)(\tfrac13)+(\tfrac13)(\tfrac13)+(\tfrac13)(0)=\tfrac29\). The middle coordinate is \((\tfrac13)(\tfrac23)+(\tfrac13)(\tfrac13)+(\tfrac13)(\tfrac23)=\tfrac59\), and the last is \(\tfrac29\). Thus the result is \((\tfrac29,\tfrac59,\tfrac29)\), not the original uniform distribution. The correction is to use the degree-proportional distribution, which the direct multiplication in the example verifies is stationary.

Periodicity and stationarity answer different questions. Period \(1\) means the return times have greatest common divisor \(1\); it does not by itself prove that the distributions at successive times converge. In particular, this tutorial uses no mixing-time estimate: it establishes the return-time obstruction for the simple walk and shows how a holding probability removes that obstruction while preserving stationarity.

Check Your Understanding

Use the definitions and arguments above to answer the following questions.

Why does a simple random walk on a connected bipartite graph with at least two vertices have a return of length \(2\) from every vertex?
For the 4-cycle in the first example, explain why the distribution at every odd time is supported on \(\{2,4\}\) when the walk starts at \(1\).
For the path on three vertices, calculate the degree-proportional stationary distribution and verify its middle coordinate after applying \(P_\alpha\) with \(\alpha=\tfrac13\).
What fails if \(\alpha=1\) on a connected graph with at least two vertices?
Explain why the existence of return times \(2\) and \(5\) at a state implies that its period is \(1\).

Periodicity and Lazy Random Walks

What You'll Learn