Some inequalities for reversible Markov chains and branching random walks via spectral optimization

DOI10.1214/21-AIHP1208zbMATH Open1493.60112arXiv1908.08525OpenAlexW4288257318MaRDI QIDQ2157453FDOQ2157453

Authors: Jonathan Hermon 

Publication date: 22 July 2022

Published in: Annales de l'Institut Henri Poincaré. Probabilités et Statistiques (Search for Journal in Brave)

Abstract: We present results relating mixing times to the intersection time of branching random walk (BRW) in which the logarithm of the expected number of particles grows at rate of the spectral-gap $mathrmgap$ . This is a finite state space analog of a critical branching process. Namely, we show that the maximal expected hitting time of a state by such a BRW is up to a universal constant larger than the $L_{infty}$ mixing-time, whereas under transitivity the same is true for the intersection time of two independent such BRWs. Using the same methodology, we show that for a sequence of reversible Markov chains, the $L_{infty}$ mixing-times $t_{mathrmmix}^{(infty)}$ are of smaller order than the maximal hitting times $t_{mathrmhit}$ iff the product of the spectral-gap and $t_{mathrmhit}$ diverges, by establishing the inequality $t_{mathrmmix}^{(infty)}lefrac1mathrmgaplog(e{t}_{mathrmhit}cdotmathrmgap)$. This resolves a conjecture of Aldous and Fill (Reversible Markov chains and random walks on graphs, Open Problem 14.12) asserting that under transitivity the condition that $t_{mathrmhit}ggfrac1mathrmgap$ implies mean-field behavior for the coalescing time of coalescing random walks.

Full work available at URL: https://arxiv.org/abs/1908.08525

Recommendations

• Intersection and mixing times for reversible chains
• Mixing and hitting times for finite Markov chains
• Tight inequalities among set hitting times in Markov chains
• Convergence of some time inhomogeneous Markov chains via spectral techniques
• Meeting times for independent Markov chains

zbMATH Keywords

hitting timesmixing timesvertex-transitive graphsbranching random walkspectral optimizationcoalescing random walkspectral-gapintersection times

Mathematics Subject Classification ID

Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Sums of independent random variables; random walks (60G50) Branching processes (Galton-Watson, birth-and-death, etc.) (60J80)

Cites Work

• Probability on trees and networks
• Markov chain models - rarity and exponentiality
• Mean field conditions for coalescing random walks
• On sensitivity of uniform mixing times
• On the coalescence time of reversible random walks
• Threshold limits for cover times
• The cutoff phenomenon for ergodic Markov processes
• Some Inequalities for Reversible Markov Chains
• Mixing times are hitting times of large sets
• Hitting times for random walks on vertex-transitive graphs
• A spectral characterization for concentration of the cover time
• Mixing and hitting times for finite Markov chains
• Sensitivity of mixing times
• Intersection and mixing times for reversible chains
• Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
• Total variation cutoff in birth-and-death chains
• The critical branching Markov chain is transient
• Characterization of cutoff for reversible Markov chains
• A technical report on hitting times, mixing and cutoff
• On sensitivity of mixing times and cutoff
• A characterization of \(L_{2}\) mixing and hypercontractivity via hitting times and maximal inequalities

Cited In (1)

• Mean field behavior during the big bang regime for coalescing random walks

This page was built for publication: Some inequalities for reversible Markov chains and branching random walks via spectral optimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2157453)