Mathew D. Penrose
On the total length of the random minimal directed spanning tree
Penrose, Mathew D.; Wade, Andrew R.
Abstract
In Bhatt and Roy's minimal directed spanning tree construction for a random, partially ordered set of points in the unit square, all edges must respect the `coordinatewise' partial order and there must be a directed path from each vertex to a minimal element. We study the asymptotic behaviour of the total length of this graph with power-weighted edges. The limiting distribution is given by the sum of a normal component away from the boundary plus a contribution introduced by the boundary effects, which can be characterized by a fixed-point equation, and is reminiscent of limits arising in the probabilistic analysis of certain algorithms. As the exponent of the power weighting increases, the distribution undergoes a phase transition from the normal contribution being dominant to the boundary effects being dominant. In the critical case in which the weight is simple Euclidean length, both effects contribute significantly to the limit law.
Citation
Penrose, M. D., & Wade, A. R. (2006). On the total length of the random minimal directed spanning tree. Advances in Applied Probability, 38(2), 336-372. https://doi.org/10.1239/aap/1151337075
Journal Article Type | Article |
---|---|
Publication Date | Jan 1, 2006 |
Deposit Date | Oct 4, 2012 |
Publicly Available Date | Feb 13, 2013 |
Journal | Advances in Applied Probability |
Print ISSN | 0001-8678 |
Electronic ISSN | 1475-6064 |
Publisher | Applied Probability Trust |
Peer Reviewed | Peer Reviewed |
Volume | 38 |
Issue | 2 |
Pages | 336-372 |
DOI | https://doi.org/10.1239/aap/1151337075 |
Keywords | Spanning tree, Nearest-neighbour graph, Weak convergence, Fixed-point equation, Phase transition, Fragmentation process. |
Public URL | https://durham-repository.worktribe.com/output/1473356 |
Files
Accepted Journal Article
(459 Kb)
PDF
You might also like
Passage-times for partially-homogeneous reflected random walks on the quadrant
(2025)
Journal Article
Semi-infinite particle systems with exclusion interaction and heterogeneous jump rates
(2025)
Journal Article
Iterated-logarithm laws for convex hulls of random walks with drift
(2024)
Journal Article
Superdiffusive planar random walks with polynomial space–time drifts
(2024)
Journal Article