§2, p. 4 — the eigenvalues of the transition matrix of a reversible Markov chain are all real
ProvedAccelVI.AVC.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 space (nonnegative entries, rows summing to one), and suppose the chain is reversible in the sense of Definition 2.1: is irreducible and has a stationary distribution with for all . Then every eigenvalue of is real:
The paper cites this from Brémaud (2013, Ch. 6, §2.1) and uses it to locate the spectrum of in the analysis of A-VC.
Formalization Note. The spectrum is that of viewed as a complex matrix, so non-real eigenvalues are not excluded by the choice of field. The stationary distribution is a probability vector by the definition of stationarity in mm_basic.
Preamble
import Mathlib import Definitions.Def_mm_basic import Definitions.Def_AccelVI_AVC_Setting
Formal statement
namespace AccelVI.AVC
variable {S : Type*} [Fintype S] [DecidableEq S]
/-- §2, p. 4 (after Definition 2.1): the eigenvalues of the transition matrix `L` of a
reversible Markov chain are all real. -/
theorem real_spectrum (L : Matrix S S ℝ) (hL : MarkovMixing.IsStochastic L)
(hrev : IsReversible L) :
∀ μ ∈ spectrum ℂ (L.map (algebraMap ℝ ℂ)), μ.im = 0 := by sorry
end AccelVI.AVC
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.