Pith. sign in

REVIEW 2 major objections 5 minor 37 references

Quantitative convergence rates for reversible Markov chains via strong random times

T0 review · 2 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read For reversible chains with nonnegative eigenvalues, any strong random time's tail controls the rate of convergence to stationarity, yielding explicit bounds that improve on existing quantitative methods.

desk verdict A genuinely new strong-random-time principle for reversible chains, with a clean proof; the numerical example needs better documentation but the core theorem holds up. read the letter →

arxiv 1908.06459 v1 pith:6HPU7SSU submitted 2019-08-18 math.PR math.STstat.TH

Daniel C. Jerison This is my paper · ORCID
classification math.PRmath.STstat.TH MSC 60J0560J22
keywords MarkovchainstrongrandomtimereversibilitynonnegativeeigenvaluesdriftandminorizationgeometricergodicityL2convergenceGibbssampler
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper establishes that for a reversible Markov chain whose transition operator has spectrum in $[0,1]$, the tail of any strong random time directly controls convergence to stationarity: the squared $L^2(\pi)$ distance after $t$ steps is at most the tail sum $\sum_{n=2t+1}^{\infty} \mathbb{P}_\nu(T>n)$. This turns the drift-and-minorization method into a fully quantitative tool, because the algorithm that constructs a strong random time also bounds its tail. The resulting explicit total-variation and $V$-norm bounds are tighter than previous quantitative bounds, cutting the guaranteed mixing time for a standard Gibbs sampler about in half.

What carries the argument

The central object is the strong random time $T$ with measure $\nu$: a randomized stopping time such that, conditioned on $T=n$, the state $X_n$ has distribution $\nu$ regardless of the initial measure. The argument's load-bearing identity is the spectral monotonicity of the sequence $\langle \mathbf{P}^t f,f\rangle_\pi$ when $\mathbf{P}$ is self-adjoint and its spectrum lies in $[0,1]$, which lets the tail of $T$ be converted into an upper bound on the $L^2(\pi)$ distance from stationarity. A separate drift-and-minorization algorithm constructs such a $T$ and bounds its tail, supplying the exponential rate $\rho$ and the linear prefactor $F(x,t)$ used in the final bounds.

What would settle it

Using the drift and minorization data in the paper's worked example ($\lambda=0.61$, $K=3.05$, $m=1$, $\varepsilon=0.287$, $C=[4.74,8.50]$), simulate the strong random time $T$ from the construction, estimate the tail sum $\sum_{n=2t+1}^{\infty}\mathbb{P}_\nu(T>n)$ and the actual $L^2(\pi)$ distance for small $t$; a systematic violation of Theorem 1.2's inequality would refute the central claim.

Watch

Extended reading notes

Core claim

For a Markov chain that is reversible with respect to $\pi$ and has nonnegative eigenvalues, Theorem 1.2 proves that any strong random time $T$ with measure $\nu$ satisfies $\|\mathbf{P}^t(\nu,\cdot)-\pi\|^2_{L^2(\pi)} \le \sum_{n=2t+1}^{\infty} \mathbb{P}_\nu(T>n)$ for all $t\ge 0$. An exponential tail on $T$ therefore forces the same exponential rate of convergence, up to a change in the leading constant. The paper then builds $T$ from drift and minorization data, proves an exponential tail bound for it, and combines these ingredients into explicit convergence bounds in total variation and in $V$-norm. The claim that matters for users is that for reversible chains with nonnegative eigenvalues, the sometimes difficult analysis of the transition operator's spectral gap can be replaced by the much more tractable tail of a random time.

Load-bearing premise

The load-bearing premise is that the chain is reversible and its transition operator has no negative eigenvalues, because the proof needs the sequence $\langle \mathbf{P}^t f,f\rangle_\pi$ to be nonincreasing; without nonnegativity of the spectrum, or without reversibility, the tail bound is not established and the paper notes analogous bounds can be much worse.

