Suppose we have n balls $b_1, b_2,\cdots , b_n$ and n boxes. Each ball is placed into a box chosen independently and uniformly randomly. A colliding pair is defined as $(b_i,b_j)$, where $i<j$ and $b_i$ and $b_j$ are placed in the same box. We are asked to evaluate the expected number of colliding pairs.

What I did -

Clearly, for any $k$-set of balls in some box, there are $\binom{k}{2}$ colliding pairs in that box.

Next if $C$ is the total number of colliding pairs after randomly placing all the balls in boxes,

$E[C] = E[C_1+C_2+\cdots+C_n]=\displaystyle\sum_{i=1}^{n}E[C_i]=nE[C_k]$

where $C_k$ is the number of colliding pairs in box $k$ and $E[C_k] = E[C_1]=E[C_2]=\cdots$ .

Now as each box will have $\binom{i}{2} = i(i-1)/2$ colliding pairs if the box contains $i$ balls, we can calculate the expected value as follows -

$\begin{align} nE[C_k] &= n\left(\displaystyle\sum_{i=2}^{n}\binom{i}{2}\text{Pr}\left[i(i-1)\text{ colliding pairs in box k}\right]\right) \\&= n\left(\displaystyle\sum_{i=2}^{n}\binom{n}{i}\dfrac{i(i-1)}{2}\left(\dfrac{1}{n}\right)^i\left(\dfrac{n-1}{n}\right)^{n-i}\right)\end{align}$

This can be calculated using various tricks like differentiating the $(1+x)^n$ binomial expansion and so on.

But, the answer $E[C] = \dfrac{n-1}{2}$. Given that the answer is so simple, is there a much simpler/slicker/quicker way to see it?


2 Answers 2



Yes. Whenever you are asked to find an expected value, always check to see if you can use the linearity of expectations. Remember that linearity of expectations apply even when variables are dependent!

For any pair $i < j$, let $X_{ij}$ be the indicator variable for whether $(i,j)$ is a colliding pair.

  • What is $E[X_{ij}]$?

  • How many pairs are there?

  • Use linearity of expectation...

Lemme know if you need further help.

  • $\begingroup$ Brilliant ! ^3^ $\endgroup$ Commented Dec 26, 2019 at 17:22
  • $\begingroup$ Omg i'm v dumb. Thanks for the nice answer!! $\endgroup$
    – hello_123
    Commented Dec 26, 2019 at 17:40
  • $\begingroup$ @hello_123 - missing shortcuts / tricks in math, esp. in probability, is commonplace and happens to all of us. don't worry about it! :) $\endgroup$
    – antkam
    Commented Dec 26, 2019 at 17:42

Continuing the OP's solution, let $B_{1}$ denote the number of balls in box $1$, so $C_{1}=\dbinom{B_{1}}{2}=\dfrac{B_{1}\left( B_{1}-1\right) }{2}$.

Next, one can write $B_{1}=I_{1}+I_{2}+\ldots+I_{n}$, where $I_{k}=\left\{ \begin{array} [c]{l}% 1\text{, if the ball }k\text{ is in box }1\\ 0\text{, otherwise}% \end{array} \right. \quad (k=1,2,\ldots,n)$.

Then $E\left[ B_{1}\right] =\sum_{k=1}^{n}E\left[ I_{k}\right] =\sum _{k=1}^{n}\underbrace{P\left( \text{the ball }k\text{ is in box }1\right) }_{p_{k}}=n\cdot\dfrac{1}{n}=1$. The mutual independence of $\left\{ I_{k}\right\} $ assures that $V\left[ B_{1}\right] =\sum_{k=1}^{n}V\left[ I_{k}\right] =\sum_{k=1}^{n}\left( p_{k}-p_{k}^{2}\right) =n\left( \dfrac{1}{n}-\dfrac{1}{n^{2}}\right) =\dfrac{n-1}{n}$.

Concluding, \begin{align*} E\left[ C\right] & =nE\left[ C_{1}\right] =\dfrac{n}{2}\left( E\left[ \left( B_{1}-1\right) ^{2}+B_{1}-1\right] \right) \\ & =\dfrac{n}{2}\left( E\left[ \left( B_{1}-E\left[ B_{1}\right] \right) ^{2}\right] +E\left[ B_{1}\right] -1\right) \\ & =\dfrac{n}{2}\left(V\left[ B_{1}\right] +1-1\right)=\dfrac{n-1}{2}. \end{align*} .


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .