Weak Concentration for First Passage Percolation Times on Graphs and General Increasing Set-valued Processes

2016/04/21 by Aldous, David J.
#60J27 #FOS: Mathematics #Probability (math.PR)

paper · doi:10.48550/arxiv.1604.06418

Abstract

A simple lemma bounds s.d.(T)/𝔼 T for hitting times T in Markov chains with a certain strong monotonicity property. We show how this lemma may be applied to several increasing set-valued processes. Our main result concerns a model of first passage percolation on a finite graph, where the traversal times of edges are independent Exponentials with arbitrary rates. Consider the percolation time X between two arbitrary vertices. We prove that s.d.(X)/𝔼 X is small if and only if Ξ/𝔼 X is small, where Ξ is the maximal edge-traversal time in the percolation path attaining X.

Related

• Exponential concentration for First Passage Percolation through modified Poincare inequalities
• On the concentration and the convergence rate with a moment condition in first passage percolation
• Strict inequality between the time constants of first-passage percolation and directed first-passage percolation
• Monotonicity in first-passage percolation
• Uniform fluctuation and wandering bounds in first passage percolation