Skip to main content
eScholarship
Open Access Publications from the University of California

Weak concentration for first passage percolation times on graphs and general increasing set-valued processes

Abstract

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
Current View