MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

You start with a bag of N recognizable balls. You pick them one by one and replace them until they have all been picked up at least once. So when you stop the ball you pick has not been picked before but all the others have been picked once or more.

Let $P_N$ be the probability that all the others were actually picked twice or more.

Questions: does $P_N$ have a limit as $N\to \infty$, is this limit 0 or can you compute it?

Note: This is a question that was asked at the Yahoo answers forum, by gianlino. Since no one has found an answer in that forum, I forwarded it here. Here is the original link.;_ylt=ApZ_Q6sS137DnEcNoUBqn.vty6IX;_ylv=3?qid=20100704050924AAfLYYJ

share|cite|improve this question
up vote 9 down vote accepted

One way to think about this sort of problem is to embed in continuous time. Take $N$ independent Poisson processes of rate 1. (Think of $N$ independent Geiger counters, each going off at rate 1, if you like). A point in the $i$th process corresponds to picking the $i$th ball. Since the processes are independent and all have the same rate, the sequence of ball selections is just a sequence of independent uniform choices, as we desire.

Let $M_i(x)$ be the number of points in the $i$th Poisson process up to time $x$. Then the distribution of $M_i(x)$ is Poisson($x$). In particular, $P(M_i(x)\geq 2)= 1-(1+x)e^{-x}$. The time of the first point in such a process has exponential(1) distribution, so its probability density function is $e^{-x}$.

So fix one ball, say ball 1. Consider the event that when ball 1 is first chosen, all the other $N-1$ balls have each been chosen at least twice. To get the probability of this event, integrate over the time that ball 1 is first chosen (i.e. the time of the first event in process 1):

$\int_0^\infty e^{-x} P\big(M_i(x)\geq 2 \text{ for } i=2,3,\dots,N\big) dx$

$=\int_0^\infty e^{-x} \big(1-(1+x)e^{-x}\big)^{N-1} dx$.

The same applies for any ball, and the events are disjoint, so an exact answer to your question is

$N\int_0^\infty e^{-x} \big(1-(1+x)e^{-x}\big)^{N-1} dx$.

I don't know if it's possible to get an exact expression for this integral, but it's easy enough to bound it. For any $K$

$N\int_0^\infty e^{-x} \big(1-(1+x)e^{-x}\big)^{N-1} dx$

$\leq N \int_0^K e^{-x} \big(1-e^{-x}\big)^{N-1} dx + N\int_K^\infty e^{-x} \big(1-Ke^{-x}\big)^{N-1} dx$.

Take $K=\frac12 \log N$, for example; it's easy to evaluate both integrals exactly (substitute $u=e^{-x}$) and to show that they both tend to 0 as $N\to\infty$.

share|cite|improve this answer

I'm assuming, since you don't say, that the balls are drawn with uniform probability.

Number and order the balls then, for fixed i, the probability of picking the i-th ball last, after picking the other N-1 balls at least twice each is no greater than $1/N^2 \times 1/N$. Likewise for the other N-1 balls, so the probability you're after is no greater than $N \times 1/N^2 \times 1/N = 1/N^2$ and no less than zero, so $\lim_{N \rightarrow \infty} P_{N} = 0$ by squeeze rule.

share|cite|improve this answer

Also, here's a heuristic argument to show that the probability behaves like $1/N$ as $N$ becomes large.

The last ball to be chosen is chosen for the first time after roughly $N\log N$ steps. (It's the maximum of $N$ random variables which are geometric with mean $N$). By this stage, the number of times that any particular other ball has been selected is Poisson($\log N$). So the probability a particular other ball has been selected only once is roughly $\log N e^{-\log N}$ which is $\log N/N$. Hence the probability that no other ball has been selected only once is roughly $(1-\log N/N)^{N-1}$, which is $\exp[-\log N + O(\log N/N)] \sim 1/N$.

Of course the previous paragraph ignores various dependencies, but as $N$ becomes large these will be negligible and no doubt one could formalise the argument if desired.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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