Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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 4 '13 at 17:20

3 Answers 3

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.

share|improve this answer
    
Thanks very much. solved! –  user1685224 Mar 5 '13 at 7:26

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} $$

share|improve this answer
    
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. –  user1685224 Mar 5 '13 at 7: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 5 '13 at 13:22

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.