2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ The mean is straightforward, closed form for probabilities not likely, but good approximations are likely. $\endgroup$ – André Nicolas Jun 24 '14 at 15:32
  • $\begingroup$ 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. $\endgroup$ – user14972 Jun 24 '14 at 16:05
  • $\begingroup$ That said... what information do you actually want to extract from the problem? $\endgroup$ – user14972 Jun 24 '14 at 16:06
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.