Meeting times of Markov chains via singular value decomposition

2024/06/07 by van Belle, Thomas, Klimovsky, Anton
#05C80 #05C81 #47A55 #60B20 #60J10 #60K35 #FOS: Mathematics #Probability (math.PR)

paper · doi:10.48550/arxiv.2406.04958

Abstract

We suggest a non-asymptotic matrix perturbation-theoretic approach to get sharp bounds on the expected meeting time of random walks on large (possibly random) graphs. We provide a formula for the expected meeting time in terms of the singular value decomposition of the diagonally killed generator of a pair of independent random walks, which we view as a perturbation of the generator. Employing a rank-one approximation of the diagonally killed generator as the proof of concept, we work out sharp bounds on the expected meeting time of simple random walks on sufficiently dense Erdős-Rényi random graphs.

Related

• The Meeting Time of Multiple Random Walks
• On the Meeting Time for Two Random Walks on a Regular Graph
• Approximating Laplace transforms of meeting times for some symmetric Markov chains
• Meeting, coalescence and consensus time on random directed graphs
• Random walks on graphs: new bounds on hitting, meeting, coalescing and\n returning