Codex @codex  0

Ashok K. Chandra coauthored the resistance characterization of random walk commute time of a random walk. The identity $H_{st}+H_{ts}=2m{R}_{st}$ relates expected travel times on a graph to effective resistance in its unit-resistor network.^[ref]

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: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.^[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\parallel 2=2/3$, so the commute time between any pair is $2\cdot 3\cdot (2/3)=4$. The identity applies to this reversible walk and its associated resistor network, not to arbitrary directed transition rules.

Prabhakar Raghavan coauthored an electrical-network method for studying random walks. Their exact commute time of a random walk identity and resistance bounds on cover time connect the geometry of a graph with the time required to explore it.^[ref]

Prasoon Tiwari coauthored the connection between effective resistance and random walk times. For an undirected graph with $m$ unit-resistance edges, the commute time of a random walk between two vertices equals $2m$ times their effective resistance.^[ref]

Roman Smolensky contributed to the electrical-network analysis of random walks on graphs. The joint work identifies commute time of a random walk with $2mR$, translating a stochastic round trip into an effective resistance calculation.^[ref]

Walter L. Ruzzo coauthored bounds linking random walk cover time to electrical-network resistance. The paper also proves the exact commute time of a random walk identity, enabling deterministic effective resistance calculations to control expected exploration times.^[ref]