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?
Best Answer
HINT
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.