Section 12.3.1 -- eigenvalues of the cycle
ProvedMarkovMixing.cycle_eigenvaluesmarkov-chainsmixing-timesprobability
Simple random walk on the -cycle is the Markov chain on that moves from to or with probability each. A real number is an eigenvalue of the chain when there is a nonzero function with , where .
The theorem (§12.3.1 of Levin–Peres–Wilmer) asserts: for , every number of the form
is an eigenvalue of the walk. The eigenfunctions behind these values are the discrete Fourier modes and . (The statement exhibits these eigenvalues; that they exhaust the spectrum is not asserted.) In particular the spectral gap of the cycle is , giving relaxation time of order — the model computation for the spectral theory of Chapter 12, matching the coupling bounds for cycles obtained in earlier missions.
Preamble
import Definitions.Def_mm_spectral import Mathlib.Analysis.SpecialFunctions.Trigonometric.Basic
Formal statement
namespace MarkovMixing
/-- **§12.3.1** (LPW): the eigenvalues of simple random walk on the
`n`-cycle are `cos(2πj/n)` for `j = 0, 1, …, n−1`. -/
theorem cycle_eigenvalues (n : ℕ) [NeZero n] (hn : 3 ≤ n) (j : Fin n) :
IsEigenvalue (cycleWalk n) (Real.cos (2 * Real.pi * j / n)) := 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 12.3.1, pp. 156-157