Limit theory for the random on-line nearest-neighbour graph

Penrose, Mathew D. and Wade, Andrew R. (2007) Limit theory for the random on-line nearest-neighbour graph. Random Structures and Algorithms, 32 (2). pp. 125-156. ISSN 1042-9832 (https://doi.org/10.1002/rsa.20185)

Preview

Text. Filename: strathprints013396.pdf Accepted Author Manuscript Download (519kB)| Preview

Abstract

In the on-line nearest-neighbour graph (ONG), each point after the first in a sequence of points in Rd is joined by an edge to its nearest neighbour amongst those points that precede it in the sequence. We study the large-sample asymptotic behaviour 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 centred 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-neighbour (directed) graph on uniform random points in the unit interval.

• Share and Export
  

  ASCII CitationEP3 XMLRIS (EndNote Online, Zotero, Ref manager, etc)HTML CitationOpenURL ContextObject in SpanRIOXX2 XMLRDF+N-TriplesBibTeXMPEG-21 DIDLMODSRefWorksRDF+N3Multiline CSVJSONDublin CoreData Cite XMLSimple MetadataEndNoteAtomMETSOpenURL ContextObjectRDF+XMLRefer
• Item metadata

  Item type:	Article
  ID code:	13396
  Dates:	Date Event 13 August 2007 Published
  Subjects:	Science > Mathematics > Probabilities. Mathematical statistics Science > Mathematics
  Department:	Faculty of Science > Mathematics and Statistics
  Depositing user:	Mrs Carolynne Westwood
  Date deposited:	12 Nov 2009 14:14
  Last modified:	12 Dec 2024 02:20
  URI:	https://strathprints.strath.ac.uk/id/eprint/13396