4
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Brilliant ! ^3^ $\endgroup$ Dec 26 '19 at 17:22
  • $\begingroup$ Omg i'm v dumb. Thanks for the nice answer!! $\endgroup$
    – hello_123
    Dec 26 '19 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
    Dec 26 '19 at 17:42
0
$\begingroup$

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

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