Let's Sample Perfectly

on YouTube ↗13m

" summary

Uniform sampling of proper colorings of an n-vertex graph with maximum degree Δ is framed: want exact samples from the uniform distribution over colorings, not approximate. Uses Glauber dynamics and perfect sampling via Coupling from the Past. Known thresholds: Jerrum shows rapid mixing for K > 2Δ, Vigoda improves mixing with flipped dynamics, Huber gives perfect sampling requiring K = Θ(Δ^2). Recent progress lowers perfect-sampling requirements to about 3Δ and then ≈8/3 Δ using preconditioning, with algorithms that are constructive and provably correct.

AI-written summary · about

" chapters (11)

1. 0:00Intro
2. 1:28Problem Statement and Result
3. 2:25Glauber Dynamics (GD) for Colorings
4. 3:02Approximate Sampling of Colorings
5. 3:51Why Exact Sampling?
6. 4:53Approximate Sampling vs Exact Sampling of Colorings
7. 7:12Framework for Exact Sampling
8. 8:35Coupling From the Past
9. 9:34Toy Example: CFTP for Random Walk on [n]
10. 10:31CFTP for Colorings
11. 12:03Further Questions