Mathew D. Penrose
Limit theory for the random on-line nearest-neighbor graph
Penrose, Mathew D.; Wade, Andrew R.
Abstract
In the on-line nearest-neighbor graph (ONG), each point after the first in a sequence of points in ℝd is joined by an edge to its nearest neighbor amongst those points that precede it in the sequence. We study the large-sample asymptotic behavior of the total power-weighted length of the ONG on uniform random points in (0,1)d. In particular, for d = 1 and weight exponent α > 1/2, the limiting distribution of the centered total weight is characterized by a distributional fixed-point equation. As an ancillary result, we give exact expressions for the expectation and variance of the standard nearest-neighbor (directed) graph on uniform random points in the unit interval.
Citation
Penrose, M. D., & Wade, A. R. (2008). Limit theory for the random on-line nearest-neighbor graph. Random Structures and Algorithms, 32(2), 125-156. https://doi.org/10.1002/rsa.20185
Journal Article Type | Article |
---|---|
Publication Date | Mar 1, 2008 |
Deposit Date | Oct 4, 2012 |
Journal | Random Structures and Algorithms |
Print ISSN | 1042-9832 |
Publisher | Wiley |
Peer Reviewed | Peer Reviewed |
Volume | 32 |
Issue | 2 |
Pages | 125-156 |
DOI | https://doi.org/10.1002/rsa.20185 |
Keywords | Nearest-neighbor graph,Spatial network evolution, Weak convergence, Fixed-point equation, Divide-and-conquer. |
You might also like
Iterated-logarithm laws for convex hulls of random walks with drift
(2023)
Journal Article
Passage-times for partially-homogeneous reflected random walks on the quadrant
(2023)
Journal Article
Deposition, diffusion, and nucleation on an interval
(2022)
Journal Article
Cutpoints of non-homogeneous random walks
(2022)
Journal Article
Reflecting random walks in curvilinear wedges
(2021)
Book Chapter
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search