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

DOI10.1214/21-AIHP1208MaRDI QIDQ2157453zbMATH OpenOpenAlexFDO

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)

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

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)

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.

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

Cites work

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

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)