Explicit laws of large numbers for random nearest-neighbour-type graphs

DOI10.1239/AAP/1183667613zbMATH Open1122.60012arXivmath/0603559OpenAlexW3100151049MaRDI QIDQ3590741FDOQ3590741

Authors: Andrew R. Wade 

Publication date: 3 September 2007

Published in: Advances in Applied Probability (Search for Journal in Brave)

Abstract: Under the unifying umbrella of a general result of Penrose & Yukich [Ann. Appl. Probab., (2003) 13, 277--303] we give laws of large numbers (in the $L^p$ sense) for the total power-weighted length of several nearest-neighbour type graphs on random point sets in $R^d$, $dinN$. Some of these results are known; some are new. We give limiting constants explicitly, where previously they have been evaluated in less generality or not at all. The graphs we consider include the k-nearest neighbours graph, the Gabriel graph, the minimal directed spanning forest, and the on-line nearest-neighbour graph.

Full work available at URL: https://arxiv.org/abs/math/0603559

Recommendations

• Asymptotic theory for the multidimensional random on-line nearest-neighbour graph
• Limit theory for the random on‐line nearest‐neighbor graph
• Weak laws of large numbers in geometric probability
• A strong law of large numbers for random biased connected graphs
• The law of the iterated logarithm for the total length of the nearest neighbor graph

zbMATH Keywords

law of large numbersspanning forestnearest-neighbour-type graphspatial network evolution

Mathematics Subject Classification ID

Geometric probability and stochastic geometry (60D05) (L^p)-limit theorems (60F25)

Cites Work

• Central limit theorems for some graphs in computational geometry.
• Multivariate spatial central limit theorems with applications to percolation and spatial graphs
• Random Geometric Graphs
• Title not available (Why is that?)
• Graph-theoretic measures of multivariate association and prediction
• Weak laws of large numbers in geometric probability
• Probability theory of classical Euclidean optimization problems
• Graph-theoretic procedures for dimension identification
• On the Distribution of the Number of Admissible Points in a Vector Random Sample
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• GEOMETRIC PROXIMITY GRAPHS FOR IMPROVING NEAREST NEIGHBOR METHODS IN INSTANCE-BASED LEARNING AND DATA MINING
• Sums of functions of nearest neighbor distances, moment bounds, limit theorems and a goodness of fit test
• On central limit theorems in geometrical probability
• The central limit theorem for weighted minimal spanning trees on random points
• On the fraction of random points by specified nearest-neighbour interrelations and degree of attraction
• Asymptotic moments of near–neighbour distance distributions
• A proof of the Gamma test
• On a random directed spanning tree
• Scaling universalities of \(k\)th-nearest neighbor distances on closed manifolds
• Random minimal directed spanning trees and Dickman-type distributions
• On the homogeneous planar Poisson point process
• On the total length of the random minimal directed spanning tree
• Title not available (Why is that?)
• Almost sure convergence of certain slowly changing symmetric one- and multi-sample statistics

Cited In (22)

• A strong law of large numbers for random biased connected graphs
• Asymptotics for Euclidean functionals of mixing processes
• On the number of weakly connected subdigraphs in random \(k\)NN digraphs
• Strong law of large numbers on graphs and groups
• Strong laws for Euclidean graphs with general edge weights
• Law of the iterated logarithm for random graphs
• The law of the iterated logarithm for the total length of the nearest neighbor graph
• Laws of large numbers in stochastic geometry with statistical applications
• Limit theory for the random on‐line nearest‐neighbor graph
• Multivariate normal approximation in geometric probability
• A detailed investigation into near degenerate exponential random graphs
• Asymptotic theory for the multidimensional random on-line nearest-neighbour graph
• A boundary corrected expansion of the moments of nearest neighbor distributions
• Mutual and shared neighbor probabilities: finite- and infinite-dimensional results
• Quantitative two-scale stabilization on the Poisson space
• A law of large numbers for nearest neighbour statistics
• Multivariate goodness-of-fit on flat and curved spaces via nearest neighbor distances
• Limit theory for point processes in manifolds
• Title not available (Why is that?)
• Normal approximation for statistics of Gibbsian input in geometric probability
• Criticality of the exponential rate of decay for the largest nearest-neighbor link in random geometric graphs
• Limit theorems for random spatial drainage networks

This page was built for publication: Explicit laws of large numbers for random nearest-neighbour-type graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3590741)