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

https://hal.inria.fr/hal-01184029
Contributor : Coordination Episciences Iam <>
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

File

dmAD0118.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : hal-01184029, version 1

Collections

Citation

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

Share

Metrics

Record views

157

Files downloads

570