Finite Branching Processes and AND/OR Tree Evaluation

TitleFinite Branching Processes and AND/OR Tree Evaluation
Publication TypeTechnical Report
Year of Publication1993
AuthorsKarp, R. M.
Other Numbers831

This paper studies tail bounds on supercritical branching processes with finite distributions of offspring. Given a finite supercritical branching process (Z_n)_0^?, we derive upper bounds, decaying exponentially fast as c increases, on the right-tail probability Pr[Z_n > c E(Z_n)]. We obtain a similar upper bound on the left-tail probability Pr[Z_n < frac{E(Z_n)}c] under the assumption that each individual generates at least two offspring. As an application, we observe that the evaluation of an AND/OR tree by a canonical algorithm in certain probabilistic models can be viewed as a two-type supercritical finite branching process, and show that the execution time of this algorithm is likely to concentrate around its expectation.

Bibliographic Notes

ICSI Technical Report TR-93-043

Abbreviated Authors

R. M. Karp

ICSI Publication Type

Technical Report