Markov chains and mixing times

By Vaughn Climenhaga. 2013

Subfields: Probabilistic & Bayesian Methods

How researchers see this paper

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

In Probabilistic & Bayesian Methods

Citations in the corpus

Generalized Off-Policy Actor-Critic (2019, background): “The pointwise convergence for each ˆ γ is a standard conclusion for ergodic MDPs (Theorem 4.9 in Levin and Peres 2017).”
Dual Averaging for Distributed Optimization: Convergence Analysis and Network Scaling (2010, positive): “In particular, the inverse dependence on the spectral gap 1 − σ 2 ( P ) is quite natural, since it is well-known to determine the rates of mixing in random walks on graphs [LPW08], and the propagation of information in our algorithm is integrally tied to the random walk on the underlying graph with…”
Achieving Geometric Convergence for Distributed Optimization Over Time-Varying Graphs (2016, background): “Such bounds have been explored at great length within Markov chain literature, see e.g., the seminal paper [18] or the monograph [29], resulting in many diﬀerent techniques, each giving accurate bounds on some graphs, and others.”
Training Quantized Nets: A Deeper Understanding (2017, background): “We say that the -mixing time of the chain is M if M is the smallest integer such that [23] |P(x ∈ A|x)− π(A)| ≤ , for all x and all subsets of states A ⊆ X.”
Plausible Deniability for Privacy-Preserving Data Synthesis (2017, methodology): “We use a well-established statistical distance metric called “the” R e a l M a r g i n a l statistical distance (a.k.a. total variation distance [17, 30]).”
Bayesian computation: a perspective on the current state, and sampling backwards and forwards (2015, background): “…Meyn and Tweedie (2009); Roberts and Rosenthal (2004)), L 2 ( π ) spectral gap (Diaconis and Stroock (1991); Roberts (1996); Saloﬀ-Coste (1997); Levin et al. (2009)) or asymptotic variance (Peskun (1973); Geyer (1992); Tierney (1998)) in the Markov chain central limit theorem will not be…”
Bayesian computation: a summary of the current state, and samples backwards and forwards (2015, background): “…rate (c.f. Meyn and Tweedie 2009; Roberts and Rosenthal 2004), L 2 (π) spectral gap (Diaconis and Stroock 1991; Roberts 1996; Saloff-Coste 1997; Levin et al. 2009) or asymptotic variance (Peskun 1973; Geyer 1992; Tierney 1998) in the Markov chain central limit theorem will not be available…”
Empirical Dynamic Programming (2013, methodology): “By [27, Theorem 12.3], We now use the above bound on mixing time to get a non-asymptotic bound for EVI.”
Statistical Windows in Testing for the Initial Distribution of a Reversible Markov Chain (2018, methodology): “Let P be the Markov Chain on X , where, P(Xs = i|Xs−1 = j) = 1 2 for i ∈ j − 1, j + 1, j ∈ {1, . . . , d− 2} 1 if j = 0 ∧ i = 1, or j = d− 1 ∧ i = d− 2 0 otherwise As in the case of the cycle, the spectrum is explicitly known (cf. (Levin et al., 2008, Chap.”
Speed of random walks, isoperimetry and compression of finitely generated groups (2015, background): “f ﬁnite Markov chains have been a very active research area in the past decades. For a great variety of Markov chains good estimates of their spectral gaps are known, examples can be found in [SC97], [LPW09]. Note that the same Poincaré inequality holds for Hilbert space valued functions f: M → H, t”