Kendall, Wilfrid S. (2008) Networks and Poisson line patterns : fluctuation asymptotics. [Report]

Preview

PDF WRAP_Kendall_Kendall-2009b.pdf - Accepted Version - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader Download (152Kb)

Abstract

In [1] it was shown how to construct networks connecting arbitrary configurations xn of n cities in a square of area n which for example (i) involve only εn more total network length than the Euclidean Steiner tree connecting all n cities, and yet (ii) establish a network connection length between two randomly chosen cities which is on average only O(log n) more than average Euclidean connection length [1, Theorem 3, version (b)]. Moreover, under a certain quantitative equidistribution condition on the city locations xn (which can be phrased either analytically or in terms of a truncated Wasserstein coupling between a randomly chosen city and the uniform distribution on the square), a complementary result shows that for O(n) total connection length the average network connection length must have an excess over the average Euclidean connection length of at least Ω(√log n) [1, Theorem 5]. The methods of proof involve stochastic geometry: in the case of the lower bound [1, Theorem 5] the idea is to associate the uniform choice of two cities with approximately uniform random lines, and then to use simple ideas from stereology. In the case of the upper bound [1, Theorem 3] one augments the Euclidean Steiner tree by a sparse Poisson line process, to obtain good long-distance communication, and adds an additional relatively infinitesimal amount of additional connectivity, to ensure efficient passage from Steiner tree to line process network.

Item Type:	Report
Subjects:	Q Science > QA Mathematics
Divisions:	Faculty of Science > Statistics
Library of Congress Subject Headings (LCSH):	System analysis
Series Name:	Oberwolfach Reports
Publisher:	European Mathematical Society Publishing House
Place of Publication:	Zürich
Date:	2008
Volume:	Vol.5
Number:	No.4
Status:	Peer Reviewed
Publication Status:	Published
Access rights to Published version:	Restricted or Subscription Access
References:	[1] David J. Aldous and Wilfrid S. Kendall. Short-length routes in low-cost networks via Poisson line patterns. Adv. in Appl. Probab., 40(1):1{21, 2008. [2] Karoly J. Boroczky and Rolf Schneider. The mean width of circumscribed random polytopes, 2008. [3] P. Carmona, F. Petit, and M. Yor. Sur les fonctionnelles exponentielles de certains processus de Levy. Stochastics Stochastics Rep., 47(1-2):71{101, 1994. [4] Daniel Dufresne. The distribution of a perpetuity, with applications to risk theory and pension funding. Scand. Actuar. J., (1-2):39{79, 1990. [5] Rolando Rebolledo. Central limit theorems for local martingales. Z. Wahrsch. Verw. Gebiete, 51(3):269{286, 1980. [6] A. Renyi and R. Sulanke. Zufallige konvexe Polygone in einem Ringgebiet. Z. Wahrschein- lichkeitstheorie und Verw. Gebiete, 9:146{157, 1968. [7] Marc Yor. On some exponential functionals of Brownian motion. Adv. in Appl. Probab., 24(3):509{531, 1992.
URI:	http://wrap.warwick.ac.uk/id/eprint/38313

Request changes to a record

Actions (login required)

View Item