Editorial extensions

If this is right

  • If a reversible chain with nonnegative eigenvalues admits a strong random time whose tail decays like $A\rho^t$, the chain's distance from stationarity decays at the same rate $\rho$; the $L^2$ starting bound only changes the leading constant.
  • Drift and minorization data $(\lambda,K,\varepsilon,m)$ translate, through a closed-form recipe, into explicit total-variation bounds and stronger $V$-norm bounds with the same exponential rate.
  • The $m$-step minorization case is handled by the same probabilistic argument as $m=1$, with no need for a separate renewal-theoretic calculation.
  • For the nuclear pump Gibbs sampler, the guaranteed mixing time drops from 192 to 83 steps in total variation and from 212 to 111 steps in $V$-norm, compared with earlier quantitative methods.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The same tail-control principle should apply to other sources of strong random times, such as strong stationary times or coupling constructions, giving rate-preservation results beyond the drift-and-minorization setting.
  • For chains whose spectrum is not confined to $[0,1]$, the paper's example suggests the true convergence rate can be much slower than the strong-random-time tail; a natural test is whether a lazy modification, which makes eigenvalues nonnegative, is the cheapest way to recover the bound.
  • The factor-of-two improvement in the worked example may not be universal; benchmarking the recipe on exactly solvable finite chains would show how close the bounds typically come to the true spectral gap.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 5 minor

Summary. This paper proves quantitative convergence bounds for reversible Markov chains with nonnegative spectrum by introducing a general principle: any strong random time with measure ν directly controls the L2(π) distance from stationarity, through the tail sum in Theorem 1.2. The paper then couples this principle with a drift-and-minorization construction of strong random times, obtaining explicit total-variation bounds (Theorem 1.8) and V-norm bounds (Theorem 4.1). The central proofs are rigorous and self-contained apart from the numerical verification in Section 5. The paper applies the bounds to a nuclear-pump Gibbs sampler and reports a factor-of-two improvement over Rosenthal and Baxendale in Table 1, but the numerical constants underpinning that table are asserted from a procedure whose details are deferred to the author's PhD thesis.

Significance. Theorem 1.2 is an elegant and useful unification: it identifies the reversibility-plus-nonnegative-spectrum assumption as a direct mechanism by which strong random times control convergence, it recovers and strengthens Baxendale's result, and it handles m-step minorization on the same footing as m=1. The tail bound in Theorem 1.7 and the V-norm transfer in Theorem 4.1 are clean and appear to be new. If the numerical constants in Section 5 are certified, the factor-of-two improvement over existing bounds is a valuable practical demonstration. The proofs of Theorems 1.2, 1.3, 1.7, and 4.1 are internally consistent, and I found no gap in the central argument.

major comments (2)
  1. [Section 5, Lemma 5.1] The constants λ=0.61, K=3.05, ε=0.287, and the set C=[4.74,8.50] are the inputs to Table 1 and to the paper's headline factor-of-two comparison, but the proof of Lemma 5.1 does not provide a reproducible numerical procedure. It says to compute PV(x) numerically, set C by the inequality PV(x)>λV(x), set K=sup_C PV, and compute ε 'by the same method used in the proof of [33, Theorem 11]', with no grid, quadrature rule, tolerance, or error analysis. Since the state space is continuous and the inequalities in the drift/minorization definitions must hold for all x, pointwise numerical evaluation is not by itself a proof. Please supply a certified computation, for instance interval-arithmetic certificates or a public script with rigorous error bounds, or clearly label the constants as heuristic. As written, the strongest applied claim is conditional on an unverifiable numerical step.
  2. [Section 5, Lemma 5.1, step 1] The optimization over λ is described as 'for λ=0.01,0.02,...,0.99' followed by choosing the smallest ρ, but no justification is given that this finite grid exhausts the relevant range of λ, nor that the function ρ(λ) has no isolated minimum between grid points. If the numerical constants are to be load-bearing, the paper should either certify the search over λ or state that the reported value is only an upper bound obtained at the grid point λ=0.61. This is a local but consequential gap in the demonstration of the claimed improvement.
