Surprising Limit of Expected Value of Difference

Question

Let $S_n = \{ 1, 2, \ldots, n \}$. For every non-empty subset $S$ of $S_n$, denote $$\Delta_S = \max S - \min S.$$

What is the expected value of $\Delta_S$ ?

We can compute this as follows. We can form every nonempty subset by first picking a maximum value $k$, then a minimum value $j$ such that $j \le k$. For the calculation, we can ignore the cases where $j = k$ since $\Delta_S = 0$ in that case. Thus, the expected value of $\Delta_S$ is

$$\frac{1}{2^n - 1} \sum_{k = 1}^n \sum_{j = 1}^{k - 1} (k - j) 2^{k - j - 1}. $$

Evaluating this sum, we get

$$\mathbb{E}[\Delta_S] = \frac{(n - 3)2^n + (n + 3)}{2^n - 1}.$$

While trying to understand the behavior of this quantity, I noticed that

$$\lim_{n \rightarrow \infty} n - \mathbb{E}[\Delta_S] = 3.$$

This result is very unintuitive to me. Can anyone provide an insight to why such a beautiful and surprising fact holds?

Answer 1

$\Delta$ only depends on the extremal values. By counting these 'extremal probabilites', we have $P(\Delta=n-1) = P(1\in S, n\in S)=1/4$, $P(\Delta=n-2)=P(1\notin S,2\in S, n\in S) + P(1\in S, n-1\in S, n\notin S)=2 \times 2^{-3}$, etc... so $P(\Delta=n-k)= k \times 2^{-(k+1)}$ for $k<n/2$. The average of $n-\Delta$ converges as $n\rightarrow \infty$ to $$ \sum_{k\geq 1} k^2 2^{-(k+1)} =3 .$$ (Thanks to Did for checking)

Answer 2

Toss a coin to decide whether $1$ is included, then another to decide whether $2$ is included, then another to decide whether $3$ is included, etc.

What is the average value of the first one included? I.e., on average, how many times do you toss the coin in order to get one "head"? Since there are two equally probable outcomes, the answer is $2$.

Similarly with $n$, then $n-1$, then $n-2$, then $n-3$, etc.: The average is $n-1$.

So $(n-1) -2 = n-3$.

(This is of course about the limit, not about the exact value for finite $n$. If one cannot toss the coin more than $n$ times, then the average gets smaller, with this complication: What if the random set has no elements? What is the value of the minimum then? Or the maximum? If it has just one element, then the difference -- the range, as it is usually called -- is $0$.)