Canonical Paths for MCMC: From Art to Science

on YouTube ↗40m

" summary

Presents a concrete criterion that turns the canonical-paths trick into an algorithmic test: symmetric (Hamming-weight) constraints are windable exactly when a certain nonnegative solution exists to a linear system defined by a combinatorial matrix A that counts partitions of pairings. Uses canonical paths and flow-congestion bounds on a Metropolis chain over Omega0∪Omega2, reduces finding path weights to solving A x ≥ 0, and proves rapid mixing when the Omega2/Omega0 weight ratio is polynomial. Delivers FPRAS consequences: subgraph-world (μ>0) and b-matching are tractable up to b≤7, with worked examples and computations.

AI-written summary · about

" chapters (14)

1. 0:00Intro
2. 1:06MARKOV CHAIN FOR SAMPLING MATCHINGS
3. 2:21MIXING TIME
4. 5:48CANONICAL PATHS FOR JERRUM-SINCLAIR'S CHAIN
5. 7:59HOLANT PROBLEMS
6. 13:56HALF EDGES
7. 17:16CANONICAL PATHS FOR WINDABLE FUNCTIONS
8. 23:04WINDABILITY FOR SYMMETRIC FUNCTIONS
9. 26:04PROOF SKETCH
10. 27:50EXAMPLE: MATCHINGS
11. 29:09EXAMPLE: SUBGRAPHS WORLD
12. 30:47b-MATCHINGS
13. 32:17b-EDGE COVERS
14. 34:41FUTURE WORK