Geometric Bounds on the Fastest Mixing Markov Chain
summary
Proves two concrete claims: a Cheeger-type bound that the optimal reversible relaxation time is Theta(1/phi_match) up to a log N factor (uses SDP duality, a Rock-style variational formula and Johnson–Lindenstrauss to reduce to 1D) and an existence theorem giving a reversible chain with relaxation time ≤ diameter^2 whose invariant measure is ε-close to uniform. Key concepts are matching conductance (matches vertex conductance up to constants but can be smaller for some cuts) and a weighted BFS spanning tree construction. Examples: two N-vertex cliques linked by a perfect matching admit a chain with relaxation O(1) by weighting inter-clique edges by N; a K-edge bottleneck yields simple RW gap Θ(K/N^2) but optimized chains via sparsification get relaxation ≈N.
AI-written summary · about