Guy Louchard ; Helmut Prodinger ; Mark Daniel Ward - The number of distinct values of some multiplicity in sequences of geometrically distributed random variables

dmtcs:3358 - Discrete Mathematics & Theoretical Computer Science, January 1, 2005, DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms - https://doi.org/10.46298/dmtcs.3358
The number of distinct values of some multiplicity in sequences of geometrically distributed random variablesArticle

Authors: Guy Louchard 1; Helmut Prodinger 2; Mark Daniel Ward 3

  • 1 Département d'Informatique [Bruxelles]
  • 2 Department of Mathematical Sciences [Matieland, Stellenbosch Uni.]
  • 3 Department of mathematics Purdue University

We consider a sequence of $n$ geometric random variables and interpret the outcome as an urn model. For a given parameter $m$, we treat several parameters like what is the largest urn containing at least (or exactly) $m$ balls, or how many urns contain at least $m$ balls, etc. Many of these questions have their origin in some computer science problems. Identifying the underlying distributions as (variations of) the extreme value distribution, we are able to derive asymptotic equivalents for all (centered or uncentered) moments in a fairly automatic way.


Volume: DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms
Section: Proceedings
Published on: January 1, 2005
Imported on: May 10, 2017
Keywords: extreme value distribution,Distinct values,geometric random variables,[INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS],[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM],[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO],[INFO.INFO-CG] Computer Science [cs]/Computational Geometry [cs.CG],[INFO.INFO-HC] Computer Science [cs]/Human-Computer Interaction [cs.HC]

5 Documents citing this article

Consultation statistics

This page has been seen 288 times.
This article's PDF has been downloaded 268 times.