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$
2
  • 6
    $\begingroup$ I would title this: "How popular is the most popular ball, when choosing repeatedly from a large urn?" $\endgroup$
    – user44143
    Dec 12, 2016 at 16:54
  • $\begingroup$ See OEIS A208250 divided by $n^n$ $\endgroup$
    – Henry
    Jan 8, 2017 at 20:31

3 Answers 3

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$
3
  • $\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$ Dec 12, 2016 at 16:46
  • $\begingroup$ @FedorPetrov: After a suitable generalization - maybe, but I'm not sure if just negativeness of pairwise correlations is sufficient... $\endgroup$ Dec 12, 2016 at 16:53
  • $\begingroup$ Kleitman lemma works, does not it? $\endgroup$ Dec 12, 2016 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 and acknowledge you have read our privacy policy.

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