DMTCS Proceedings, 2005 International Conference on Analysis of Algorithms

Font Size:  Small  Medium  Large

A hooray for Poisson approximation

Rudolf Grübel


We give several examples for Poisson approximation of quantities of interest in the analysis of algorithms: the distribution of node depth in a binary search tree, the distribution of the number of losers in an election algorithm and the discounted profile of a binary search tree. A simple and well-known upper bound for the total variation distance between the distribution of a sum of independent Bernoulli variables and the Poisson distribution with the same mean turns out to be very useful in all three cases.

Full Text: GZIP Compressed PostScript PostScript PDF original HTML abstract page

Valid XHTML 1.0 Transitional