Skip to main contentSkip to search
Episciences
Open Access Journals
Sign in(new window)
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Sign in(new window)
Articles & Issues
All articlesAll accepted articlesAll volumesLast volumeSectionsSpecial issuesAuthors
About
The journalIndexing
Boards
Publish
For authorsEthical charter
Submit
Discrete Mathematics & Theoretical Computer Science logo
Contact
|
Credits
eISSN 1365-8050
|
RSS
|
Atom
Episciences
Documentation
|
Acknowledgements
|
Publishing policy
Accessibility: non-compliant
|
Legal mentions
|
Privacy statement
|
Terms of use
  1. Home > Articles & Issues >
  2. Articles >
  3. The number of distin ...
Conference paper

The number of distinct values of some multiplicity in sequences of geometrically distributed random variables

Guy Louchard (1), Helmut Prodinger (2) (3), Mark Daniel Ward (4) (5)
(1) Département d'Informatique [Bruxelles]
(2) Department of Mathematical Sciences [Matieland, Stellenbosch Uni.]
(3) Department of Mathematical Sciences [Stellenbosch University]
(4) Department of mathematics Purdue University
(5) Department of Mathematics [West Lafayette]
Download article
Open on HAL
Imported on
May 10, 2017
Published on
December 31, 2004
Last modified on
March 31, 2025
Volume 0
DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms
Proceedings
DOI
10.46298/dmtcs.3358
License
https://about.hal.science/hal-authorisation-v1
Indicators
666
Views
549
Downloads

The number of distinct values of some multiplicity in sequences of geometrically distributed random variables

Guy Louchard (1), Helmut Prodinger (2) (3), Mark Daniel Ward (4) (5)
(1) Département d'Informatique [Bruxelles]
(2) Department of Mathematical Sciences [Matieland, Stellenbosch Uni.]
(3) Department of Mathematical Sciences [Stellenbosch University]
(4) Department of mathematics Purdue University
(5) Department of Mathematics [West Lafayette]
Abstract
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.
Keywords
  • [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]
  • Distinct values
  • geometric random variables
  • extreme value distribution
Cited by

Source: OpenCitations

  • Inverse auctions

    Dépôt institutionnel de l'Université libre de Bruxelles (Université Libre de Bruxelles)

    Authors : F. Thomas Bruss ORCID, Guy Louchard, Mark Daniel Ward ORCID

    Journal reference : Volume 6, 2009, pp. 1-19

    DOI : 10.1145/1644015.1644036

  • The number of distinct adjacent pairs in geometrically distributed words

    Discrete Mathematics & Theoretical Computer Science

    Authors : Margaret Archibald ORCID, Aubrey Blecher ORCID, Charlotte Brennan ORCID, Arnold Knopfmacher ORCID, Stephan Wagner ORCID, Mark Ward ORCID

    Journal reference : Volume vol. 22 no. 4, 2021, pp.

    DOI : 10.23638/dmtcs-22-4-10

  • The Asymmetric Leader Election Algorithm: Another Approach

    Annals of Combinatorics

    Authors : Guy Louchard, Helmut Prodinger ORCID

    Journal reference : Volume 12, 2009, pp. 449-478

    DOI : 10.1007/s00026-009-0004-2

  • Samples of geometric random variables with multiplicity constraints

    Discrete Mathematics & Theoretical Computer Science

    Authors : Margaret Archibald ORCID, Arnold Knopfmacher ORCID

    Journal reference : Volume DMTCS Proceedings vol. AG,..., 2006, pp.

    DOI : 10.46298/dmtcs.3490

  • Asymptotic results for silent elimination

    Discrete Mathematics & Theoretical Computer Science

    Authors : Guy Louchard, Helmut Prodinger ORCID

    Journal reference : Volume Vol. 12 no. 2, 2010, pp.

    DOI : 10.46298/dmtcs.527
Preview
Loading PDF preview...