2
$\begingroup$

I am given $n$ objects and for $n$ times, I pick one of them with uniform probability and put it back after picking it.

For $k\in\{1,\ldots,n\}$ let $f_k$ denote the number of times that I have picked object number $k$. So we have $f_k\in \{0,\ldots,n\}$ for all $k$.

We consider $M:= \max\big\{f_k: k\in\{1,\ldots,n\}\big\}$, so we have $M\in\{1,\ldots,n\}$. We are interested in the expected value $E_n:= E(M)$.

Does $\lim_{n\to\infty} E_n$ exist? If yes, what is its value?

$\endgroup$
  • 6
    $\begingroup$ I would title this: "How popular is the most popular ball, when choosing repeatedly from a large urn?" $\endgroup$ – Matt F. Dec 12 '16 at 16:54
  • $\begingroup$ See OEIS A208250 divided by $n^n$ $\endgroup$ – Henry Jan 8 '17 at 20:31
4
$\begingroup$

Fix some $k$. The probability that the element $1$ is chosen exactly $k$ times is ${n\choose k}\frac1{n^k}\left(1-\frac1n\right)^{n-k}\to \frac1{ek!}$ as $n\to\infty$. So $1$ is chosen at least $k$ times with probability at least, say, $\frac1{2ek!}$

Under the condition that $1$ has been chosen less than $k$ times, the same probability for $2$ is at least ${n-k\choose k}\frac1{n^k}\left(1-\frac1{n-1}\right)^{n-k}\to \frac1{ek!}$, so both $1$ and $2$ are not chosen with the probability at most $\left(1-\frac1{2ek!}\right)^2$ if $n$ is large.

Iterating this, we get that for large enough $n$ the probabitily of $M<k$ is at most $\left(1-\frac1{2ek!}\right)^d$, where $d$ is an arbitrary fixed number. Thus this probability tends to $0$ as $n\to\infty$, and $E_n\to\infty$.

$\endgroup$
  • $\begingroup$ I think, we may even say that the probability that all elements are chosen at most $k$ times does not exceed $p^n$, where $p$ is the probability that the element 1 is chosen at most $k$ times. Since these events correlate negatively. $\endgroup$ – Fedor Petrov Dec 12 '16 at 16:46
  • $\begingroup$ @FedorPetrov: After a suitable generalization - maybe, but I'm not sure if just negativeness of pairwise correlations is sufficient... $\endgroup$ – Ilya Bogdanov Dec 12 '16 at 16:53
  • $\begingroup$ Kleitman lemma works, does not it? $\endgroup$ – Fedor Petrov Dec 12 '16 at 17:36
8
$\begingroup$

$M = \Theta(\log n / \log\log n)$ with high probability and in expectation.

An alternative way of thinking about this problem is that you're tossing $n$ balls uniformly at random into $n$ bins and looking at the size of the largest bin. In this formulation, this model is used in computer science to think about load-balancing; Gonnet 1981 (Expected length of the longest probe sequence in hash code searching, Journal of the ACM 28(2): 289-304, https://cs.uwaterloo.ca/research/tr/1978/CS-78-46.pdf) has a sketch of a proof. Alternatively, these lecture notes https://people.eecs.berkeley.edu/~sinclair/cs271/n14.pdf work through the argument more carefully, justifying why the Poisson approximation can be used there.

As an aside, if instead of picking your object uniformly at random you first eyeball two objects (uniformly at random), and then actually pick the less popular one of those, the maximum will drop down to $\log\log(n) / \log(2) + O(1)$. This is known as the "power of two choices" and makes for a nice term to Google.

$\endgroup$
5
$\begingroup$

This is the Balls and Bins setting.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.