The number of distinct values of some multiplicity in sequences of geometrically distributed random variables
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 question...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2005-01-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/3358/pdf |
| _version_ | 1797270637198180352 |
|---|---|
| author | Guy Louchard Helmut Prodinger Mark Daniel Ward |
| author_facet | Guy Louchard Helmut Prodinger Mark Daniel Ward |
| author_sort | Guy Louchard |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-25T02:07:26Z |
| format | Article |
| id | doaj.art-8a964b8764064ae19747de2b67542fcd |
| institution | Directory Open Access Journal |
| issn | 1365-8050 |
| language | English |
| last_indexed | 2024-04-25T02:07:26Z |
| publishDate | 2005-01-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-8a964b8764064ae19747de2b67542fcd2024-03-07T14:30:51ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502005-01-01DMTCS Proceedings vol. AD,...Proceedings10.46298/dmtcs.33583358The number of distinct values of some multiplicity in sequences of geometrically distributed random variablesGuy Louchard0Helmut Prodinger1Mark Daniel Ward2Département d'Informatique [Bruxelles]Department of Mathematical Sciences [Matieland, Stellenbosch Uni.]Department of mathematics Purdue UniversityWe 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.https://dmtcs.episciences.org/3358/pdfextreme value distributiondistinct valuesgeometric 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] |
| spellingShingle | Guy Louchard Helmut Prodinger Mark Daniel Ward The number of distinct values of some multiplicity in sequences of geometrically distributed random variables Discrete Mathematics & Theoretical Computer Science 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] |
| title | The number of distinct values of some multiplicity in sequences of geometrically distributed random variables |
| title_full | The number of distinct values of some multiplicity in sequences of geometrically distributed random variables |
| title_fullStr | The number of distinct values of some multiplicity in sequences of geometrically distributed random variables |
| title_full_unstemmed | The number of distinct values of some multiplicity in sequences of geometrically distributed random variables |
| title_short | The number of distinct values of some multiplicity in sequences of geometrically distributed random variables |
| title_sort | number of distinct values of some multiplicity in sequences of geometrically distributed random variables |
| topic | 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] |
| url | https://dmtcs.episciences.org/3358/pdf |
| work_keys_str_mv | AT guylouchard thenumberofdistinctvaluesofsomemultiplicityinsequencesofgeometricallydistributedrandomvariables AT helmutprodinger thenumberofdistinctvaluesofsomemultiplicityinsequencesofgeometricallydistributedrandomvariables AT markdanielward thenumberofdistinctvaluesofsomemultiplicityinsequencesofgeometricallydistributedrandomvariables AT guylouchard numberofdistinctvaluesofsomemultiplicityinsequencesofgeometricallydistributedrandomvariables AT helmutprodinger numberofdistinctvaluesofsomemultiplicityinsequencesofgeometricallydistributedrandomvariables AT markdanielward numberofdistinctvaluesofsomemultiplicityinsequencesofgeometricallydistributedrandomvariables |