Simple Random Walks on Regular Graphs

Choosing a Neighbor at Each Step

A random walk turns the local structure of a graph into a rule for moving through it. At each step, the walker chooses one of the current vertex’s neighbors uniformly. On a regular graph, every vertex has the same number of choices, so the transition probabilities have a particularly simple matrix form. This lets us calculate the distribution of the walker’s position after a prescribed number of steps.

Graphs here are finite and simple, so there are no loops or multiple edges. The condition \(d\ge 1\) matters: a connected graph with one vertex has degree zero, and the rule “choose a neighbor uniformly” does not define a next step there. We do not add a rule for that exceptional graph.

A walk of length \(t\) is a sequence \(v_0,v_1,\ldots,v_t\) with consecutive vertices adjacent; vertices may repeat. A random walk follows such a walk, with the choice of each next vertex made according to the transition rule. In particular, a trajectory need not be a path, since it may revisit a vertex.

For every vertex \(u\), exactly \(d\) entries in row \(u\) of \(P\) equal \(1/d\), and the other entries are zero. Thus every row sums to \(d(1/d)=1\). The matrix has nonnegative entries and each row is a probability distribution. A matrix with these properties is called row-stochastic.

Distributions and Matrix Powers

Write a probability distribution on \(V\) as a row vector \(\mu\), where \(\mu_u=\Pr(X_0=u)\). The distribution after one step is \(\mu P\): its coordinate at \(v\) is the sum, over all possible starting vertices \(u\), of the probability of starting at \(u\) and then moving to \(v\). Repeating the same rule gives \(\mu P^t\) after \(t\) steps. In particular, if the walk starts at a fixed vertex \(x\), its initial distribution is the row vector with a \(1\) at \(x\) and zeros elsewhere.

Proof. We prove both statements by induction on \(t\). At \(t=0\), there is one length-zero walk from \(u\) to \(u\), none from \(u\) to any other vertex, and \((P^0)_{uv}\) is \(1\) when \(u=v\) and \(0\) otherwise. The claimed probability and count formulas therefore hold.

Now suppose the statements hold for \(t\). Matrix multiplication gives \((P^{t+1})_{uv}=\sum_{w\in V}(P^t)_{uw}P_{wv}\). For each \(w\), the factor \((P^t)_{uw}\) is the probability of being at \(w\) after \(t\) steps, and \(P_{wv}\) is the probability of moving from \(w\) to \(v\) on the next step. The events specifying the position \(w\) at time \(t\) are disjoint and cover all possibilities, so this sum is the probability of being at \(v\) after \(t+1\) steps. For the count statement, each length-\((t+1)\) walk from \(u\) to \(v\) has a unique penultimate vertex \(w\). If \(wv\notin E\), it contributes no walk; if \(wv\in E\), each length-\(t\) walk from \(u\) to \(w\) extends by the edge \(wv\). By the induction hypothesis, the number of such walks is \(d^t(P^t)_{uw}\). Hence the total number is \(\sum_{w:wv\in E}d^t(P^t)_{uw}=d^{t+1}\sum_{w\in V}(P^t)_{uw}P_{wv}=d^{t+1}(P^{t+1})_{uv}\), because \(P_{wv}=1/d\) on an edge and is zero otherwise. Dividing by \(d^{t+1}\) proves the formula. \(\square\)

There is also a direct interpretation for a particular trajectory \(v_0,v_1,\ldots,v_t\): when each consecutive pair is an edge, its probability, starting at \(v_0\), is \((1/d)^t\). The endpoint probability is the sum of these probabilities over all length-\(t\) walks with that endpoint. This sum is important when different trajectories reach the same vertex.

Calculating Short-Step Distributions

Why the Matrix View Is Useful

The transition matrix records all one-step moves at once. Matrix multiplication then combines those moves across time, while the proposition explains what each entry means. This is useful even when a graph has many vertices: instead of listing every possible trajectory, one can compute a row of \(P^t\), or multiply an initial distribution by \(P\) repeatedly.

The regularity assumption is what makes every allowed move have probability \(1/d\). It also makes the probability of any particular length-\(t\) walk equal to \(d^{-t}\), regardless of which vertices the walk visits. If degrees differ, the next-step probability from \(u\) to a neighbor is \(1/\deg(u)\), and different trajectories of the same length need not have equal probabilities. The regular-graph formula \(P=\mathbf{A}(G)/d\) should not be used in that setting.

Common mistake: counting endpoints instead of trajectories. On the 4-cycle above, a two-step walk from \(1\) returns to \(1\) in two different ways. Assigning probability \(1/4\) to the endpoint because there is one endpoint vertex would miss one of those walks. The correct calculation sums the probabilities of both trajectories, giving \(1/4+1/4=1/2\). Conversely, one must not count a trajectory more than once: each walk is specified by its complete vertex sequence, and its probability is the product of the step probabilities along that sequence.

For a fixed starting vertex, every row of \(P^t\) is a probability distribution: its entries are nonnegative, and its sum is \(1\). This also follows from the interpretation in the proposition, since after exactly \(t\) steps the walk must be at one of the vertices of \(V\). When doing a calculation, checking that the entries sum to \(1\) is a quick way to detect arithmetic or matrix-multiplication errors.