minor comments (5)
  1. [Definition 1.4 and Theorem 1.7] The drift condition is stated with λ<1 but not explicitly with λ≥0, while the formulas in Theorem 1.7 use log λ and therefore require λ>0. The intended domain is presumably 0≤λ<1; please state it explicitly or treat λ=0 as a separate case.
  2. [Footnote 1 and Section 5] The paper defers a technical construction and the detailed numerical verification to the author's PhD thesis [14]. For a journal version, either include these details or describe them in an appendix or supplementary material; at present the self-containedness of the manuscript is only partial.
  3. [Section 1.6] In the nearly periodic example, the notation K=(1+e)/2 uses e without defining it as the base of natural logarithms. Please add a definition or use the explicit constant.
  4. [Section 1.6] The term 'strongly aperiodic with β=1/2' is used before the constant β is defined. A brief definition would help the reader follow the aperiodicity discussion.
  5. [Section 5, Table 1] The caption or text could state explicitly that the row for Theorem 1.8 and the row for Theorem 4.1 use the same drift/minorization constants from Lemma 5.1; this is implied but making it explicit would aid reproducibility.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: Theorem 1.2 is proved from first principles; the thesis self-citations are ancillary, and the example bounds are genuine outputs of the stated formulas.

full rationale

The paper's main result, Theorem 1.2, is a direct theorem: given a strong random time T with measure ν, the L2(π) distance from stationarity is bounded by a tail sum of T, proved via the spectral representation of the reversible nonnegative-eigenvalue operator, the Radon-Nikodym derivative dν/dπ, and the summation-by-parts Lemma 2.2. The drift and minorization machinery in Algorithm 1.6 and Theorem 1.7 then bounds the tail of T in terms of the drift/minorization data, and Theorem 1.8 simply composes these independent results. No parameter is fitted to the target mixing-time bounds; the constants λ = 0.61, K = 3.05, and ε = 0.287 in Lemma 5.1 are numerical inputs computed from the transition kernel, and the reported τ values are outputs of the formulas in Theorems 1.8 and 4.1. The citations to the author's own thesis [14] are for a technical construction of the splitting probability space in footnote 1 and for an expanded exposition of the worked example in Section 5; these are ancillary, and the central derivation is self-contained. The numerical verification in Lemma 5.1 is less reproducible than the theoretical results, but that is a verification/correctness concern, not a circular reduction of the prediction to its inputs. The reversibility and nonnegative-spectrum assumption is an explicit scope condition, with the lazy-chain workaround noted, rather than a hidden circularity.

Assumptions & free parameters 5 free parameters · 4 assumptions · 0 invented entities

The central theorems rest on the spectral theorem and the definition of strong random times; no fitted parameters enter the main results. The only free parameters appear in the illustrative example of Section 5, where the drift function center, drift rate, drift bound, minorization constant, and small set are chosen or computed numerically to minimize the resulting bound. No new entities are postulated.

free parameters (5)
  • lambda (drift rate in example) = 0.61
    Chosen in Section 5 by numerically searching a grid to minimize the computed convergence rate rho; not derived analytically.
  • K (drift bound in example) = 3.05
    Numerically computed as sup_{x in C} PV(x) for the chosen C in Lemma 5.1 of Section 5.
  • epsilon (minorization constant in example) = 0.287
    Numerically computed minorization constant for the small set C in Section 5, following the method of [33, Theorem 11].
  • C (small set in example) = [4.74, 8.50]
    Small set determined numerically from the drift condition for lambda=0.61 in Lemma 5.1.
  • Center 6.5 of drift function V = 6.5
    The drift function V(x)=1+(x-6.5)^2 is chosen because the stationary mean is approximately 6.5 (Section 5); this is a modeling choice for the example, not a derived quantity.
