3
$\begingroup$

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?

$\endgroup$
7
  • $\begingroup$ Do we know anything about the distances between $2$ consecutive people? Can they take any values or are they set? Are they equal? $\endgroup$
    – user799688
    Dec 7, 2020 at 17:18
  • $\begingroup$ @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? $\endgroup$
    – Joe
    Dec 7, 2020 at 17:21
  • $\begingroup$ 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.) $\endgroup$
    – user799688
    Dec 7, 2020 at 17:22
  • 2
    $\begingroup$ 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) $\endgroup$
    – E-A
    Dec 7, 2020 at 17:27
  • 1
    $\begingroup$ @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! $\endgroup$
    – E-A
    Dec 7, 2020 at 18:44

3 Answers 3

2
$\begingroup$

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

$\endgroup$
0
2
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .