3
$\begingroup$

I'm pondering on this problem which I made up, so am not sure what the right answer is.

Suppose we throw $n$ balls uniformly at random into $N$ bins.

Let's call a sequence of contiguous non-empty bins as a "cluster" and the number of bins in each cluster as the "size" of this cluster.

What would be the expected number of clusters and expected value of cluster size?

Example: Let us have the following 10 bins. (the ones in bold being non-empty).

1 2 3 4 5 6 7 8 9 10

This has two clusters $C_1$ = {1,2,3} and $C_2$ = {8,9} with cluster sizes 3 and 2 respectively.

| cite | improve this question | |
$\endgroup$
  • $\begingroup$ One bin can contain one ball max? $\endgroup$ – Stockfish Nov 9 '18 at 12:28
  • $\begingroup$ @Stockfish Not necessarily. $\endgroup$ – sidharth228 Nov 9 '18 at 12:29
  • $\begingroup$ @Stockfish However, the solution for the simplified (?) problem you suggest would certainly be helpful. $\endgroup$ – sidharth228 Nov 9 '18 at 12:40
  • $\begingroup$ Well then there would be $\binom{N}{n}$ possible events - in your problem the multinomial coefficent is needed $\endgroup$ – Stockfish Nov 9 '18 at 13:06
  • $\begingroup$ if there is at most one ball in each bin, then the probability of any bin being full is clearly $p = \frac nN $, and you can use formula $(\star)$ in my answer below. $\endgroup$ – MJD Nov 9 '18 at 22:35
1
$\begingroup$

Suppose we happen to know that each bin is empty with probability $p$ and full with probability $q=1-p$. Suppose just for argument that the first bin is empty. (The analysis of the other case is exactly the same.) Let's calculate the expected length of the first cluster. It is clearly $$\frac1q$$ because we expect to have to examine $q$ bins before we see the first full one. Similarly, the length of the next cluster is $$\frac 1p$$ because that is how many bins we expect to examine before seeing an empty one. Clusters of empty and full bins must alternate, so the average cluster length $\ell$ is just the average of the two: $$\ell=\frac12\left(\frac1q+\frac1p\right) = \frac12\frac1{p-p^2}.\tag{$\star$}$$

(It's possible that one cluster might be cut short, or missing entirely, but when the number of bins is large, this will not bias the result significantly.)

The expected number of clusters, of course, is just $\frac N\ell$.

The probability $p$ of a bin being empty when there are $N$ bins and $n$ balls is well-studied and I am sure you can find it easily for whatever cases interest you; see for example these notes of John Canny. One common case has $N=n$ and when this is true it is well-known that for large $N$ and $n$, $p=\frac1e\approx 36.8\%$, so from the formula $(\star)$ above we find $$\ell = \frac1{2(e^{-1}-e^{-2})} \approx 2.15013.$$ This accords perfectly with the computer simulations I tried.

(Addendum: I now see you want a cluster to be a sequence of full bins. This is even easier. The expected length of a cluster is $\frac 1q$.)

| 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.