Markov Chains and Mixing Times

By David A. Levin, Yuval Peres, Elizabeth L. Wilmer. 2008

1,046 citations recorded by the source corpus.

Subfields: Computer Vision and Pattern Recognition, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/4a853f3325dd0e13bc7c4b4eb07ae23e7bef459b

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Vision and Pattern Recognition

1. Neil Zhenqiang Gong
2. Yuval Peres
3. Bruno Ribeiro
4. Alexander Rakhlin
5. Ali Jadbabaie
6. Maxim Raginsky
7. D. Towsley
8. Jianshu Chen

In Statistical and Nonlinear Physics

1. Angelia Nedić
2. Alexander Olshevsky
3. Binghui Wang
4. Ali H. Sayed
5. Neil Zhenqiang Gong
6. Jianshu Chen
7. Jinyuan Jia
8. Santiago Zazo

Citations in the corpus

• Walkman: A Communication-Efficient Random-Walk Algorithm for Decentralized Optimization (2018, methodology): “f current state iand time k, the probability of visiting each state jafter ˝() more steps is (ˇ )-close to ˇ j, that is, for all i;j2V, [P˝()] ij ˇ j ˇ: (4) 3 A good reference for mixing time is [31]. The mixing time requirement, inequality (3), is guaranteed to hold for[1] ˝() := l 1 1 ˙(P) ln p 2 ”
• Network Topology and Communication-Computation Tradeoffs in Decentralized Optimization (2017, background): “or example, the fact that the hitting time on the path graph is quadratic in the number of nodes is essentially the main finding of the standard “gambler’s ruin” exercise (see e.g., Proposition 2.1 of [28]). The result for the 2-d grid follows from putting together Theorem 2.1 and Theorem 6.1 of [29]”
• Some simple but challenging Markov processes (2014, background): “brium in L2 µ. When the invariant measure is reversible, the spectral decomposition (and particularly its spectral gap) of L provides fine estimates for the convergence to equilibrium. See for example [41] and the connection with coupling strategies and strong stationary times introduced in [1]. Open”
• Coordinate Dual Averaging for Decentralized Online Optimization With Nonseparable Global Objectives (2015, background): “[n]: The conditions we have imposed on the pair (r;M) are equivalent to saying that Mis the transition probability matrix of a reversible random walk on Gwith invariant distribution r = (r 1;:::;r n) [38]. Let zk(t) = (zk 1(t);:::;zk n(t)); k2[n]; t0; (17) andP r ,min 1inr i. We state the following ”
• Distributed Detection: Finite-Time Analysis and Impact of Network Topology (2014, background): “trality of each agent are fixed. The key idea is to change the mixing behavior of the Markov chain W. It June 14, 2018 DRAFT 14 is well-known, for instance, that we could do so using lazy random walks [26] which replaces W with 1 2 (W+ I n). To generalize the idea, let us define a modified communicatio”
• Structure-Based Sybil Detection in Social Networks via Local Rule-Based Propagation (2018, background): “These guarantees are achieved based on the assumption that the benign region of the social network is fast-mixing [44].”
• Distributed Policy Evaluation Under Multiple Behavior Strategies (2013, background): “te Markov chain resulting from the MDP is irreducible and aperiodic under any policy of interest. Thus, it has a unique positive stationary probability distribution of visiting each state [6, App. A] [30] denoted by d π= [d (1),...,dπ(S)]⊤, such that dπ(s) > 0, for all 1 ≤ s ≤ S. November 6, 2014”
• Incremental Knowledge Base Construction Using DeepDive (2015, neutral): “First, we define a coupling [15,29].”
• A Structural Model of Segregation in Social Networks (2010, background): “37See Meyn and Tweedie (2009), Levin et al. (2008) of the model.”
• Analyzing concept drift and shift from sample data (2018, methodology): “In the current work we employ total variation distance (Levin et al. 2008): where Z represents a vector of random variables.”
• Iterative parameter mixing for distributed large-margin training of structured predictors for natural language processing (2015, background): “The relationship between mixing time and spectral properties holds more generally (Guruswami, 2000; Levin et al., 2009).”
• Glauber dynamics for the mean-field Ising model: cut-off, critical power law, and metastability (2007, background): “gap of P is bounded below by c3= (see, for example, Sinclair (1993).) The mixing time, in turn, is bounded below by the spectral gap (see, for example, Aldous and Fill (in progress).) The details of this standard argument can be found in the forthcoming book Levin, Peres, and Wilmer (2007) .”