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

A simple lemma bounds $\mathrm{s}\mathrm{.}\mathrm{d}\mathrm{.}(T)\mathrm{/}\mathbb{E}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 time $X$ between two arbitrary vertices. We prove that $\mathrm{s}\mathrm{.}\mathrm{d}\mathrm{.}(X)\mathrm{/}\mathbb{E}X$ is small if and only if $\mathrm{\Xi }\mathrm{/}\mathbb{E}X$ is small, where $\mathrm{\Xi }$ is the maximal edge-traversal time in the percolation path attaining $X$.