Calculating probabilities around “overlapping” events.

Question

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.

Answer 1

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.