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.
Type de document :
Communication dans un congrès
Conrado Martínez. 2005 International Conference on Analysis of Algorithms, 2005, Barcelona, Spain. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms, pp.181-192, 2005, DMTCS Proceedings
Liste complète des métadonnées

Littérature citée [14 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01184029
Contributeur : Coordination Episciences Iam <>
Soumis le : mercredi 12 août 2015 - 15:51:39
Dernière modification le : jeudi 11 mai 2017 - 01:03:07
Document(s) archivé(s) le : vendredi 13 novembre 2015 - 11:40:10

Fichier

dmAD0118.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-01184029, version 1

Collections

Citation

Rudolf Grübel. A hooray for Poisson approximation. Conrado Martínez. 2005 International Conference on Analysis of Algorithms, 2005, Barcelona, Spain. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms, pp.181-192, 2005, DMTCS Proceedings. 〈hal-01184029〉

Partager

Métriques

Consultations de la notice

121

Téléchargements de fichiers

145