Chapter 14 · Special Topics
Random Walks and Cover Times
Hitting times as linear equations, commute-time bounds via effective resistance, and the walk-based algorithms that actually get used.
#Hitting and commute times
A walk on G that at each step chooses a uniformly random neighbour of the current vertex. Huv = hitting time = expected steps to reach v from u; Cuv = Huv + Hvu = commute time; the cover time is the expectation of the first time all vertices have been visited.
#Hitting times solve a linear system
For fixed target v: Hvv = 0 and
On a connected graph this system has a unique solution.
First-step analysis: one step is taken (the +1), then the walk is at a uniformly random neighbour, and the expectation from there is the average — the Markov property makes the future independent of the past. Uniqueness: the coefficient matrix is I - P' where P' is the transition matrix with row v removed; because the walk reaches v with probability 1 (finite irreducible chain), the spectral radius of P' is < 1, so I - P' is invertible. ∎
#Commute time is effective resistance
where Reff is the resistance between u and v when every edge is a 1 Ω resistor.
Inject one unit of current at u and extract it at v; the potential φ then satisfies Lφ = mathbf 1u - mathbf 1v (Kirchhoff) and φ(u)-φ(v) = Reff. The proof identifies the hitting-time difference with this potential. Define g(x) = Hxu - Hxv. Subtracting the two hitting-time equations cancels the +1 terms, so g is harmonic at every x ∉ {u,v}: g(x) is the average of g over its neighbours. The unit-current potential φ is harmonic at the same vertices, and both are determined by their values at u,v (uniqueness of harmonic functions with given boundary values, by the maximum principle). Comparing the edge differences: the walk crosses edge xy (in the direction away from v) with rate proportional to (1)/(deg) times the stationary mass (deg(x))/(2m), so the "flow" 2m ∇ g is a unit flow from u to v; energy minimality then gives g(u)-g(v) = 2m (φ(u)-φ(v)) = 2m Reff. Since Cuv = Huv+Hvu = g(u) - g(v) with this g, the identity follows. ∎
#Values you can quote
Consequences you can quote (with the resistance computed by hand)
- path on n vertices: Reff = n-1 ohms in series ⇒ C = Θ(n2) ⇒ hitting time from end to end is Θ(n2) (the classic gambler's-ruin computation),
- complete graph Kn: Reff = 2/n (direct edge 1 Ω in parallel with the n-2 two-edge paths, each of 2 Ω, giving (1 + tfrac{n-2}{2})-1 = tfrac{2}{n}) ⇒ Cuv = 2m R = n(n-1)·tfrac2n = 2(n-1) — and directly, while the walk is away from v each step lands on v with probability frac1{n-1}, so Huv = n-1 and symmetry gives Cuv = 2(n-1) ✓;
- cycle Cn: R = ((n/2)(n/2))/(n) = n/4 ⇒ C = Θ(n2),
- lollipop / "barbell" graphs: cover time Θ(n3) — the worst case for random walk covering, and the reason "let the walk run and hope" is not an algorithm,
- general bounds: cover time is at least n log n (coupon collector; tight on Kn) and at most (4)/(27) n3 (1+o(1)) (Feige); the elementary bound on the maximum hitting time is Hmax ≤ 2m(n-1) = O(n3), from Cuv ≤ 2m · (n-1) using Reff ≤ distance in edges ≤ n-1,
- bipartite graphs: the walk is periodic, so stationary distribution arguments fail unless you add laziness (with probability ½ stay put) — a real trap, since πu = (deg u)/(2m) only holds for the aperiodic (lazy) chain.
#Two algorithms built on walks
- Monte-Carlo s–t connectivity / undirected ST = L (Reingold): a walk of length poly(n) finds a path in a connected graph with constant probability using O(log n) random bits per step, via expander graph products — the reason L is closed under complement, and the reason "random walk on a graph" is a complexity topic, not just a puzzle;
- Karp–Luby style walk-based counting/estimation, and loopy random walks for sampling from a distribution defined on states (MCMC): the mixing time bound ≤ a cover-type bound is the practical version. For a contest problem, walks appear mainly as expected-value recurrences (solve a small linear system by Gaussian elimination — Linear Recurrences from Graphs and Matrices' "expected steps" examples) and the answer is "set up n equations, O(n3)".
#Worked: a walk on a tree
For a path of length d starting at one end, H = d2. For a general tree and target v: root at v; the walk's edge-crossing counts give the elegant formula
where se is the number of vertices on the u-side of e. Proof by first-step analysis: to make progress you must cross each path edge, and every time you cross an edge away from v into a side branch of size s, returning takes an expected 2s further steps (gambler's ruin on that pendant subtree); summing the forced crossings and the excursions gives the formula, which for a path (se = distance from u) telescopes to d2. This is why "expected hitting time on a tree" is an O(n) DFS, not a linear solve, and it is the trick behind several olympiad-style expectation problems.
#Modelling traps
- "Expected number of steps until something happens" needs the right state: if the process has memory (visited-set, last colour), the state space is 2n-ish and the linear system is over states, not vertices;
- absorbing states must be made absorbing (remove the target row) or the system is singular,
- with weights/probabilities that are not 1/deg, the commute-time identity is false — you get Reff with conductances ce = weight, and C = vol · R, where vol = ∑ weights; forgetting
volinstead of 2m is the standard slip, - floating point: expectations are rationals; if the answer is requested mod p, solve the linear system over 𝔽p (Linear Recurrences from Graphs and Matrices) — the matrix is invertible mod p for prime p > n in the usual cases, and Gaussian elimination with modular inverse is the implementation.