Skip to Main content Skip to Navigation
Conference papers

A hooray for Poisson approximation

Abstract : 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.
Complete list of metadata

Cited literature [14 references]  Display  Hide  Download
Contributor : Coordination Episciences Iam Connect in order to contact the contributor
Submitted on : Wednesday, August 12, 2015 - 3:51:39 PM
Last modification on : Sunday, November 25, 2018 - 2:02:17 PM
Long-term archiving on: : Friday, November 13, 2015 - 11:40:10 AM


Publisher files allowed on an open archive




Rudolf Grübel. A hooray for Poisson approximation. 2005 International Conference on Analysis of Algorithms, 2005, Barcelona, Spain. pp.181-192, ⟨10.46298/dmtcs.3357⟩. ⟨hal-01184029⟩



Record views


Files downloads