Simple, yet tough urn problem

M Quack

Thanks JCVD, that explanation is very clear.

Well spotted. I was trying to calculate the opposite probability, that there is at least one empty urn. But even that I got wrong.

SW VandeCarr

I got P= 0.8784 for n(M)=20, k=10 using the binomial distribution. Does anyone want the check JCVD's solution against this for these values?

JolleJ

Thank you very much JCVD ! What a great way to do it.

SW VandeCarr

Why? Is there an upper limit on the number of balls that an urn can hold? If so, what is it (other than n itself)? In principle, there is no mathematical reason that the probability should equal 1 for any finite number of balls, although the probability can get arbitrarily close to one. This seems to be a fairly straightforward problem involving the binomial distribution. All one has to do is show that there is a non zero probability that exactly one urn may be empty after any finite n. Then the probability that all all urns have at least one ball is 1-p(x=0). It's not necessary to calculate the probability that at least one urn is empty after n balls. It should be clear that for n balls and k urns, the expected value for the number of balls in each urn is n/k which is the expectation of the binomial distribution when p=1/k.

M Quack

Pick any one urn, which is empty at the start.

For each throw there is a 1/k chance that a ball will end up in this urn. So with each additional turn, the chance that the urn remains empty becomes smaller (1/k^M after M turns).

For an infinite number of throws that probability will go to zero. If for each individual urn the probability to remain empty is zero, then the probability of finding at least one empty bowl in the set is also zero.

In other words the probability that there is at least one ball in each urn increases with M and the limit M->infinity will be 100%.

Kai performed a simple sanity check on my formula and noted that it goes the wrong way. Therefore it has to be wrong. Well spotted, as I said.

SW VandeCarr

Your formula may have been incorrect, but your initial intuition that finding the probability that exactly one urn will be empty for any n was a correct approach. Note "at least one" is a higher probability than "exactly". The former would underestimate the probability that every urn gets at least one ball when computing 1-p(x=0). And of course, we are dealing with a finite mathematics problem here.