Variance of the number of balls between two specified balls 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.
 A: 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.
A: 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}
$$
A: 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.
