Lemma 4.13 -- a walk and its inverse walk mix at the same rate
ProvedMarkovMixing.group_walk_reversal_distanceLet be a finite group and a probability distribution on . The random walk on with increment distribution moves from to with probability : at each step an increment is drawn and multiplied on the left. Its time reversal is the walk driven by the inverse distribution , which undoes -steps. Write for the uniform distribution on and for the total variation distance, .
The theorem (Lemma 4.13 of Levin–Peres–Wilmer) asserts that the two walks approach uniformity at exactly the same speed: for every time , the distribution after steps started at the identity satisfies
where and are the transition matrices of the -walk and the -walk. Corollary 4.14 is immediate: a random walk on a group and its time reversal have the same mixing times. For card shuffling this means a shuffle and its inverse shuffle mix equally fast — the reason the riffle shuffle can be analyzed through the easier inverse riffle.
import Definitions.Def_mm_mixing
namespace MarkovMixing
/-- **Lemma 4.13 and Corollary 4.14** (LPW): a random walk on a finite group
and the walk with the inverse increment distribution (its time reversal) are
at the same total variation distance from the uniform distribution at every
time, so in particular they have the same mixing times. -/
theorem group_walk_reversal_distance {G : Type*} [Group G] [Fintype G]
[DecidableEq G] (μ : G → ℝ) (hμ : IsDist μ) (t : ℕ) :
tvDist (rowDist (groupWalk μ) t 1) (uniformDist G) =
tvDist (rowDist (groupWalk (invDist μ)) t 1) (uniformDist G) := by
sorry
end MarkovMixing