Probabilistic Analysis for Randomized Game Tree Evaluation

Details Probabilistic Analysis for Randomized Game Tree Evaluation Probabilistic Analysis for Randomized Game Tree Evaluation

2004-05-17

arxiv.org/abs/math/0405322v1

Mathematics

Probability

10 pages, conference: Third Colloquium on Mathematics and Computer Science

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Probabilistic Analysis for Randomized Game Tree Evaluation does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Probabilistic Analysis for Randomized Game Tree Evaluation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Probabilistic Analysis for Randomized Game Tree Evaluation will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-284899