Density for number of collected golden balls from urns

Question

$m$ golden balls are randomly allocated into $n$ binary urns, such that an urn contains either one or no ball ($m \leq n$).

We select $k$ urns without replacement and collect the balls. Since we have amnesia, we repeat this $r$ times. What is the density of the number of collected balls?

Phrased differently: $m$ winning tickets are hidden behind $n$ boxes. Sequentially, $r$ players pick independently $k$ boxes and open them to collect the tickets. What is the probability that $i$ tickets ($0\leq i \leq m$) are collected from the game?

We know that for $r=1$ the density for the number of collected balls is $f(i) = \frac{{m\choose i} {n-m\choose k-i}}{n\choose k}$. The difficulty starts for $r>1$.

Answer 1

To solve this, we use the generalized principle of inclusion exclusion.

Let $E_1,\dots,E_m$ be events in a probability space. For each $\ell\in \{0,1,\dots,m\}$, let $$a_\ell=\sum_{1\le j_1<j_2<\dots<j_\ell\le m}P(E_{j_1}\cap \dots \cap E_{j_\ell})$$ Let $X$ be a random variable, equal to the number of events in $E_1,\dots,E_m$ that occur: $X=\sum_{i=1}^m {\bf 1}(E_i)$. Then the probability distribution for $X$ is given by

$$P(X=i)=\sum_{\ell=i}^m (-1)^{\ell-i}\binom{\ell}{i}a_\ell,\qquad 0\le i\le m.$$

To apply this to your problem, for each $j \in \{1,\dots,m\}$, let $E_j$ be the event that the $j^\text{th}$ ball is not collected. Note that, for any selection $j_1\le \dots \le j_\ell$ of $\ell$ indices, we have $$ P(E_{j_1}\cap \dots \cap E_{j_\ell})=\binom{n-\ell}{k}^r\big/\binom{n}{k}^r $$ This is because there are $\ell$ particular balls which cannot be chosen. This shows that $$ a_\ell= \binom{m}\ell\binom{n-\ell}{k}^r\big/\binom{n}{k}^r. $$ Finally, let $X$ be the number of events that occur, meaning the number of balls which are not chosen. Applying the generalized PIE, we conclude $$ P(\text{$i$ balls are chosen})=P(X = m-i)=\sum_{\ell=m-i}^m (-1)^{\ell-(m-i)}\binom{\ell}{m-i} \binom{m}\ell\frac{\binom{n-\ell}{k}^r}{\binom{n}k^r} $$ This formula agrees with simulation. Python demonstration

Answer 2

What you are seeking is the expected number of golden balls collected after r iterations, and the simplest way to get the answer is by treating it as a mixture problem.

In the first iteration, you expect to collect $\dfrac{k}{n}\cdot m\;$ golden balls,
and $m - \dfrac{k}{n}\cdot m\;$ are left behind.

Denote $1-\dfrac{k}{n} = f$ for fraction of total balls left behind,

Then the fraction left behind after $r$ iterations = $f^r$, and golden balls collected $= \boxed {m(1 - f^r)}$

---

As an example, with $m=40, n=100, k = 30, r = 3$

After first iteration, with $f = 0.7$, we leave behind $28$ balls

After 2nd iteration, we leave behind $0.7*28=19.6$ balls

After 3rd iteration, we leave behind $0.7*19.6 = 13.72$ balls

Thus balls collected in $3$ iterations $= 40-13.72 = 26.28$

which we directly get by the formula we devised, $m(1-f^r) = 40(1-0.7^3)=26.28$