Commute time of a random walk
ID: commute-time-of-a-random-walk
For a finite connected undirected graph, the commute time of a random walk between and is the expected time to travel from to and back:For the simple random walk and unit edge resistances, it satisfies , where 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 edges, the endpoint resistance is and the commute time is ; each one-way hitting-time expectation is . On a triangle, two routes give resistance , so the commute time between any pair is . The identity applies to this reversible walk and its associated resistor network, not to arbitrary directed transition rules.
New to topics? Read the docs here!