Mathematical Aspects of Mixing Times in Markov Chains
By Ravi Montenegro, Prasad Tetali. Foundations and Trends® in Theoretical Computer Science, 2006
373 citations recorded by the source corpus.
Subfields: Statistical and Nonlinear Physics
View Paper: https://www.semanticscholar.org/paper/d616d628cf5455db883d4112fd872e3e9d22f24f
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Statistical and Nonlinear Physics
- Devavrat Shah
- Maxim Raginsky
- Sean F. Lawlor
- Konstantinos I. Tsianos
- Michael G. Rabbat
- Persi Diaconis
- Justin Salez
- Sourav Chatterjee
Citations in the corpus
- The Markov chain Monte Carlo revolution (2008, background): “A good survey of this set of ideas is in [69].”
- Consensus-based distributed optimization: Practical issues and applications in large-scale machine learning (2012, result): “We remark that more recent results for characterizing the mixing times of non-reversible Markov chains with zero minimum holding probability [29] may lead to tighter results and this is an interesting direction for future work.”
- Cutoff for non-negatively curved Markov chains (2021, methodology): “Understanding how this fundamental parameter depends on the underlying transition matrix P constitutes a fascinating area of research, at the crossroad between probability, discrete geometry, spectral analysis and functional inequalities; see the books [43, 51] for an introduction.”
- Geometric ergodicity and the spectral gap of non-reversible Markov chains (2009, background): “If the chain is reversible, the same equivalence holds with L2 in place of L V ∞ , but in the absence of reversibility it fails: There are (necessarily non-reversible, geometrically ergodic) chains that admit a spectral gap in LV ∞ but not in L2.”
- Gossip Algorithms (2009, background): “To learn details of these results/techniques as well as a host of other results/techniques we refer an interested reader to the excellent surveys by Lovasz and Winkler [43], Montenegro and Tetali [52].”
- Strong Data Processing Inequalities and $\Phi $ -Sobolev Inequalities for Discrete Channels (2014, background): “In the literature on Markov chains (see, e.g., [25], [46], [47]), one often sees the following definition: given a pair (μ, K ) ∈ P ( X ) × M ( X | X ) such that μ is invariant w.r.t.”