Markov Chain Mixing Times and Applications II
summary
Metropolis chain on proper colorings mixes in order O(n log n) when the number of colors satisfies q > 4Δ via a simple coupling that contracts expected Hamming distance; path coupling (Bubley–Dyer) sharpens the analysis so only pairs differing at one vertex need consideration and proves the same O(n log n) bound for q > 2Δ by showing a per-step contraction. Exact sampling uses a coupling from the past construction via a random-function representation; monotone CFTP reduces work to top and bottom states when a lattice order exists.
AI-written summary · about
chapters (14)
- 0:00Intro
- 1:40A few remarks on yesterday's talk
- 4:50Sampling Colorings
- 6:02A coupling for colorings Recall
- 7:52Case analysis
- 15:12Mixing time
- 22:00Path Coupling (Bubley-Dyer 1997)
- 26:53Metropolis chain on extended space
- 28:53Path coupling for colorings
- 41:12Exact Sampling. Coupling from the past
- 43:56Random function representation of a MC
- 47:16Simulating forwards and backwards in time
- 51:18Why does CFTP work?
- 54:30Implementing CFTP
related talks
55mLower Bounds for Subgraph Isomorphism and Consequences in First-Order Logic
30mStreaming Lower Bounds for Approximating MAX-CUT
01h 09mInformation Theory in Computational Complexity IV
23mHow to Cheat at “Who Wants to Be a Millionaire?” (and Show Non-Hardness of GapMCSP)
33mLucky Talk: Exponential Separation of Information and Communication
50mRandom Combinatorial Matrices
31mAnswering FAQs in CSPs, PGMs, Databases, Logic and Matrix Operations
01h 17mInapproximability of Constraint Satisfaction Problems III