Spectral Gap — Markov Chain Mixing

Spectral Gap

For an ergodic Markov chain with transition matrix P, the eigenvalues 1=λ₁>λ₂≥...≥λₙ satisfy: ‖p(t)−π‖_TV ≤ (1/2)|λ₂|^t · √(n)

Spectral gap: γ = 1−λ₂. Mixing time: t_mix ≈ 1/γ

Poor connectivity → small γ → slow mixing. Expander graphs → large γ → fast mixing.