  We give a probabilistic analysis for the randomized game tree evaluation
algorithm of Snir. We first show that there exists an input such that the
running time, measured as the number of external nodes read by the algorithm,
on that input is maximal in stochastic order among all possible inputs. For
this worst case input we identify the exact expectation of the number of
external nodes read by the algorithm, give the asymptotic order of the variance
including the leading constant, provide a limit law for an appropriate
normalization as well as a tail bound estimating large deviations. Our tail
bound improves upon the exponent of an earlier bound due to Karp and Zhang,
where subgaussian tails were shown based on an approach using multitype
branching processes and Azuma's inequality. Our approach rests on a direct,
inductive estimate of the moment generating function.

Probability