Finite Branching Processes and AND/OR Tree Evaluation
Title | Finite Branching Processes and AND/OR Tree Evaluation |
Publication Type | Technical Report |
Year of Publication | 1993 |
Authors | Karp, R. M. |
Other Numbers | 831 |
Abstract | 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. |
URL | http://www.icsi.berkeley.edu/ftp/global/pub/techreports/1993/tr-93-043.pdf |
Bibliographic Notes | ICSI Technical Report TR-93-043 |
Abbreviated Authors | R. M. Karp |
ICSI Publication Type | Technical Report |