Lectures in Probability and Statistics (LPS) XV
Date: December 2022
Place: Indian Institute of Science, Bengaluru
The conference webpage is available here.
Lecture notes/transcripts
For some notes and references on basic Markov chain theory, please see the webpages for iterations of related courses I taught in Winter 2020, Monsoon 2017 and Winter 2022.
Functional inequalities and mixing times: See pp. 1-10 of these notes.
A simple case: functional inequalities for the random walk on the hypercube: See these notes.
- In the lectures, we did the slightly simpler Poincare calculation rather than the modified log Sobolev (MLS) inequality worked out in the notes above.
Analysis of the basis-exchange walk for matroids
See these notes for the “inductive” argument performed for the setting of the Poincare inequality ([ALOGV]), based on the setup of [CGM].
The notes here give a presentation of the proof of the MLS inequality completely following the presentation of [CGM], but are more dense in notation.
See these slides for the setup for the proof of the spectral gap that comprises the base case of the above induction. The detailed calculation (from [ALOGV]) can be found in these notes, pp. 26-31. Note that the rank \(r\) in the slides is written as \(d\) in the notes.
References
[ALOGV]: Anari, Nima, Kuikui Liu, Shayan Oveis Gharan, and Cynthia Vinzant. Log-Concave Polynomials II: High-Dimensional Walks and an FPRAS for Counting Bases of a Matroid. Proc. ACM STOC 2018. Available at arXiv:1811.01816.
[BH]: Brändén, Petter, and June Huh. Lorentzian Polynomials. Ann. Math. Available at arXiv:1902.03719.
[CE]: Chen, Yuansi, and Ronen Eldan. Localization Schemes: A Framework for Proving Mixing Bounds for Markov Chains. Proc. IEEE FOCS 2022. Available at arXiv:2203.04163.
[CGM]: Cryan, Mary, Heng Guo, and Giorgos Mousa. Modified Log-Sobolev Inequalities for Strongly Log-Concave Distributions. Proc. IEEE FOCS 2019 Available at arXiv:1903.06081.