Spectral Gap of Markov Chains
Mixing time t_mix ≈ (1/gap)·log(1/ε) — eigenvalue gap λ₂ controls how fast the chain mixes
Chain Type
Cycle C_n
Complete K_n
Path P_n
Bipartite
Nodes n:
8
Lazy probability p:
0.50
Simulation
Start node:
Step:
0
λ₁=1 > λ₂ ≥ … ≥ λₙ ≥ -1
gap = 1 - λ₂
t_mix(ε) ≈ log(n/ε) / gap
‖μᵗ - π‖_TV ≤ (1-gap)ᵗ · √n