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

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

Probability Seminar
Sep 2, 2015, 03:10 PM - 04:00 PM | 344 Evans Hall | Happening As Scheduled
David Aldous, Department of Statistics, U.C. Berkeley
A simple lemma bounds $s.d.(T)/\Ex 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...