Solution
ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2017/iii/paper-215/3/b/solution
Past exam of the mathematics course of the University of Cambridge 2017 iii Paper 215 3 b Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-06
For a finite irreducible Markov chain satisfying detailed balance, define the directed-edge capacity . For every ordered pair choose a path from to using only positive-capacity edges; take the empty path for . Let count occurrences of the directed edge . The canonical paths Poincare bound says thatis a valid Poincare inequality for a reversible Markov chain constant. Simple paths give ; allowing repetitions requires the multiplicities shown.
To prove the theorem, expand the variance using two independent samples from :Telescoping along and applying the Cauchy-Schwarz inequality givesInterchange the finite sums, then use the definition of :Consequently . All edges here are directed, so the in the Dirichlet form of a Markov chain is retained consistently.
New to topics? Read the docs here!