Bounded branching process and and/or tree evaluation

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} with a bounded offspring distribution, we derive a tight bound, decaying super-exponentially fast as c increases, on the probability PrZ_n > cE(Z_n)], and a similar bound on the probability PrZ_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.