Random minimal directed spanning trees and Dickman-type distributions

M.D. Penrose, Andrew Wade

Research output: Contribution to journalArticle

27 Citations (Scopus)

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.
LanguageEnglish
Pages691-714
Number of pages24
JournalAdvances in Applied Probability
Volume36
Issue number3
DOIs
Publication statusPublished - Sep 2004

Fingerprint

Poisson distribution
Spanning tree
Poisson-Dirichlet Distribution
Limit Distribution
Limiting Distribution
Roots
Path
Unit
Vertex of a graph

Keywords

  • spanning tree
  • extreme value
  • weak convergence
  • dickman distribution
  • poisson-dirichlet distribution

Cite this

Penrose, M.D. ; Wade, Andrew. / Random minimal directed spanning trees and Dickman-type distributions. In: Advances in Applied Probability. 2004 ; Vol. 36, No. 3. pp. 691-714.
@article{e7ecca454b7b436683dfbff7d3b2c539,
title = "Random minimal directed spanning trees and Dickman-type distributions",
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 = "spanning tree, extreme value, weak convergence, dickman distribution, poisson-dirichlet distribution",
author = "M.D. Penrose and Andrew Wade",
year = "2004",
month = "9",
doi = "10.1239/aap/1093962229",
language = "English",
volume = "36",
pages = "691--714",
journal = "Advances in Applied Probability",
issn = "0001-8678",
number = "3",

}

Random minimal directed spanning trees and Dickman-type distributions. / Penrose, M.D.; Wade, Andrew.

In: Advances in Applied Probability, Vol. 36, No. 3, 09.2004, p. 691-714.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Random minimal directed spanning trees and Dickman-type distributions

AU - Penrose, M.D.

AU - Wade, Andrew

PY - 2004/9

Y1 - 2004/9

N2 - 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.

AB - 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.

KW - spanning tree

KW - extreme value

KW - weak convergence

KW - dickman distribution

KW - poisson-dirichlet distribution

UR - http://projecteuclid.org/euclid.aap/1093962229

UR - http://www.newton.ac.uk/preprints/NI03088.pdf

U2 - 10.1239/aap/1093962229

DO - 10.1239/aap/1093962229

M3 - Article

VL - 36

SP - 691

EP - 714

JO - Advances in Applied Probability

T2 - Advances in Applied Probability

JF - Advances in Applied Probability

SN - 0001-8678

IS - 3

ER -