---
title: "Random Walks and Cover Times"
summary: Hitting times as linear equations, commute-time bounds via effective resistance, and the walk-based algorithms that actually get used.
difficulty: hard
tags: [probability, markov, trees]
prereq: [matrices/recurrences, foundations/types]
see: [matrices/walks-powers, special/independent]
---

## Hitting and commute times

:::definition label="The objects"
A walk on $G$ that at each step chooses a uniformly random neighbour of the current vertex. $H_{uv}$ = **hitting time** = expected steps to reach $v$ from $u$; $C_{uv} = H_{uv} + H_{vu}$ = **commute time**; the **cover time** is the expectation of the first time all vertices have been visited.
:::

## Hitting times solve a linear system

:::theorem title="Hitting times solve a linear system"
For fixed target $v$: $H_{vv} = 0$ and
$$H_{uv} = 1 + \frac{1}{\deg(u)} \sum_{w \sim u} H_{wv} \qquad (u \ne v).$$
On a connected graph this system has a unique solution.
:::

:::proof
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

:::theorem title="Commute time = effective resistance"
$$C_{uv} = 2m \cdot R_{\mathrm{eff}}(u,v),$$
where $R_{\mathrm{eff}}$ is the resistance between $u$ and $v$ when every edge is a $1\,\Omega$ resistor.
:::

:::proof
Inject one unit of current at $u$ and extract it at $v$; the potential $\phi$ then satisfies $L\phi = \mathbf 1_u - \mathbf 1_v$ (Kirchhoff) and $\phi(u)-\phi(v) = R_{\mathrm{eff}}$. The proof identifies the hitting-time difference with this potential. Define $g(x) = H_{xu} - H_{xv}$. Subtracting the two hitting-time equations cancels the $+1$ terms, so $g$ is **harmonic** at every $x \notin \{u,v\}$: $g(x)$ is the average of $g$ over its neighbours. The unit-current potential $\phi$ 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 $\frac{1}{\deg}$ times the stationary mass $\frac{\deg(x)}{2m}$, so the "flow" $2m\,\nabla g$ is a unit flow from $u$ to $v$; energy minimality then gives $g(u)-g(v) = 2m\,(\phi(u)-\phi(v)) = 2m R_{\mathrm{eff}}$. Since $C_{uv} = H_{uv}+H_{vu} = g(u) - g(v)$ with this $g$, the identity follows. ∎
:::

## Values you can quote

:::props title="Consequences you can quote (with the resistance computed by hand)"
- **path** on $n$ vertices: $R_{\text{eff}} = n-1$ ohms in series ⇒ $C = \Theta(n^2)$ ⇒ hitting time from end to end is $\Theta(n^2)$ (the classic gambler's-ruin computation),
- **complete graph** $K_n$: $R_{\mathrm{eff}} = 2/n$ (direct edge $1\,\Omega$ in parallel with the $n-2$ two-edge paths, each of $2\,\Omega$, giving $\big(1 + \tfrac{n-2}{2}\big)^{-1} = \tfrac{2}{n}$) ⇒ $C_{uv} = 2m R = n(n-1)\cdot\tfrac2n = 2(n-1)$ — and directly, while the walk is away from $v$ each step lands on $v$ with probability $\frac1{n-1}$, so $H_{uv} = n-1$ and symmetry gives $C_{uv} = 2(n-1)$ ✓;
- **cycle** $C_n$: $R = \frac{(n/2)(n/2)}{n} = n/4$ ⇒ $C = \Theta(n^2)$,
- **lollipop / "barbell" graphs**: cover time $\Theta(n^3)$ — 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 $K_n$) and at most $\frac{4}{27} n^3 (1+o(1))$ (Feige); the elementary bound on the maximum hitting time is $H_{\max} \le 2m(n-1) = O(n^3)$, from $C_{uv} \le 2m \cdot (n-1)$ using $R_{\mathrm{eff}} \le$ distance in edges $\le 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 $\pi_u = \frac{\deg u}{2m}$ only holds for the aperiodic (lazy) chain.
:::

## Two algorithms built on walks

:::note title="The two algorithms built on walks"
- **Monte-Carlo $s$–$t$ connectivity / undirected ST = L** (Reingold): a walk of length $\mathrm{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 $\le$ 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 — @matrices/recurrences' "expected steps" examples) and the answer is "set up $n$ equations, $O(n^3)$".
:::

## Worked: a walk on a tree

:::example title="Worked: random walk on a tree, expected time from root to a fixed leaf"
For a path of length $d$ starting at one end, $H = d^2$. For a general tree and target $v$: root at $v$; the walk's edge-crossing counts give the elegant formula
$$H_{uv} = \sum_{e \in \mathrm{path}(u,v)} \big(2 s_e - 1\big),$$
where $s_e$ 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 ($s_e = $ distance from $u$) telescopes to $d^2$. 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

:::warning title="Modelling traps"
1. "Expected number of steps until something happens" needs the *right* state: if the process has memory (visited-set, last colour), the state space is $2^n$-ish and the linear system is over states, not vertices;
2. absorbing states must be *made* absorbing (remove the target row) or the system is singular,
3. with weights/probabilities that are not $1/\deg$, the commute-time identity is false — you get $R_{\text{eff}}$ with conductances $c_e = $ weight, and $C = \mathrm{vol} \cdot R$, where $\mathrm{vol} = \sum$ weights; forgetting `vol` instead of $2m$ is the standard slip,
4. floating point: expectations are rationals; if the answer is requested mod $p$, solve the linear system over $\mathbb{F}_p$ (@matrices/recurrences) — the matrix is invertible mod $p$ for prime $p > n$ in the usual cases, and Gaussian elimination with modular inverse is the implementation.
:::

:::problems
- [[CSES 1751]] Planets Cycles | https://cses.fi/problemset/task/1751 | core | functional-graph walk length until repetition — the deterministic twin
- [[CSES 1750]] Planets Queries I | https://cses.fi/problemset/task/1750 | easy | "where is the walk after k steps": lifting, not expectations
:::