= Commute time of a random walk
{title2=$C_{ab}$}
For a finite connected undirected <graph>, the <commute time of a random walk> between $a$ and $b$ is the expected time to travel from $a$ to $b$ and back:
$$
C_{ab}=\mathbb E_aT_b+\mathbb E_bT_a.
$$
For the <simple random walk> and unit edge resistances, it satisfies $C_{ab}=2|E|R_{\mathrm{eff}}(a,b)$, where $R_{\mathrm{eff}}$ is <effective resistance>. Each additional parallel route lowers resistance and therefore lowers commute time when the total edge count is fixed.<Markov Chains and Mixing Times, second edition by David A. Levin and others>[Chapter 9, commute-time identity]{ref}
On a path with $m$ edges, the endpoint resistance is $m$ and the commute time is $2m^2$; each one-way hitting-time expectation is $m^2$. On a triangle, two routes give resistance $1\parallel2=2/3$, so the commute time between any pair is $2\cdot3\cdot(2/3)=4$. The identity applies to this reversible walk and its associated resistor network, not to arbitrary directed transition rules.
Back to article page
