5

Question: Assume we have 100 different balls numbered from 1 to 100, distributed in 100 different bins, each bin has 1 ball in it. What is the variance of the number of balls in between ball #1 and ball #2?

What I did: I defined $X_i$ as an indicator for ball $i$ - "Is it in between balls 1 and 2?" Also I thought of the question as this problem: "We have actually just 3 places to put the 98 remaining balls: before, after and between balls #1,2, so for each ball there is a probability of 1/3 to be in between. So by this we have $E[X_i]= $$1 \over 3$ . Now $X=\sum _{i=1} ^{98} X_i$. Since $X_i$ is a Bernoulli RV then: $V(X_i)=p(1-p)=$$2 \over 9$.

But I know that the correct answer is 549 $8 \over 9$. I know that I should somehow use the formula to the sum of variances, but somehow I don't get to the correct answer.

Bravo
  • 4,413
jreing
  • 3,297
  • Your idea of dealing with 'three places' is not valid, I think, when you condition on the placements of balls 1 and 2. For a given ball the likelihood of being between 1 and 2 depends on the placement of 1 and 2 (when you condition). – A Blumenthal Mar 04 '13 at 17:20

3 Answers3

2

Well, you are right. If we use the formula for the sum of variances,$$ Var (\sum_{i=1}^{98} X_i) = E[(\sum_{i=1}^{98} X_i)^2] - (E[\sum_{i=1}^{98} X_i])^2$$ and expand the sum, we see that the RHS reduces to $$\sum_{i=1}^{98}Var(X_i) + \sum_{j\ne i,j=1}^{98}\sum_{i=1}^{98}(E[X_i X_j]-E[X_i]E[X_j])$$ where $E[X_i X_j]$ equals $1/6$ and $E[X_i]E[X_j]$ equals $1/9$, as stated in the question, and $Var(X_i)$ equals $2/9$.

It evaluates to the answer given. I think the only point of confusion may lie in the fact that $X_i$ and $X_j$ may be assumed to be independent, whereas in fact, they are not. A good way to see this would be to use the argument used in the question to arrive at $E[X_i]$ in the following manner. Take two balls and see in how many ways $ B_1, B_i, B_j,$ and $B_2$ can be arranged such that $ B_1$ and $B_2$ remain at the corners. The other balls are allowed to be anywhere, so they will not affect our probability calculations. The probability comes out to be $\frac{4}{4!}$ and not $1/9$, as one would expect if they were independent.

StrangelyCorrelated
  • 111
1

Denote the number of balls and the the number of bins by $b$. Suppose the first ball lands in bin $X_1$ and second ball lands in the bin $X_2$. The number of balls that will land in between them equals $Z = |X_2 -X_1| - 1$. Clearly $$ \Pr\left( X_1 = m_1, X_2 = m_2 \right) = \frac{1}{b\cdot (b-1)} [ m_1 \not= m_2 ] $$ Thus: $$\begin{eqnarray} \Pr\left(Z = n\right)&=&\sum_{m_1}^b \sum_{m_2=1}^b \frac{1}{b(b-1)} [ m_1 \not=m_2, |m_1-m_2|=n+1] \\ &=& \sum_{m_1}^b \sum_{m_2=1}^b \frac{2}{b(b-1)} [ m_1 > m_2, m_1=n+1+m_2] \\ &=& \frac{b-n-1}{\binom{b}{2}} [ 0 \leqslant n < b-1 ] \end{eqnarray} $$ With this it is straightforward to find: $$ \mathbb{E}\left(Z\right) = \sum_{n=0}^{b-2} n \frac{b-n-1}{\binom{b}{2}} = \frac{b-2}{3} $$ $$ \mathbb{E}\left(Z^2\right) = \sum_{n=0}^{b-2} n^2 \frac{b-n-1}{\binom{b}{2}} = \frac{(b-2)(b-1)}{6} $$ Thus the variance reads: $$ \mathbb{Var}(Z) =\mathbb{E}(Z^2) - \mathbb{E}(Z)^2 = \frac{(b+1)(b-2)}{18} = 549 \frac{8}{9} $$

Sasha
  • 70,631
  • Hi. Thanks for the solution, could you please elaborate how you moved from the 2nd to the third line in the equality of Pr(Z=n), this is the only part I didn't understand. – jreing Mar 05 '13 at 07:23
  • $b-n-1$ is the number of ${m_1,m_2: b \geqslant m_1 > m_2 \geqslant 1, m_1 = n+1+m_2$. It is easiest to draw a box of bots, $b \times b$, and then, for each fixed $m_2$ mark $m_1 = n+1+m_2$. Since $m_1 \leqslant b$ we have $n+1+m_2 \leqslant b$, thus $1 \leqslant m_2 \leqslant n-b-1$. For all other $m_2$ there will be no solutions to the constraints, thus the Iverson bracket will equal 0. – Sasha Mar 05 '13 at 13:22
0

If $X$ is the number of balls between the two labelled $0$ and $1$, clearly $X$ takes values between 0 and 98. The last value comes from the fact that if 0 is in bin 1 and 1 in bin 100 you have exactly 98 balls/bins between them, and this is the only way to get $X=98$. The other extreme case is $X=0$, so both 0 and 1 have to follow each other, and you have 99 ways to put them this way, so there are 99 ways to get $X=0$.

Now for the probability: to get $X=98$ you need to get 1 at bin 1 and 0 and bin 100 and anything inbetween. Also, you have two ways of doing this:(0,1), (1,0). So the probability of $X=98$ is $2 \cdot\frac{1}{100} \cdot \frac{98}{99} \cdot \frac{97}{98} \cdots 1 =2 \cdot \frac{1}{100 \cdot 99} \cdot 1$ or replace $0$ with $1$). To get $X=97$ you either have $1x \cdots 0y$ or $x1 \cdots y0$, where $x,y$ are any number. The probability of this is $2 \cdot \bigg( \frac{1}{100 \cdot 99} +\frac{1}{99} + \frac{1}{98} \bigg)$. Ando so on. At hte end of the day the probability to have $k$ balls inbetween should be something like $$ P(X=98)=2 \cdot \frac{1}{100 \cdot 99}\\ P(X=k)=2 \bigg(\frac{1}{100 \cdot 99} + \sum_{j=1}^{100-(k+2)}\frac{1}{100-j}\bigg), \ 0 \leq k \leq 97 $$
From this you should be able to find MGF, mean and variance.

Alex
  • 19,262