# Density for number of collected golden balls from urns

$$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$$.

• If $r=1$ and any $1 \le k\le m$ then you have a hypergeometric distribution, as you have noted, while if $k=1$ and any $1 \le r$ you have a binomial distribution. With $k>1$ and $r>1$ you have a combination of the two and I doubt there is a simple expression for probability mass function (not density), though as trueblueanil has answered there is a simple expression for its expectation. Jul 11, 2023 at 15:44

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 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

• Perfect I was looking for either incl-excl or recurrence relation! I cannot see why $\ell \choose i$ is included, as it seems correct if it is omitted. E.g. with $n=m=k=r=1$ we should almost surely collect $1$ ball (0 remaining), but we get $P(X=0)=P(X=1)=0$. Jul 12, 2023 at 7:40
• @PontusHultkrantz Thank you for the comment. As you noticed, my formula was wrong; I mixed up $i$ with $m-i$ at one spot. The formula is correct now; with the variables set as in your comment, my formula now gives $P(\text{1 ball chosen})=P(X=0)=1$. Jul 12, 2023 at 17:43
• very useful, thx! How would the incl-excl change if each repetition (player) only collects max 1 ball (ticket)? I.e. in total max $r$ balls can be collected, or rather ($0\leq i\leq min(m,r)$). Can incl-excl still be applied here? Jul 13, 2023 at 9:15
• That variant sounds like it might require a different method. I won’t attempt to answer in the comment section, but I will attempt to answer if you make a new question post. Jul 13, 2023 at 16:48

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$$

• Interesting, although I need the discrete density function. Actually what I am looking for is: after $r$ repeats each picking $k$ urns, what is the prob of collecting (additional) >0 balls if picking $k_2$ urns, for some $k_2>k$. (Equivalently, what is the prob of player $r+1$ winning a ticket if choosing $k_2$ boxes). Once I know the density this is easy to calculate. Jul 11, 2023 at 12:49
• I don't know whether this link helps you in any way: stats.stackexchange.com/questions/211574/… Jul 11, 2023 at 13:28
• For the lottery variant you have described, my answer represents the average number of tickets you would get in the r round game, if it is played a large number of times. Jul 11, 2023 at 13:41