Expected number of bags having at least one of the special items

Question

I stumbled upon this problem and was unable to solve it. I tried to find a similar question on the forum but did not find a satisfying answer, feel free to point me to an existing answer if you find one.

Question:

I have $n$ (e.g. $190$) black balls and $m$ (e.g. $10$) white balls and I randomly spread them into $k$ (e.g. $20$) bags such that each bag has an equal number of balls (so $10$ per bag in the example). What is the expectation of the number of bags that will contain at least one white ball ?

For the random process used to put the balls in the bag, it could be seen as first ordering the balls, then random shuffling them such that all balls have equal probability to be at every positions, and then using the ordering to separate the balls in bags. So for example, after shuffling, putting the first 10 balls in one bag, then the next 10 balls in the next bag, etc.

Answer 1

You can use linearity of the expectation to calculate the expectation much more easily than for example calculating the joint distribution. If $X$ is the number of bags with at least one special ball, then

$$X = \sum_{i=1}^k {1}_i$$

Where ${1}_i$ is a variable taking the value 1 if bag $i$ has a special ball, and zero otherwise. Then $EX = k P(\mbox{ bag 1 has at least one special ball})$, since all the probabilities are the same.

Answer 2

This is typically an exercise in using the linearity of expectation. While you can find (using inclusion/exclusion) the complete distribution telling what the probabilities are of finding exactly $l$ bags with at least one a white ball for any value of $l$, from which the expectation of the value of $l$ follows as a weighted average, you can find just the latter much more easily. The value of $l$ can be interpreted the sum over all bags $B$ of the number of bags among $\{B\}$ that contain at least one white ball (since there is only one candidate bag, this number is always either $0$ or $1$). By symmetry the expected value of this number does not depend on which bag is taken to be $B$, so it suffices to compute the expectation for any one of the bags and multiply it by the number$~k$ of bags. Moreover, the expectation of the value for a fixed$~B$, being the expectation of a random variable taking values in $\{0,1\}$ only, is the same as the probability of that variable being$~1$. And that is the complement of the probability of that variable being$~0$, which is easily computed, assuming a uniform sample space in which each of the $\binom{n+m}m$ ways of assigning a colour to all $n+m$ positions* so that exactly $m$ are white has equal probability of being realised: it is the number of such assignments that happen to assign "black" to all $(n+m)/k$ slots in $B$ divided by the size of the sample space (number of all valid assignements).

*I am using a model where the individual available positions in each bag are distinguished, as this is easiest to work with; if one were to work instead with a smaller sample space in which only the number of black (or equivalently white) balls in each bag is recorded, then a uniform distribution would be unrealistic, and the points of this smaller sample space would have to be weighted in such a way as to obtain the same end result, albeit after a more complicated computation.