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

MaRDI QIDQ2829201zbMATHFDO

Authors David Aldous

Publication date 27 October 2016

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

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)

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$.

Recommendations

• Subdiffusive concentration in first passage percolation
• Exponential concentration for first passage percolation through modified Poincaré inequalities
• Monotonicity in first-passage percolation
• On the concentration and the convergence rate with a moment condition in first passage percolation
• On the Markov transition kernels for first passage percolation on the ladder

Cited in

(4)

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

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)