Asymptotic theory for the multidimensional random on-line nearest-neighbour graph

Wade, Andrew R.

Abstract

The on-line nearest-neighbour graph on a sequence of n uniform random points in (0,1)d (d∈N) joins each point after the first to its nearest neighbour amongst its predecessors. For the total power-weighted edge-length of this graph, with weight exponent α∈(0,d/2], we prove O(max{n1−(2α/d),logn}) upper bounds on the variance. On the other hand, we give an n→∞ large-sample convergence result for the total power-weighted edge-length when α>d/2. We prove corresponding results when the underlying point set is a Poisson process of intensity n.

Citation

Wade, A. R. (2009). Asymptotic theory for the multidimensional random on-line nearest-neighbour graph. Stochastic Processes and their Applications, 119(6), 1889-1911. https://doi.org/10.1016/j.spa.2008.09.006

• Journal Article Type: Article
• Publication Date: Jun 1, 2009
• Deposit Date: Oct 4, 2012
• Publicly Available Date: Jan 31, 2013
• Journal: Stochastic Processes and their Applications
• Print ISSN: 0304-4149
• Electronic ISSN: 1879-209X
• Publisher: Elsevier
• Peer Reviewed: Peer Reviewed
• Volume: 119
• Issue: 6
• Pages: 1889-1911
• DOI: https://doi.org/10.1016/j.spa.2008.09.006
• Keywords: Random spatial graphs, Network evolution, Variance asymptotics, Martingale differences.
• Public URL: https://durham-repository.worktribe.com/output/1495702