Propositions 2.12 and 2.14 -- random walks on finite groups
ProvedMarkovMixing.group_walk_uniform_stationarymarkov-chainsmixing-timesprobability
The random walk on a finite group with increment distribution (step from to with probability ) is a Markov chain for which the uniform distribution on is stationary; and if is symmetric (), the walk is reversible with respect to the uniform distribution.
Preamble
import Definitions.Def_mm_basic
Formal statement
namespace MarkovMixing
/-- **Propositions 2.12 and 2.14** (LPW): the random walk on a finite group
with increment distribution `μ` is a Markov chain for which the uniform
distribution is stationary; if `μ` is symmetric (`μ(g) = μ(g⁻¹)`), the walk is
moreover reversible. -/
theorem group_walk_uniform_stationary {G : Type*} [Group G] [Fintype G]
[DecidableEq G] (μ : G → ℝ) (hμ : IsDist μ) :
IsStochastic (groupWalk μ) ∧
IsStationary (groupWalk μ) (uniformDist G) ∧
((∀ g : G, μ g⁻¹ = μ g) → DetailedBalance (groupWalk μ) (uniformDist G)) := 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 2.6, Propositions 2.12 and 2.14, pp. 28-29