TransWikia.com

Ball / Urn question with a twist

Mathematics Asked by user109387 on December 3, 2021

I am trying to answer questions like: We select, with replacement, $20$ balls from an urn holding $30$ numbered balls. What is the probability that we have selected at least $15$ distinct balls?

The general form is: An urn contains $m$ balls, numbered $1$ to $m$. We select $n$ balls with replacement $(n ≤ m)$. What is the probability that we have selected AT LEAST $k$ distinct balls $(k ≤ m)$?

There are related questions on this site, but I’m not sure how to handle the ‘AT LEAST’ part.

One Answer

The following problem is equivalent.

Suppose we have $n$ bins and $r$ balls. We toss the balls into the bins independently, with all bins being equally likely to receive a ball. Let's say that in general $x_m(n,r)$ is the probability that at least $m$ bins are empty. Then the answer to the original problem is $1-x_{16}(30,20)$, since having at least $15$ cells selected is equivalent to having $15$ or fewer cells empty, and the complementary event is that there are $16$ or more empty cells.

The only difficulty that remains is how to calculate $x_m(n,r)$, and a recent question gives the answer via the principle of inclusion and exclusion. See Given $n$ cells and $r$ balls, estimate the probability of finding $m$ or more cells empty. (The problem title is misleading, since the result is exact, not an estimate.) At the risk of being repetitious, the answer is $$x_m(r,n) = binom{n}{m} sum_{nu=0}^{n-m} (-1)^{nu} binom{n-m}{nu} left( 1 - frac{m+nu}{n} right)^r frac{m}{m+nu}$$

If we evaluate this formula with $n=30$, $r=20$, and $m=16$, we find $$1-x_{16}(30,20) approx 0.577467$$

Answered by awkward on December 3, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP