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:
- There are $a_0$ universes where $0$ buckets overlap, i.e. $p$ distinct buckets with water.
- There are $a_1$ universes where $1$ bucket overlaps, i.e. $p-1$ distinct buckets with water.
- 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.