We consider first-passage percolation on segment processes and provide concentration results concerning moderate deviations of shortest-path lengths from a linear function in the distance of their endpoints. The proofs are based on a martingale technique developed by [H. Kesten, Ann. Appl. Probab. 3 (1993) 296–338.] for an analogous problem on the lattice. Our results are applicable to graph models from stochastic geometry. For example, they imply that the time constant in Poisson−Voronoi and Poisson−Delaunay tessellations is strictly greater than 1. Furthermore, applying the framework of Howard and Newman, our results can be used to study the geometry of geodesics in planar shortest-path trees.
Accepté le :
DOI : 10.1051/ps/2016012
Mots-clés : Random segment process, first-passage percolation, moderate deviation, shortest-path
@article{PS_2016__20__261_0,
author = {Hirsch, Christian and Neuh\"auser, David and Schmidt, Volker},
title = {Moderate deviations for shortest-path lengths on random segment processes},
journal = {ESAIM: Probability and Statistics},
pages = {261--292},
publisher = {EDP-Sciences},
volume = {20},
year = {2016},
doi = {10.1051/ps/2016012},
mrnumber = {3528627},
zbl = {1384.60040},
language = {en},
url = {http://www.numdam.org/articles/10.1051/ps/2016012/}
}
TY - JOUR AU - Hirsch, Christian AU - Neuhäuser, David AU - Schmidt, Volker TI - Moderate deviations for shortest-path lengths on random segment processes JO - ESAIM: Probability and Statistics PY - 2016 SP - 261 EP - 292 VL - 20 PB - EDP-Sciences UR - http://www.numdam.org/articles/10.1051/ps/2016012/ DO - 10.1051/ps/2016012 LA - en ID - PS_2016__20__261_0 ER -
%0 Journal Article %A Hirsch, Christian %A Neuhäuser, David %A Schmidt, Volker %T Moderate deviations for shortest-path lengths on random segment processes %J ESAIM: Probability and Statistics %D 2016 %P 261-292 %V 20 %I EDP-Sciences %U http://www.numdam.org/articles/10.1051/ps/2016012/ %R 10.1051/ps/2016012 %G en %F PS_2016__20__261_0
Hirsch, Christian; Neuhäuser, David; Schmidt, Volker. Moderate deviations for shortest-path lengths on random segment processes. ESAIM: Probability and Statistics, Tome 20 (2016), pp. 261-292. doi : 10.1051/ps/2016012. http://www.numdam.org/articles/10.1051/ps/2016012/
D.J. Aldous, Which connected spatial networks on random points have linear route-lengths? Preprint arXiv:0911.5296 (2009).
, and , Markov paths on the Poisson-Delaunay graph with applications to routeing in mobile networks. Adv. Appl. Probab. 32 (2000) 1–18. | DOI | MR | Zbl
, and , Semi-infinite paths of the 2D-radial spanning tree. Adv. Appl. Probab. 47 (2013) 814–844. | Zbl
and , Exponential concentration for first passage percolation through modified Poincaré inequalities. Ann. Inst. Henri Poincaré, Probab. Stat. 44 (2008) 544–573. | DOI | Numdam | MR | Zbl
, and , On concentration of self-bounding functions. Electron. J. Probab. 14 (2009) 1884–1899. | DOI | MR | Zbl
N. Chenavier and O. Devillers, Stretch factor of long paths in a planar Poisson−Delaunay triangulation. Preprint (2015).
S.N. Chiu, D. Stoyan, W.S. Kendall and J. Mecke, Stochastic Geometry and its Applications. J. Wiley & Sons, Chichester, 3rd edition (2013). | MR
and , The 2D-directed spanning forest is almost surely a tree. Random Structures & Algorithms 42 (2013) 59–72. | DOI | MR | Zbl
and , Descending chains, the lilypond model, and mutual-nearest-neighbour matching. Adv. Appl. Probab. 37 (2005) 604–628. | DOI | MR | Zbl
and , Moderate deviations for the chemical distance in Bernoulli percolation. Latin Amer. J. Probab. Math. Statist. 7 (2010) 171–191. | MR | Zbl
, and , Parametric distributions of connection lengths for the efficient analysis of fixed access networks. Ann. Telecommun. 66 (2011) 103–118. | DOI
and , Second-order properties of the point process of nodes in a stationary Voronoi tessellation. Math. Nachr. 281 (2008) 350–375. | DOI | MR | Zbl
, , and , Asymptotic properties of Euclidean shortest-path trees in random geometric graphs. Statist. Probab. Lett. 107 (2015) 122–130. | DOI | MR | Zbl
, , and , First-passage percolation on random geometric graphs and an application to shortest-path trees. Adv. Appl. Probab. 47 (2015) 328–354. | DOI | MR | Zbl
and , Euclidean models of first-passage percolation. Probab. Theory Related Fields 108 (1997) 153–170. | DOI | MR | Zbl
and , Geodesics and spanning trees for Euclidean first-passage percolation. Ann. Probab. 29 (2001) 577–623. | DOI | MR | Zbl
D. Illian, P. Penttinen, H. Stoyan and D. Stoyan, Statistical Analysis and Modelling of Spatial Point Patterns. J. Wiley & Sons, Chichester (2008). | MR | Zbl
, On the speed of convergence in first-passage percolation. Ann. Appl. Probab. 3 (1993) 296–338. | DOI | MR | Zbl
and , Geodesics in two-dimensional first-passage percolation. Ann. Probab. 24 (1996) 399–410. | DOI | MR | Zbl
, and , Domination by product measures. Ann. Probab. 25 (1997) 71–95. | DOI | MR | Zbl
C. McDiarmid, Concentration. In Probabilistic Methods for Algorithmic Discrete Mathematics. Edited by M. Habib, C. McDiarmid, J. Ramirez-Alfonsin and B. Reed. Springer, Berlin (1998) 195–248. | MR | Zbl
D. Neuhäuser, C. Hirsch, C. Gloaguen and V. Schmidt, A parametric copula approach for modelling shortest-path trees in telecommunication networks. In Analytical and Stochastic Modeling Techniques and Applications, edited by A. Dudin and K. Turck. Vol. 7984 of Lect. Notes Comput. Sci. Springer, Berlin (2013) 324–336. | Zbl
and , Divergence of shape fluctuations in two dimensions. Ann. Probab. 23 (1995) 977–1005. | MR | Zbl
, Multitype shape theorems for first-passage percolation models. Adv. Appl. Probab. 39 (2007) 53–76. | DOI | MR | Zbl
, Asymptotics for first-passage times on Delaunay triangulations. Comb., Probab. Comput. 20 (2011) 435–453. | DOI | MR | Zbl
R. Schneider and W. Weil, Stochastic and Integral Geometry. Springer, Berlin (2008). | MR | Zbl
M.Q. Vahidi-Asl and J.C. Wierman, First-passage percolation on the Voronoi tessellation and Delaunay triangulation. In Random Graphs’ 87, edited by M. Karoński, J. Jaworski and A. Ruciński. J. Wiley & Sons, Chichester (1990) 341–359. | MR | Zbl
, and , Scaling limits for shortest path lengths along the edges of stationary tessellations. Adv. Appl. Probab. 42 (2010) 936–952. | DOI | MR | Zbl
Cité par Sources :
