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
NULL##NULL##NULL
Guy Louchard;Helmut Prodinger;Mark Daniel Ward
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.
Margaret Archibald;Aubrey Blecher;Charlotte Brennan;Arnold Knopfmacher;Stephan Wagner;et al., 2021, The number of distinct adjacent pairs in geometrically distributed words, DOAJ (DOAJ: Directory of Open Access Journals), 10.23638/dmtcs-22-4-10.
F. Thomas Bruss;Guy Louchard;Mark Daniel Ward, 2009, Inverse auctions, ACM Transactions on Algorithms, 6, 1, pp. 1-19, 10.1145/1644015.1644036.
Guy Louchard;Helmut Prodinger, 2009, The Asymmetric Leader Election Algorithm: Another Approach, Annals of Combinatorics, 12, 4, pp. 449-478, 10.1007/s00026-009-0004-2.
Margaret Archibald;Arnold Knopfmacher, 2006, Samples of geometric random variables with multiplicity constraints, Discrete Mathematics & Theoretical Computer Science, DMTCS Proceedings vol. AG,..., Proceedings, 10.46298/dmtcs.3490, https://doi.org/10.46298/dmtcs.3490.