Increasing paths in regular trees

M Roberts, Lee Zhuo Zhao

Research output: Contribution to journalArticle

6 Citations (Scopus)
57 Downloads (Pure)

Abstract

We consider a regular n-ary tree of height h, for which every vertex except the root is labelled with an independent and identically distributed continuous random variable. Taking motivation from a question in evolutionary biology, we consider the number of paths from the root to a leaf along vertices with increasing labels. We show that if α=n/h is fixed and α>1/e, the probability that there exists such a path converges to 1 as h→∞. This complements a previously known result that the probability converges to 0 if α≤1/e.
Original languageEnglish
Article number87
Number of pages10
JournalElectronic Communications in Probability
Volume18
Early online date9 Nov 2013
DOIs
Publication statusPublished - 2013

Fingerprint

Roots
Converge
Continuous random variable
Path
Identically distributed
Biology
Leaves
Complement
Vertex of a graph
Evolutionary biology
Random variables

Cite this

Increasing paths in regular trees. / Roberts, M; Zhuo Zhao, Lee.

In: Electronic Communications in Probability, Vol. 18, 87, 2013.

Research output: Contribution to journalArticle

@article{2c3b41102f254914bc5b6f00d0c8fb3e,
title = "Increasing paths in regular trees",
abstract = "We consider a regular n-ary tree of height h, for which every vertex except the root is labelled with an independent and identically distributed continuous random variable. Taking motivation from a question in evolutionary biology, we consider the number of paths from the root to a leaf along vertices with increasing labels. We show that if α=n/h is fixed and α>1/e, the probability that there exists such a path converges to 1 as h→∞. This complements a previously known result that the probability converges to 0 if α≤1/e.",
author = "M Roberts and {Zhuo Zhao}, Lee",
year = "2013",
doi = "10.1214/ECP.v18-2784",
language = "English",
volume = "18",
journal = "Electronic Communications in Probability",
issn = "1083-589X",
publisher = "Institute of Mathematical Statistics",

}

TY - JOUR

T1 - Increasing paths in regular trees

AU - Roberts, M

AU - Zhuo Zhao, Lee

PY - 2013

Y1 - 2013

N2 - We consider a regular n-ary tree of height h, for which every vertex except the root is labelled with an independent and identically distributed continuous random variable. Taking motivation from a question in evolutionary biology, we consider the number of paths from the root to a leaf along vertices with increasing labels. We show that if α=n/h is fixed and α>1/e, the probability that there exists such a path converges to 1 as h→∞. This complements a previously known result that the probability converges to 0 if α≤1/e.

AB - We consider a regular n-ary tree of height h, for which every vertex except the root is labelled with an independent and identically distributed continuous random variable. Taking motivation from a question in evolutionary biology, we consider the number of paths from the root to a leaf along vertices with increasing labels. We show that if α=n/h is fixed and α>1/e, the probability that there exists such a path converges to 1 as h→∞. This complements a previously known result that the probability converges to 0 if α≤1/e.

UR - http://www.scopus.com/inward/record.url?scp=84887413686&partnerID=8YFLogxK

UR - http://ecp.ejpecp.org/article/view/2784/2364

UR - http://dx.doi.org/10.1214/ECP.v18-2784

U2 - 10.1214/ECP.v18-2784

DO - 10.1214/ECP.v18-2784

M3 - Article

VL - 18

JO - Electronic Communications in Probability

JF - Electronic Communications in Probability

SN - 1083-589X

M1 - 87

ER -