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 Academic Senate's Open Access Policy. Let us know how this access is important for you.

Main Content
Current View