- Main
Weak Concentration for First Passage Percolation Times on Graphs and General Increasing Set-valued Processes
Published Web Location
https://doi.org/10.30757/alea.v13-35Abstract
A simple lemma bounds s.d.(T )/ET 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)/EX is small if and only if Ξ/EX is small, where Ξ is the maximal edge-traversal time in the percolation path attaining X.
Many UC-authored scholarly publications are freely available on this site because of the UC's open access policies. Let us know how this access is important for you.
Main Content
Enter the password to open this PDF file:
-
-
-
-
-
-
-
-
-
-
-
-
-
-