Characterization of Cutoff for Reversible Markov Chains, and Surprise Probabilities
summary
Proves a sharp inequality: t_mix(2ε) ≤ hit_{1/2}(ε) + C t_rel log(1/ε), and deduces that for lazy reversible chains on trees the product condition (t_rel = o(t_mix)) implies cutoff with a window of order sqrt(t_rel · t_mix) — i.e. the geometric mean window. Key tools are variance decay and a classical L^2 maximal inequality (Stein/Nikishin type) to control hitting tails. Gives concrete benchmarks: hypercube and random transpositions mix at (1/2) n log n, while two‑cliques exhibit no cutoff.
AI-written summary · about
chapters (21)
- 0:00Intro
- 0:46Notation
- 1:10TV distance
- 8:05Cutoff - definition
- 13:17Background
- 15:05Spectral gap & relaxation time
- 16:11The product condition (Prod. cond)
- 20:29Aldous example
- 26:05Hitting and Mixing
- 27:45counter-example
- 31:34Cutoff for trees
- 35:03Hitting times when Xo
- 36:32Hitting of worst sets
- 37:56Main abstract result
- 39:09Tools
- 43:00Combining the Max-in with the Contraction Lomma
- 47:51Main idea
- 52:31Central vertex
- 55:33Beyond trees
- 56:41Last remark
- 57:25Open problems
related talks
20mBalanced Allocations with Incomplete Information: The Power of Two Queries
57mCoding for Interactive Communication
26mCounting Distinct Elements in the Message Passing Model
45mOn Analyzing Blockchain Consistency
27mOn Distributed Differential Privacy and Counting Distinct Elements
01h 07mMarrying Graph Convergence and Cascade Models
01h 02mConditional Hardness for Massively Parallel Computing (MPC) Via Distributed Lower Bounds
01h 02mDerandomization to Boolean Circuit Lower Bounds