Mathew D. Penrose
Random minimal directed spanning trees and Dickman-type distributions
Penrose, Mathew D.; Wade, Andrew R.
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.
Citation
Penrose, M. D., & Wade, A. R. (2004). Random minimal directed spanning trees and Dickman-type distributions. Advances in Applied Probability, 36(3), 691-714. https://doi.org/10.1239/aap/1093962229
Journal Article Type | Article |
---|---|
Publication Date | Jan 1, 2004 |
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 | 36 |
Issue | 3 |
Pages | 691-714 |
DOI | https://doi.org/10.1239/aap/1093962229 |
Keywords | Spanning tree, Extreme value, Weak convergence, Dickman distribution, Poisson-Dirichlet distribution. |
Files
Accepted Journal Article
(266 Kb)
PDF
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