§2, p. 4 — the eigenvalues of the transition matrix of an irreducible, reversible Markov chain are real
ProvedAccelVI.MVC.reversible_real_spectrummarkov-chainp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1reversible-markov-chainspectrum
Let be the transition matrix of a Markov chain on a finite state set (nonnegative entries, rows summing to ), and suppose the chain is irreducible and reversible: there is a stationary probability distribution with for all . Then every eigenvalue of is real:
The paper quotes this fact from Brémaud (Chapter 6, Section 2.1); it is what makes the eigenvalues of explicit in the proof of Lemma B.2.
Formalization Note. The spectrum is taken over : is the spectrum of the complexified matrix, and "real" means zero imaginary part. Irreducibility, stationarity and detailed balance are the published mm_basic notions.
Preamble
import Mathlib import Definitions.Def_mm_basic import Definitions.Def_AccelVI_MVC_Setting
Formal statement
namespace AccelVI.MVC
variable {S : Type*} [Fintype S] [DecidableEq S]
/-- §2, p. 4 (after Definition 2.1): the eigenvalues of the transition matrix of an irreducible,
reversible Markov chain are all real. -/
theorem reversible_real_spectrum (L : Matrix S S ℝ) (hL : MarkovMixing.IsStochastic L)
(hrev : AccelVI.AVC.IsReversible L) :
∀ μ ∈ spectrum ℂ (L.map (algebraMap ℝ ℂ)), μ.im = 0 := by sorry
end AccelVI.MVC
Source
Goyal & Grand-Clément, A First-Order Approach to Accelerated Value Iteration, arXiv:1905.09963v7, p. 4, paragraph after Definition 2.1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.