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

zbMATH Open1350.60098arXiv1604.06418MaRDI QIDQ2829201FDOQ2829201

David Aldous

Publication date: 27 October 2016

Published in: ALEA. Latin American Journal of Probability and Mathematical Statistics (Search for Journal in Brave)

Abstract: A simple lemma bounds $mathrms.d.(T)/mathbbET$ 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 $mathrms.d.(X)/mathbbEX$ is small if and only if $Xi/mathbbEX$ is small, where $Xi$ is the maximal edge-traversal time in the percolation path attaining $X$.

Full work available at URL: https://arxiv.org/abs/1604.06418

zbMATH Keywords

Markov processcouplingfirst-passage percolationset-valued processesweak concentration inequality

Mathematics Subject Classification ID

Interacting random processes; statistical mechanics type models; percolation theory (60K35) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Continuous-time Markov processes on discrete state spaces (60J27)

Cited In (4)

• Covering a compact space by fixed-radius or growing random balls
• A framework for imperfectly observed networks
• THE NEAREST UNVISITED VERTEX WALK ON RANDOM GRAPHS
• A conversation with David J. Aldous

This page was built for publication: Weak concentration for first passage percolation times on graphs and general increasing set-valued processes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2829201)