Random minimal directed spanning trees and Dickman-type distributions
Authors:
- Mathew D. PenroseMPMathew D. Penrose
- Andrew R. WadeAWAndrew R. Wade
- 1 September 2004
- journal article
- Published by Cambridge University Press (CUP) in Advances in Applied Probability
- Vol. 36 (3) , 691-714
Abstract
In Bhatt and Roy's minimal directed spanning tree construction for n random points in the unit square, all edges must be in a south-westerly direction and there must be a directed path from each vertex to the root placed at the origin. We identify the limiting distributions (for large n) for the total length of rooted edges, and also for the maximal length of all edges in the tree. These limit distributions have been seen previously in analysis of the Poisson-Dirichlet distribution and elsewhere; they are expressed in terms of Dickman's function, and their properties are discussed in some detail.Keywords
This publication has 16 references indexed in Scilit:
- On a random directed spanning treeAdvances in Applied Probability, 2004
- Weak laws of large numbers in geometric probabilityThe Annals of Applied Probability, 2003
- Density approximation and exact simulation of random variables that are solutions of fixed-point equationsAdvances in Applied Probability, 2002
- Probabilistic Analysis of MULTIPLE QUICK SELECTAlgorithmica, 1998
- Perpetuities with thin tailsAdvances in Applied Probability, 1996
- On the Asymptotic Distribution of Large Prime FactorsJournal of the London Mathematical Society, 1993
- On the distribution of points in a poisson dirichlet processJournal of Applied Probability, 1988
- The stationary distribution of the infinitely-many neutral alleles diffusion modelJournal of Applied Probability, 1976
- On the Distribution of the Number of Admissible Points in a Vector Random SampleTheory of Probability & Its Applications, 1966
- On the shortest spanning subtree of a graph and the traveling salesman problemProceedings of the American Mathematical Society, 1956