On weighted heights of random trees


Journal Article

Consider the family tree T of a branching process starting from a single progenitor and conditioned to have v=v(T) edges (total progeny). To each edge we associate a weight W(e). The weights are i.i.d. random variables and independent of T. The weighted height of a self-avoiding path in T starting at the root is the sum of the weights associated with the path. We are interested in the asymptotic distribution of the maximum weighted path height in the limit as v=n→∞. Depending on the tail of the weight distribution, we obtain the limit in three cases. In particular if y2P(W(e)> y)→0, then the limit distribution depends strongly on the tree and, in fact, is the distribution of the maximum of a Brownian excursion. If the tail of the weight distribution is regularly varying with exponent 0≤α<2, then the weight swamps the tree and the answer is the asymptotic distribution of the maximum edge weight in the tree. There is a borderline case, namely, P(W(e)> y)∼cy-2 as y→∞, in which the limit distribution exists but involves both the tree and the weights in a more complicated way. © 1991 Plenum Publishing Corporation.

Full Text

Duke Authors

Cited Authors

  • Durrett, R; Kesten, H; Waymire, E

Published Date

  • January 1, 1991

Published In

Volume / Issue

  • 4 / 1

Start / End Page

  • 223 - 237

Electronic International Standard Serial Number (EISSN)

  • 1572-9230

International Standard Serial Number (ISSN)

  • 0894-9840

Digital Object Identifier (DOI)

  • 10.1007/BF01047004

Citation Source

  • Scopus