# Calculating probabilities around “overlapping” events.

## Problem

Suppose we have $n$ buckets, and we randomly select $p$ buckets to fill with water—a filled bucket may be chosen again. If we now randomly select $q$ buckets, how many of them will have water?

## Thoughts

If the $p$ buckets were guaranteed to be distinct, then it's a simple problem.

But once overlapping buckets are introduced, I first imagine a naive expansion as follows:

1. There are $a_0$ universes where $0$ buckets overlap, i.e. $p$ distinct buckets with water.
2. There are $a_1$ universes where $1$ bucket overlaps, i.e. $p-1$ distinct buckets with water.
3. There are $a_2$ universes where $2$ buckets overlap, but here, there may be $p-2$ or $p-1$ buckets that are distinct, since 3 "pours" may have filled one bucket.

I don't think this is the right way to think about the problem.

I'll edit my question as I come up with alternate approaches, but this isn't a homework problem (rather, it's a simplification of a real-world problem regarding execution collisions in a stock exchange), so I don't have any reference material or any assurance that this is something practical to figure out with little practice in probability.

• The mean is straightforward, closed form for probabilities not likely, but good approximations are likely. – André Nicolas Jun 24 '14 at 15:32
• It might be useful to reorder the problem: pick the $q$ buckets first, randomly decide how many (up to $p$) times to fill one of them with water, then each time randomly pick one of the $q$ buckets to fill with water. – user14972 Jun 24 '14 at 16:05
• That said... what information do you actually want to extract from the problem? – user14972 Jun 24 '14 at 16:06

Let $N$ be the random variable that denotes the number of buckets that are filled with water after selecting $p$ buckets to fill with replacement. Let $X$ be the random variable that denotes the number of buckets that are filled with water that are observed from a selection of $q$ buckets without replacement. Then we want the probability distribution for $X$; i.e., $$\Pr[X = x] = \sum_{k=1}^n \Pr[X = x \mid N = k]\Pr[N = k]$$ by the law of total probability. In turn, we need to establish $\Pr[N = k]$ for the fixed parameters $n,p$. This is not trivial, since $$\Pr[N = k] = \frac{n! \, S(p,k)}{(n-k)! \, n^p},$$ where $S(p,k)$ is the Stirling number of the second kind. The conditional probability $$\Pr[X = x \mid N = k] = \frac{\binom{k}{x}\binom{n-k}{q-x}}{\binom{n}{q}}$$ is hypergeometric. The resulting sum is the desired probability distribution, which does not appear to have an elementary closed form.