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

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?

• Do we know anything about the distances between $2$ consecutive people? Can they take any values or are they set? Are they equal?
– user799688
Dec 7, 2020 at 17:18
• @Vlad. Sorry, I don't understand what you mean. When I say 'distance', all I mean is the number of people standing in between the two randomly selected people. Does that answer your question?
– Joe
Dec 7, 2020 at 17:21
• Yes, that does answer my question, thanks. I think you better explain that and edit your post. I thought that by "distance" you literally meant how much space is inbetween $2$ people (1 meter, 3 meters, etc.)
– user799688
Dec 7, 2020 at 17:22
• It should be (n-2)/3. You can prove it by putting n+1 people around in a circle, and picking one of them uniformly as the start of the queue (and then taking them out the queue). The result will then follow by symmetry. (This is very much a discrete analog of a continuous argument)
– E-A
Dec 7, 2020 at 17:27
• @String some function of laziness (I have to care about rigor and presentation when I write an answer) and uncertainty on whether my answer is sufficiently accessible and correct and not wanting to depress turnout for other potential good answers; thanks for the compliment though!
– E-A
Dec 7, 2020 at 18:44

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

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

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