Journal article
On a tail bound for analyzing random trees
Statistics & probability letters, Vol.162, p.108746
07/01/2020
DOI: 10.1016/j.spl.2020.108746
Abstract
We re-examine a lower-tail upper bound for the random variable
X = Pi(infinity)(i=1)min {Sigma E-i(k=1)k, 1},
where E-1, E-2,... similar to(iid) Exp(1). This bound has found use in root-finding and seed-finding algorithms for randomly growing trees, and was initially established in the context of the uniform attachment tree model. We first show that X has a useful representation as a compound product of uniform random variables that allows us to determine its moments and refine the existing nonasymptotic bound. Next we demonstrate that the lower-tail probability for X can equivalently be written as a probability involving two independent Poisson random variables, an equivalence that yields a novel general result regarding independent Poissons and that also enables us to obtain tight asymptotic bounds on the tail probability of interest. (C) 2020 Elsevier B.V. All rights reserved.
Details
- Title: Subtitle
- On a tail bound for analyzing random trees
- Creators
- Sam Justice - University of IowaN. D Shyamalkumar - University of Iowa
- Resource Type
- Journal article
- Publication Details
- Statistics & probability letters, Vol.162, p.108746
- Publisher
- ELSEVIER
- DOI
- 10.1016/j.spl.2020.108746
- ISSN
- 0167-7152
- eISSN
- 1879-2103
- Number of pages
- 6
- Language
- English
- Date published
- 07/01/2020
- Academic Unit
- Statistics and Actuarial Science
- Record Identifier
- 9984257626502771
Metrics
11 Record Views