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

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

2007-02-14

arxiv.org/abs/math/0702414v2

Stochastic Processes and their Applications, Vol. 119 (2009), no. 6, p. 1889-1911

Mathematics

Probability

25 pages; v2: substantial revision, change in title, central limit theorem present in v1 removed due to a gap

Scientific paper

10.1016/j.spa.2008.09.006

The on-line nearest-neighbour graph on a sequence of $n$ uniform random points in $(0,1)^d$ ($d \in \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 $\alpha \in (0,d/2]$, we prove $O(\max \{n^{1-(2\alpha/d)}, \log n \})$ upper bounds on the variance. On the other hand, we give an $n \to \infty$ large-sample convergence result for the total power-weighted edge-length when $\alpha > d/2$. We prove corresponding results when the underlying point set is a Poisson process of intensity $n$.

Affiliated with

Also associated with

No associations

Rating

Asymptotic theory for the multidimensional random on-line nearest-neighbour graph does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Asymptotic theory for the multidimensional random on-line nearest-neighbour graph, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Asymptotic theory for the multidimensional random on-line nearest-neighbour graph will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-209962