Moderate deviations for shortest-path lengths on random segment processes

Hirsch, Christian; Neuhäuser, David; Schmidt, Volker

ESAIM: Probability and Statistics, Tome 20 (2016), pp. 261-292.

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.

D.J. Aldous, Which connected spatial networks on random points have linear route-lengths? Preprint arXiv:0911.5296 (2009).

F. Baccelli, K. Tchoumatchenko and S. Zuyev, Markov paths on the Poisson-Delaunay graph with applications to routeing in mobile networks. Adv. Appl. Probab. 32 (2000) 1–18. | DOI | MR | Zbl

F. Baccelli, D. Coupier and V. Tran, Semi-infinite paths of the 2D-radial spanning tree. Adv. Appl. Probab. 47 (2013) 814–844. | Zbl

M. Benaïm and R. Rossignol, Exponential concentration for first passage percolation through modified Poincaré inequalities. Ann. Inst. Henri Poincaré, Probab. Stat. 44 (2008) 544–573. | DOI | Numdam | MR | Zbl

S. Boucheron, G. Lugosi and P. Massart, 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

D. Coupier and V.C. Tran, The 2D-directed spanning forest is almost surely a tree. Random Structures & Algorithms 42 (2013) 59–72. | DOI | MR | Zbl

D.J. Daley and G. Last, Descending chains, the lilypond model, and mutual-nearest-neighbour matching. Adv. Appl. Probab. 37 (2005) 604–628. | DOI | MR | Zbl

O. Garet and R. Marchand, Moderate deviations for the chemical distance in Bernoulli percolation. Latin Amer. J. Probab. Math. Statist. 7 (2010) 171–191. | MR | Zbl

C. Gloaguen, F. Voss and V. Schmidt, Parametric distributions of connection lengths for the efficient analysis of fixed access networks. Ann. Telecommun. 66 (2011) 103–118. | DOI

L. Heinrich and L. Muche, Second-order properties of the point process of nodes in a stationary Voronoi tessellation. Math. Nachr. 281 (2008) 350–375. | DOI | MR | Zbl

C. Hirsch, D. Neuhäuser, C. Gloaguen and V. Schmidt, Asymptotic properties of Euclidean shortest-path trees in random geometric graphs. Statist. Probab. Lett. 107 (2015) 122–130. | DOI | MR | Zbl

C. Hirsch, D. Neuhäuser, C. Gloaguen and V. Schmidt, First-passage percolation on random geometric graphs and an application to shortest-path trees. Adv. Appl. Probab. 47 (2015) 328–354. | DOI | MR | Zbl

C. Howard and C. Newman, Euclidean models of first-passage percolation. Probab. Theory Related Fields 108 (1997) 153–170. | DOI | MR | Zbl

C. Howard and C. Newman, 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

H. Kesten, On the speed of convergence in first-passage percolation. Ann. Appl. Probab. 3 (1993) 296–338. | DOI | MR | Zbl

C. Licea and C.M. Newman, Geodesics in two-dimensional first-passage percolation. Ann. Probab. 24 (1996) 399–410. | DOI | MR | Zbl

T.M. Liggett, R.H. Schonmann and A.M. Stacey, 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

C.M. Newman and M.S.T. Piza, Divergence of shape fluctuations in two dimensions. Ann. Probab. 23 (1995) 977–1005. | MR | Zbl

L. Pimentel, Multitype shape theorems for first-passage percolation models. Adv. Appl. Probab. 39 (2007) 53–76. | DOI | MR | Zbl

L. Pimentel, 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

F. Voss, C. Gloaguen and V. Schmidt, Scaling limits for shortest path lengths along the edges of stationary tessellations. Adv. Appl. Probab. 42 (2010) 936–952. | DOI | MR | Zbl