assumptions (4)
  • standard math Spectral theorem for self-adjoint operators on L2(pi)
    Used in the proof of Theorem 1.2 to write <Pt f,f> as an integral over the spectral measure and to conclude monotonicity when the spectrum is in [0,1].
  • standard math Hahn decomposition theorem
    Used in the proof of Lemma 2.1 to prove uniqueness of the stationary distribution.
  • domain assumption The Gibbs samplers defined in Section 5 have the stated transition rules
    The example model is taken from references [12,36,23,33]; the paper does not re-derive the model.
  • domain assumption The drift and minorization conditions are the standard definitions used in the theorems
    Definitions 1.4 and 1.5 are standard; the theorems apply to chains satisfying them without further justification.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Quantitative convergence rates for reversible Markov chains via strong random times." pith.science (2026). https://pith.science/paper/6HPU7SSU

@misc{pith2026190806459,
  author       = {Pith},
  title        = {Pith review of: Quantitative convergence rates for reversible Markov chains via strong random times},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/6HPU7SSU}},
  note         = {Machine review of arXiv:1908.06459}
}
abstract

Let $(X_t)$ be a discrete time Markov chain on a general state space. It is well-known that if $(X_t)$ is aperiodic and satisfies a drift and minorization condition, then it converges to its stationary distribution $\pi$ at an exponential rate. We consider the problem of computing upper bounds for the distance from stationarity in terms of the drift and minorization data. Baxendale showed that these bounds improve significantly if one assumes that $(X_t)$ is reversible with nonnegative eigenvalues (i.e. its transition kernel is a self-adjoint operator on $L^2(\pi)$ with spectrum contained in $[0,1]$). We identify this phenomenon as a special case of a general principle: for a reversible chain with nonnegative eigenvalues, any strong random time gives direct control over the convergence rate. We formulate this principle precisely and deduce from it a stronger version of Baxendale's result. Our approach is fully quantitative and allows us to convert drift and minorization data into explicit convergence bounds. We show that these bounds are tighter than those of Rosenthal and Baxendale when applied to a well-studied example.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

37 extracted references · 24 canonical work pages

  1. [1]

    Aldous and P

    D. Aldous and P. Diaconis. Shuffling cards and stopping times. Amer. Math. Monthly , 93(5):333–348, 1986. doi:10.2307/2323590

    doi:10.2307/2323590 1986

  2. [2]

    Aldous and P

    D. Aldous and P. Diaconis. Strong uniform times and finite random walks. Adv. in Appl. Math., 8(1):69–97, 1987. doi:10.1016/0196-8858(87)90006-6

    doi:10.1016/0196-8858(87)90006-6 1987

  3. [3]

    K. B. Athreya and P. Ney. A new approach to the limit theory of recurrent Markov chains. Trans. Amer. Math. Soc. , 245:493–501, 1978. doi:10.2307/1998882

    doi:10.2307/1998882 1978

  4. [4]

    P. H. Baxendale. Renewal theory and computable convergence rates for geometri- cally ergodic Markov chains. Ann. Appl. Probab. , 15(1B):700–738, 2005. doi:10.1214/ 105051604000000710. QUANTITATIVE CONVERGENCE VIA STRONG RANDOM TIMES 25

    work page 2005

  5. [5]

    W. Bednorz. The Kendall theorem and its application to the geometric ergodicity of Markov chains. Applicationes Mathematicae , 40(2):129–165, 2013. URL: http://eudml.org/doc/ 279924

    work page 2013

  6. [6]

    Bednorz, K

    W. Bednorz, K. Latuszy´ nski, and R. Lata la. A regeneration proof of the central limit theorem for uniformly ergodic Markov chains. Electron. Commun. Probab. , 13:85–98, 2008. doi:10. 1214/ECP.v13-1354

    work page 2008

  7. [7]

    D. L. Cohn. Measure theory. Birkh¨ auser Advanced Texts: Basler Lehrb¨ ucher. [Birkh¨ auser Advanced Texts: Basel Textbooks]. Birkh¨ auser/Springer, New York, second edition, 2013. doi:10.1007/978-1-4614-6956-8

    doi:10.1007/978-1-4614-6956-8 2013

  8. [8]

    R. Douc, G. Fort, E. Moulines, and P. Soulier. Practical drift conditions for subgeo- metric rates of convergence. Ann. Appl. Probab. , 14(3):1353–1377, 2004. doi:10.1214/ 105051604000000323

    work page 2004

