Logo

Mathematical Sciences Research Institute

Home » UCB Probability Seminar: Weak Concentration for First Passage Percolation Times on Graphs and General Increasing Set-valued Processes

Seminar

UCB Probability Seminar: Weak Concentration for First Passage Percolation Times on Graphs and General Increasing Set-valued Processes September 02, 2015 (03:00 PM PDT - 04:00 PM PDT)
Parent Program: --
Location: 344 Evans Hall UCB
Speaker(s) David Aldous (University of California, Berkeley)
Description No Description
Video
No Video Uploaded
Abstract/Media

A simple lemma bounds s.d.(T)/\ExT 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)/\ExX is small if and only if Ξ/\ExX is small, where Ξ is the maximal edge-traversal time in the percolation path attaining X.

No Notes/Supplements Uploaded No Video Files Uploaded