Premium
Bounded branching process and and/or tree evaluation
Author(s) -
Karp Richard M.,
Zhang Yanjun
Publication year - 1995
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.3240070202
Subject(s) - bounded function , branching process , branching (polymer chemistry) , supercritical fluid , mathematics , upper and lower bounds , combinatorics , probabilistic logic , discrete mathematics , probability distribution , statistics , physics , mathematical analysis , chemistry , organic chemistry , thermodynamics
We study the tail distribution of supercritical branching processes for which the number of offspring of an element is bounded. Given a supercritical branching process { Z n } 0 ∞with a bounded offspring distribution, we derive a tight bound, decaying super‐exponentially fast as c increases, on the probability Pr[ Z n > cE ( Z n )], and a similar bound on the probability Pr[ Z n ≤ E(Z n )/c ] under the assumption that each element generates at least two offspring. As an application, we observe that the execution of a canonical algorithm for evaluating uniform AND/OR trees in certain probabilistic models can be viewed as a two‐type supercritical branching process with bounded offspring, and show that the execution time of this algorithm is likely to concentrate around its expectation, with a standard deviation of the same order as the expectation.