Show all 37 references
  1. [9]

    R. Douc, E. Moulines, and P. Soulier. Computable convergence rates for sub-geometric ergodic Markov chains. Bernoulli, 13(3):831–848, 2007. doi:10.3150/07-BEJ5162

    2007 doi

  2. [10]

    G. Fort. Computable bounds for V-geometric ergodicity of Markov transition kernels. Rapport de Recherche, Univ. J. Fourier, RR 1047-M, 2002. URL: http://math.univ-toulouse.fr/ ~gfort/Preprints/fort:2002.pdf

    2002

  3. [11]

    Fort and E

    G. Fort and E. Moulines. Polynomial ergodicity of Markov transition kernels. Stochastic Process. Appl., 103(1):57–99, 2003. doi:10.1016/S0304-4149(02)00182-5

    2003 doi

  4. [12]

    A. E. Gelfand and A. F. M. Smith. Sampling-based approaches to calculating marginal densi- ties. J. Amer. Statist. Assoc. , 85(410):398–409, 1990. URL: https://www.jstor.org/stable/ 2289776

    1990

  5. [13]

    S. F. Jarner and G. O. Roberts. Polynomial convergence rates of Markov chains. Ann. Appl. Probab., 12(1):224–247, 2002. doi:10.1214/aoap/1015961162

    2002

  6. [14]

    D. C. Jerison. The drift and minorization method for reversible Markov chains . PhD thesis, Stanford University, 2016. URL: http://www.math.tau.ac.il/~jerison/ thesis-regeneration.pdf

    2016

  7. [15]

    G. L. Jones and J. P. Hobert. Honest exploration of intractable probability distributions via Markov chain Monte Carlo. Statist. Sci. , 16(4):312–334, 2001. doi:10.1214/ss/1015346317

    2001

  8. [16]

    G. L. Jones and J. P. Hobert. Sufficient burn-in for Gibbs samplers for a hierarchical random effects model. Ann. Statist. , 32(2):784–817, 2004. doi:10.1214/009053604000000184

    2004 doi

  9. [17]

    Coupling from the past

    D. A. Levin and Y. Peres. Markov chains and mixing times . American Mathematical Society, Providence, RI, 2017. Second edition. With contributions by Elizabeth L. Wilmer. With a chapter on “Coupling from the past” by James G. Propp and David B. Wilson

    2017

  10. [18]

    R. B. Lund and R. L. Tweedie. Geometric convergence rates for stochastically ordered Markov chains. Math. Oper. Res. , 21(1):182–194, 1996. doi:10.1287/moor.21.1.182

    1996 doi

  11. [19]

    Marchev and J

    D. Marchev and J. P. Hobert. Geometric ergodicity of van Dyk and Meng’s algorithm for the multivariate Student’s t model. J. Amer. Statist. Assoc. , 99(465):228–238, 2004. doi: 10.1198/016214504000000223

    2004 doi

  12. [20]

    S. P. Meyn and R. L. Tweedie. Markov chains and stochastic stability . Communications and Control Engineering Series. Springer-Verlag London, Ltd., London, 1993. doi:10.1007/ 978-1-4471-3267-7

    1993

  13. [21]

    S. P. Meyn and R. L. Tweedie. Computable bounds for geometric convergence rates of Markov chains. Ann. Appl. Probab., 4(4):981–1011, 1994. URL: https://projecteuclid.org/euclid. aoap/1177004900

    1994

  14. [22]

    L. Miclo. On absorption times and Dirichlet eigenvalues. ESAIM Probab. Stat. , 14:117–150,

  15. [23]

    Mykland, L

    P. Mykland, L. Tierney, and B. Yu. Regeneration in Markov chain samplers.J. Amer. Statist. Assoc., 90(429):233–241, 1995. URL: https://www.jstor.org/stable/2291148

    1995

  16. [24]

    Nummelin

    E. Nummelin. A splitting technique for Harris recurrent Markov chains. Z. Wahrsch. Verw. Gebiete, 43(4):309–318, 1978. doi:10.1007/BF00534764

    1978 doi

  17. [25]

    Nummelin

    E. Nummelin. General irreducible Markov chains and nonnegative operators , volume 83 of Cambridge Tracts in Mathematics . Cambridge University Press, Cambridge, 1984. doi:10. 1017/CBO9780511526237

    1984

  18. [26]

    Nummelin and P

    E. Nummelin and P. Tuominen. Geometric ergodicity of Harris recurrent Markov chains with applications to renewal theory. Stochastic Process. Appl. , 12(2):187–202, 1982. doi: 10.1016/0304-4149(82)90041-2. 26 DANIEL C. JERISON

    1982 doi

  19. [27]

    I. Pak. Random walks on groups: Strong uniform time approach . PhD thesis, Harvard Uni- versity, 1997. URL: https://math.ucla.edu/~pak/papers/time57.pdf

    1997

  20. [28]

    Reed and B

    M. Reed and B. Simon. Methods of modern mathematical physics. I. Functional analysis . Academic Press, New York-London, 1972

    1972

  21. [29]

    D. Revuz. Markov chains, volume 11 of North-Holland Mathematical Library . North-Holland Publishing Co., Amsterdam, second edition, 1984

    1984

  22. [30]

    G. O. Roberts and J. S. Rosenthal. Geometric ergodicity and hybrid Markov chains. Electron. Comm. Probab., 2(2):13–25, 1997. doi:10.1214/ECP.v2-981

    1997 doi

  23. [31]

    G. O. Roberts and J. S. Rosenthal. General state space Markov chains and MCMC algorithms. Probab. Surv., 1:20–71, 2004. doi:10.1214/154957804100000024

    2004 doi

  24. [32]

    G. O. Roberts and R. L. Tweedie. Bounds on regeneration times and convergence rates for Markov chains. Stochastic Process. Appl., 80(2):211–229, 1999. doi:10.1016/S0304-4149(98) 00085-4

    1999 doi

  25. [33]

    J. S. Rosenthal. Minorization conditions and convergence rates for Markov chain Monte Carlo. J. Amer. Statist. Assoc. , 90(430):558–566, 1995. URL: https://www.jstor.org/stable/ 2291067

    1995

  26. [34]

    J. S. Rosenthal. Rates of convergence for Gibbs sampling for variance component models. Ann. Statist. , 23(3):740–761, 1995. doi:10.1214/aos/1176324619

    1995

  27. [35]

    J. S. Rosenthal. Quantitative convergence rates of Markov chains: a simple account. Electron. Comm. Probab., 7:123–128, 2002. doi:10.1214/ECP.v7-1054

    2002 doi

  28. [36]

    L. Tierney. Markov chains for exploring posterior distributions. Ann. Statist. , 22(4):1701– 1762, 1994. With discussion and a rejoinder by the author. doi:10.1214/aos/1176325750. Department of Mathematical Sciences, Tel A viv University, Tel A viv 69978, Israel E-mail address...

    1994

  29. [2010]

    doi:10.1051/ps:2008037

    doi

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.