The Probability to Hit Every Bin with a Linear Number of Balls
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866910349717929984 |
|---|---|
| author | Walzer, Stefan |
| author_facet | Walzer, Stefan |
| contents | Assume that $2n$ balls are thrown independently and uniformly at random into $n$ bins. We consider the unlikely event $E$ that every bin receives at least one ball, showing that $\Pr[E] = Θ(b^n)$ where $b \approx 0.836$. Note that, due to correlations, $b$ is not simply the probability that any single bin receives at least one ball. More generally, we consider the event that throwing $αn$ balls into $n$ bins results in at least $d$ balls in each bin. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_00736 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | The Probability to Hit Every Bin with a Linear Number of Balls Walzer, Stefan Probability Data Structures and Algorithms Assume that $2n$ balls are thrown independently and uniformly at random into $n$ bins. We consider the unlikely event $E$ that every bin receives at least one ball, showing that $\Pr[E] = Θ(b^n)$ where $b \approx 0.836$. Note that, due to correlations, $b$ is not simply the probability that any single bin receives at least one ball. More generally, we consider the event that throwing $αn$ balls into $n$ bins results in at least $d$ balls in each bin. |
| title | The Probability to Hit Every Bin with a Linear Number of Balls |
| topic | Probability Data Structures and Algorithms |
| url | https://arxiv.org/abs/2403.00736 |