# Expected number of collisions for balls and bins problem

$n$ number of balls are thrown randomly to $m$ number of bins, standing in a row. The balls are labeled as $1,2,3,....n$ and bins are also labeled as $1,2,3,...,m$. The probability of $i_{th}$ ball enters in the $j_{th}$ bin is $p_{ij}$ where $\sum_{j=1}^{m}p_{ij}=1$ for all $i$. What is the expected number of collisions when all $n$ balls are thrown? Assume that balls enter into the bins are independent events (e.g the event 1st ball goes to the 5th bin and 3rd ball enters to the 5th bin are independent events).

Clarification: Note that we count collisions over distinct and unordered pairs, that is, if three balls fall into one bin, three collisions are counted.

• Here you find the expected number of collisions for birthdays, that can be translated for balls in bins. – xecafe Mar 19 '15 at 17:47

The chance that balls $i$ and $k$, $i\ne k$, enter the same bin $j$ is $p_{ij}p_{kj}$ because these balls are thrown independently. Since they cannot collide in more than one distinct bin, and a collision must occur in some bin, the chance that these balls collide anywhere is the sum over bins of their chances of collision:

$$\Pr(i\text{ and }k\text{ collide}) = \sum_{j=1}^m p_{ij}p_{kj}.$$

This chance also is the expected number of collisions of balls $i$ and $k$. Summing over all distinct balls gives the expected total number of collisions $N$ (because expectation is linear):

$$\mathbb{E}(N) = \sum_{1\le i\lt k \le n} \sum_{j=1}^m p_{ij}p_{kj}.$$

This can be written in matrix form in terms of the matrix $\mathbb{P} = (p_{ij})$ and the constant $n$-vector $\mathbf{1} = (1,1,\ldots, 1)^\prime$ as

$$\mathbb{E}(N) = \frac{1}{2}\left(\mathbf{1}^\prime \mathbb{P}\mathbb{P}^\prime\mathbf{1} - Tr(\mathbb{P}\mathbb{P}^\prime)\right).$$

Simulations support the correctness of this result. For instance, the following R code simulates $10,000$ throws of $n=5$ balls into $m=8$ bins using randomly generated probabilities $p_{ij}$. (Note the implementation of the formula for $\mathbb{E}(N)$: it takes just two simple lines at the end where q and then the answer f are calculated.) Its output is

   Mean      SE Formula       Z
1.3489  0.0113  1.3487  0.0200


This states that the formula for $\mathbb{E}(N)$ is $1.3487$, whereas the average number of collisions observed is $1.3489\pm 0.0113$, which is just $Z=0.02$ standard errors away from the formula (indicating very close agreement). Similarly close agreement is obtained when varying either $n$ or $m$.

#
# Generate a random transition matrix.
#
n <- 5
m <- 8
set.seed(17)
p <- matrix(rexp(n*m), n)
p <- p / rowSums(p)
#
# Throw balls into bins.
#
throw <- function(p) {
sum(choose(table(sapply(1:nrow(p), function(i) sample(1:ncol(p), 1, prob=p[i, ]))), 2))
}
sim <- replicate(1e4, throw(p))
#
# Compare the results to the formula
#
mu <- mean(sim)
se <- sd(sim) / sqrt(length(sim))
q <- crossprod(t(p))
f <- sum(q[lower.tri(q)])
(round(c(Mean=mu, SE=se, Formula=f, Z=(mu-f)/se), 4))

• Thank you. Why did you choose the rexp? – Antoni Parellada Nov 20 '15 at 16:02
• @Antoni Because on each line of the transition matrix $\mathbb{P}$ it generates probabilities that look like the gaps in a uniform distribution of points in the interval $[0,1]$. That's a natural, quick, and easy way to generate random probabilities. For a different distribution, you could replace rexp by any number generation process (random or not) that produces nonnegative values. – whuber Nov 20 '15 at 16:07

If I understood well the problem, the answer should be the sum of binomial distributions.

Pick for example one bin. Being that every bin have the same probability of receive a ball, then the probability of a ball to fall in that chosen bin is 1/m. So you calculate the expectation of the binomial variable with n balls and p = 1/m of having more than 1 ball in a bin. And then make the sum over all the bins.

EDIT To give you a formula. First, give that n can be big, it's better to calculate the probability of a ball not falling in the bin or only falling once. That is: $$P(x=0 \, or \, x=1) = (1-1/m)^n + n(1/m)(1-1/m)^{n-1}$$ so the probability of having n ball colliding should be $$P = m\left[1 - (1-1/m)^n - n(1/m)(1-1/m)^{n-1}\right]$$

• How does this address the more general case of different probability distributions for different balls? How do you incorporate the $p_{ij}$ in the question? – whuber Nov 20 '15 at 15:29
• Its not the general formula, and while I like to believe this problem is way easily solved numerically, you can calculate the probability of every ball to fall in a given bin, and make a summation, while I multiplied by m, using the hypothesis that the probabilities are equal. It's still binomial, but it's a mess to write it analytically. At that point I think the problem is to find a suitable way to factorize. But you are right, my answer isn't a solution of the question. – Leonardo Herbas Nov 20 '15 at 15:38
• I believe that even in the case $p_{ij} = m$ your solution is incorrect. Consider the situation of $m=1$ bin. All balls must collide, giving $\binom{n}{2}$ separate collisions (according to the clarification at the end of the question), whereas your formula gives the value $1$. – whuber Nov 20 '15 at 15:53
• Yes, because my formula gives the probability of two or more balls falling in the bins, then the expectation value would be n*P. In the case of 1 bin, the probability of balls falling in that bin is 1, so the expectation value is n collisions. – Leonardo Herbas Nov 20 '15 at 15:58
• Close: you need to count the combinations in each bin. That, at least, is how I have understood the clarification. This interpretation is consistent with the example in the clarification which offers the case of three balls in a bin: $\binom{3}{2} = 3$ as stated. – whuber Nov 20 '15 at 16:10