In a queue of $n$ people, what is the average number of spaces in between two people?

Question

There are $n$ people in a queue. You randomly select two of them. What is the expected number of people standing in between them?

I noticed that the question can be reformulated in the following way. Let $X$ and $Y$ be discrete random variables that can take values between $1$ and $n$. What is $\mathbb{E}(|X-Y|-1 \text{ given that $X\neq Y$})$?

Unfortunately, this didn't seem to get me anywhere. I also considered what the probability was for small values of $n$. Let $Z$ be the number of people standing in between the two people. For $n=2$, $Z=0$ trivially. For $n=3$, there is a two-thirds chance that the people are standing next to each other, and a one-third chance that they are on either side of the queue. So $E(Z)=\frac{2}{3}\cdot0+\frac{1}{3}\cdot1=\frac{1}{3}$. I also calculated it for $n=4$, but stopped after that point since the calculations were getting unwieldy.

Could anyone hint at what approach I could use instead?

Answer 1

Let $p_i$ be the probability of a pair of randomly selected people having distance $i$.

You can easily observe that $$p_i=\frac{n-i-1}{\binom{n}{2}}$$ because the good cases are pairs $(1;i),(2;i+1),...,(n-i-1;n)$ and all the cases are $\binom{n}{2}$ (because that is the number of pairs.

Your expected value is $$\sum_{i=0}^{n-1}i\cdot p_i=\sum_{i=0}^{n-1}i\cdot\frac{n-i-1}{\binom{n}{2}}=\frac{1}{\binom{n}{2}}\cdot\sum_{i=1}^{n-1}i(n-i-1)=\frac{1}{\binom{n}{2}}\cdot\bigg(\frac{n(n-1)^2}{2}-\frac{(n-1)n(2n-1)}{6}\bigg)=$$$$=\frac{2}{n(n-1)}\cdot\frac{n(n-1)}{2}\cdot\bigg(n-1-\frac{2n-1}{3}\bigg)=\frac{n-2}{3}$$

Answer 2

Update: Just realized there's a simple way: pick any three people at random, there are $n \choose 3$ ways. Fix the two people at both ends, the total number of cases are the same as the number of people in between them. Therefore the expected value is $\frac{n \choose 3}{n \choose 2} = \frac{n-2}{3}.$

---

By symmetry $$E(|X-Y|-1 \mid X \ne Y) = E[X-Y-1|X>Y]=\frac{\sum_{y=1}^{n-1} {n-y \choose 2} }{n \choose 2} = \frac{n \choose 3}{n \choose 2} = \frac{n-2}{3}$$

where we used the fact that if $Y=y$, total "distance" when $X$ runs from $y+1$ to $n$ is $n-y \choose 2$.

---

A baby example: $$\begin{array}{c} & X=1 & 2 &3 &4 &5 & \rm Total\\ Y=1 &&0 &1 &2 & 3 & 6\\ 2 &&&0&1&2 & 3\\ 3 &&&&0&1 & 1\\ 4 &&&&&0 & 0\\ \rm Total &&&&&0 & 10\\ \end{array}$$

Answer 3

The sum of the number of spaces between two people is $$\sum_{i=1}^{n-1} \sum_{j=i+1}^n (j-i-1) = \sum_{i=1}^{n-1} \binom{n-i}{2} = \sum_{k=0}^{n-2} \binom{k+1}{2} = \binom{n}{3},$$ so the average is $$\frac{\binom{n}{3}}{\binom{n}{2}} = \frac{n-2}{3}.$$