We choose $5$ numbers from $1$ to $100$. We order them by value. What is the expected difference between the second and the third?

Question

I came across this peculiar problem.

We choose $5$ numbers from $1$ to $100$ (with repetition). We order them in decreasing order by value. What is the expected difference between the second and the third?

For example, we draw $6,67,89,45,33$. Difference is $67-45=22$.

Answer 1

If instead of $n=100$ possibilities we have a large $n$, the expectation converges to $n/6$. In fact, if we select numbers without replacement rather than with (which makes a negligible difference when $n$ is large), the expectation is exactly $\frac16(n+1)$. Here's a way to see that:

First, change the game to be:

We have $n+1$ chairs arranged in a circle. Select one chair at random, remove it from the circle. That leaves a chain of $n$ chairs. Select 5 of those chairs at random, and count the gap between the second and third selected chair.

It should be clear that this gives the same answer -- the business with making a circle and cutting it into a line is completely irrelevant. However, now we can modify the rules further to

We have $n+1$ chairs arranged in a circle. Select six chairs at random. Now pick (still at random) one of the six chairs, remove it, unfold the rest to a line, and count the gap between the second and third selected chair.

Doing the random choices in a different order shouldn't change anything, so we still get the sought-for answer. One more reformulation:

We have $n+1$ chairs arranged in a circle. Select six chairs at random. Start from a random chair among the selected six chairs and walk clockwise. Count how many chairs appear between the second and third time you walk past a selected chair.

And finally:

We have $n+1$ chairs arranged in a circle. Select six chairs at random. Select one of the six gaps between selected chairs at random, and count how long it is.

In the original formulation the expected size of the different gaps were not obviously the same -- but now all of the apparent asymmetry in that description has been removed. By symmetry the expected length of the random gap can only be one sixth of the total length of the circle (because that is the sum of the 6 possibilities we choose uniformly between in the second choice).

---

It gets somewhat trickier with replacement because the chair where we break the circle cannot be selected again in the next choices of the original game, so reformulating the game doesn't give us perfect symmetry. That must be why Patrick Stevens' exact answers don't show a simple 6 in the denominator.

By this reasoning we also get $n/6$ exactly if you uniformly choose 5 real numbers in $[0,n)$ (in which case replacement doesn't matter at all).

Answer 2

Value equal

$$\frac{N\text{(umerator)}}{D\text{(enominator)}}$$

I ran into trouble trying to enumerate where the order that the numbers are chosen doesn't matter, so I've gone in the other direction.

$$D = (100)^5.$$

$N$ will be calculated by going through all of the various summations, and attaching a weight to them. In the double summation below, the weight is $(b-a)$ and the number of entries represents the number of ways having exactly 2 numbers $\leq a$ and 1 number $\geq b$.

$$ \binom{5}{3} \times \sum_{a=1}^{99} [f(a)] \left[\sum_{b=a+1}^{100}(b-a)[g(b)]\right].$$

Since the denominator is computed by assuming that the order that the numbers are selected is relevant, the numerator must be computed in a consistent manner. The first factor reflects the number of ways that 3 slots, can be chosen to represent the 3 smaller numbers.

Here, I avoid the complication of $a=b$ by recognizing that since it will be attached the weight of $(b-a) = 0$, ignoring this possibility does not affect the enumeration.

$f(a) = a^3 - (a-1)^3$, where the second term represents the number of ways of having all three numbers less than $a$.

Similarly, $g(b) = (101-b)^2 - (100 - b)^2.$

Answer 3

By extremely dumb use of Mathematica I can give you some values for smaller $n$ than $100$ (though the quintic is getting too big for me to go much further than $30$). You want $n=100$ in the following.

f[n_] := Mean[Subtract @@ Reverse[Sort[#]][[2 ;; 3]] & /@ Tuples[Range[n], {5}]]

For $n=1 \dots 15$, this is:

$$\left\{0,\frac{5}{16},\frac{40}{81},\frac{85}{128},\frac{104}{125},\frac{1295}{1296},\frac{400}{343},\frac{1365}{1024},\frac{3280}{2187},\frac{3333}{2000},\frac{2440}{1331},\frac{20735}{10368},\frac{4760}{2197},\frac{12805}{5488},\frac{25312}{10125}\right\}$$

For $n=20, 25, 30$, this is $\{\frac{53333}{16000},\frac{65104}{15625},\frac{809999}{162000}\}$.

@Roman notes that this is $\frac{n^4-1}{6n^3}$, so by engineer's induction, the answer is $\frac{33333333}{2000000}$, or precisely $16.6666665$.

A proof of this fact is left as an exercise to the reader.

Answer 4

Your problem pertains to the field of Order Statistic.
You have in fact a random sample of five variables (with repetitions allowed) taken from a uniform discrete distribution over $[1,100]$ and want to determine the difference between the second and third highest, which is the case treated in the para

You will see that be able to proficiently apply the concepts and tools of this sector of probability/statistics, you have better to approximately convert your problem to a continuous uniform distribution: with five samples over a width of $100$ that is a quite reasonable approximation.

The best approximation is obtained when you center the discrete values into a unitary continuous interval, i.e. you pass from $[1,100]$ to $[1/2,100+1/2]$.
But since you are considering differences you can shift it to $[0,100]$, and scale down to the standard $[0,1]$.

That said I am not going to repeat here the exposition you can find on the referred Wikipedia article or on many others.