1
$\begingroup$

The set-up

Suppose that you have $n$ bins, $i$ of which already contain at least 1 ball. Suppose that you sequentially toss balls into those bins during a predefined number of rounds.

The rules

The rules to toss the balls are as follows:

  • We suppose that the bins are labelled from $1$ to $n$.
  • The game is played during $i$ rounds, $1 \leq i \leq n$. This is the same $i$ as before, i.e., the number of bins that already contain at least one ball.
  • During each round, each of the $i$ bins that contains at least one ball is allowed to toss $f \in \mathbb{N}^{\ast}$ balls, no more, no less.
    • A bin is not allowed to send a ball to itself,
    • it has to choose a random sample of $f$ other bins to send its balls to (i.e., $f$ other bins will receive one ball from this bin).

One toy-size example

Suppose that $n = 5$, $f = 2$ and that bins $1$ and $2$ already contain some balls.

  • Bin $1$ can send balls to bins $\{(2,3), (2,4), (2,5), (3,4), (3,5), (4,5)\}$,
  • Bin $2$ can send balls to bins $\{(1,3), (1,4), (1,5), (3,4), (3,5), (4,5)\}$.

In the end, $2, 3$ or $4$ bins will receive balls during this game. Moreover, $1$, $2$ or $3$ bins that did not contain balls previously will receive some balls for the first time.

Questions

  1. What is the distribution of the number of bins that receive at least one ball during the game?
    E.g. with the previous example what is $\mathbb{P}[2$ bins receive at least one ball$]$? What is $\mathbb{P}[3$ bins receive at least one ball$]$? Etc.
    Can we compute the expected value and variance of this distribution?

  2. What is the distribution of number of bins that received some balls for the first time?
    E.g. with the previous example what is $\mathbb{P}[1$ bin receive at least one ball for the first time$]$? What is $\mathbb{P}[2$ bins receive at least one ball for the first time$]$? Etc.
    Can we compute the expected value and variance of this distribution?


My thoughts for the moment

If I relax the assumption that a bin cannot send a ball to itself, I can get the distribution for the first question. It is the following: $$\mathbb{P}[j \text{ bins receive at least one ball}] = \binom{n}{f}^{-i} \times \binom{n}{j} \sum_{k = f}^{j} (-1)^{j-k} \binom{j}{k} \binom{k}{f}^i.$$ Please see [1] for details about this.

The expression $ A = \binom{n}{j} \sum_{k = f}^{j} (-1)^{j-k} \binom{j}{k} \binom{k}{f}^i$ counts the number of cases where $j$ bins receive at least one ball, when $i$ samples of size $f$ are drawn from a population of size $n$. (Note also the similarity with Stirling numbers of the second kind: $S_2(n,j) = \frac{1}{j!} \sum_{k=0}^{j} (-1)^{j-k} \binom{j}{k}k^n$.)
I am wondering if the following assertion is true: if I remove the samples where bin $l$ sent a ball to itself from $A$, I get the number of cases where $j$ bins receive at least one ball when drawing $i$ samples of size $f$ from a population of size $n-1$.

I am stuck at this point, and I have no idea how to tackle the second question. Feel free to ask for more details, or point me to references if you heard about a similar problem.


[1]: Johnson, N.L. and Kotz, S., 1977. Urn models and their application; an approach to modern discrete probability theory. p. 164, eq. (3.110).

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.