Section 9.1 -- the network walk is reversible
ProvedMarkovMixing.network_walk_reversiblemarkov-chainsmixing-timesprobability
A network on a finite vertex set is a conductance function : a symmetric assignment of nonnegative weights to pairs of vertices. Write for the total conductance at the vertex — assumed strictly positive at every vertex — and for the total over all vertices. The weighted random walk on the network steps from to with probability proportional to the conductance:
The theorem (§9.1 of Levin–Peres–Wilmer) asserts:
- is a genuine Markov chain: nonnegative entries with every row summing to one;
- satisfies the detailed balance equations with respect to the distribution — it is reversible;
- is a stationary distribution for : for every .
This is the dictionary's first entry: every network yields a reversible chain, and conversely every reversible chain arises this way — which is why the electrical machinery of Chapters 9–10 computes hitting times of reversible chains.
Preamble
import Definitions.Def_mm_network
Formal statement
namespace MarkovMixing
/-- **§9.1** (LPW): the weighted random walk on a network is a Markov chain,
reversible with respect to `π(x) = c(x)/c_G`, which is therefore its
stationary distribution. -/
theorem network_walk_reversible {V : Type*} [Fintype V] [DecidableEq V]
[Nonempty V] (c : V → V → ℝ) (hc : IsConductance c)
(hpos : ∀ x : V, 0 < vertexConductance c x) :
IsStochastic (networkWalk c) ∧
DetailedBalance (networkWalk c)
(fun x => vertexConductance c x / totalConductance c) ∧
IsStationary (networkWalk c)
(fun x => vertexConductance c x / totalConductance c) := by
sorry
end MarkovMixing
Source
D. A. Levin, Y. Peres, E. L. Wilmer, Markov Chains and Mixing Times, AMS 2009, https://documents.epfl.ch/groups/i/ip/ipg/www/2013-2014/Random_Walks/markovmixing.pdf, Section 9.1, pp. 115-116