Markov Chain Mixing Times and Applications I

on YouTube ↗01h 02m

" summary

Starts from Markov chains, defines ergodic chains and mixing time, links convergence to the spectral gap (eigenvalue 1 vs second eigenvalue) and shows how to get a target distribution using the Metropolis filter (accept with ratio pi(y)/pi(x)). Gives a concrete sampling→counting reduction for matchings via a telescoping product (M ratios, roughly M^2/ε^2 samples total) and develops coupling: bound total variation by Pr[Xt ≠ Yt], so mixing time ≤ 4 · max_xy E[coupling time]. Applies it to random transpositions to get O(n^2) mixing.

AI-written summary · about

" chapters (8)

1. 0:00Intro
2. 0:20Introduction to Markov Chains
3. 10:26Exponential State Space
4. 16:10Designing a Markov Chain
5. 30:22Techniques for bounding the mixing time
6. 36:53Example - Biased coins
7. 44:14Coupling Markov chains
8. 53:54Bound on the mixing time

" related talks

• 50mRandom Combinatorial MatricesAmin Coja-Oghlan · Algorithmic Advances for Statistical Inference with Combinatorial Structure
• 45mImproved Learning from Time-bounded Kolmogorov ComplexityHalley Goldberg · Lower Bounds, Learning, and Average-Case Complexity
• 29mExtended Formulations and Information ComplexityAnkur Moitra · Information Theory in Complexity Theory and Combinatorics 2015
• 01h 10mDistribution Estimation and Applications IAlon Orlitsky · Information Theory Boot Camp 2015
• 27mSmall Value Parallel Repetition for General GamesAnkit Garg · Information Theory in Complexity Theory and Combinatorics 2015
• 30mStreaming Lower Bounds for Approximating MAX-CUTMichael Kapralov · Information Theory in Complexity Theory and Combinatorics 2015
• 23mHow to Cheat at “Who Wants to Be a Millionaire?” (and Show Non-Hardness of GapMCSP)Neekon Vafa · Lower Bounds, Learning, and Average-Case Complexity
• 33mWelfare Maximization with Limited Interaction: Information and Communication in EconomicsOmri Weinstein · Information Theory in Complexity Theory and Combinatorics 2015