Vertical sticks challenge explanation

Question

This is a question based on this one

I've also tried this problem but I can't seem to understand Henry's solution to it.

Why is the average distance between the sticks $(n+1) / (k+1)$ and not $n/ k$

Answer 1

Let me first repeat the setting. There are $k$ sticks, one of them distinguished. We randomly choose $k$ different positions for them from $1,\ldots,n$, and put a special stick at $0$. How far to the left of the distinguished stick is the closest stick?

The trick here is to observe that we obtain the same distribution if we first choose positions for the sticks and then permute the $k$ sticks (without changing the set of $k$ positions). This is equivalent to choosing the $k$ positions and then choosing one of the sticks at random as the distinguished one. If the positions are $i_1 < \cdots < i_k$, the average distance to the left is $$\frac{(i_1 - 0) + (i_2 - i_1) + \cdots + (i_k - i_{k-1})}{k} = \frac{i_k}{k}. $$ Therefore the average distance to the left is $\mathbb{E}[i_k]/k$.

It remains to compute the average position of the maximum of $k$ distinct random positions. There is probably a smart way of doing that; here is a brute force calculation. The number of choices in which the maximum is $\ell$ is exactly $\binom{\ell-1}{k-1}$. Hence the average is $$ \frac{1}{\binom{n}{k}} \sum_{\ell=k}^n \ell \binom{\ell-1}{k-1} = \frac{k}{\binom{n}{k}} \sum_{\ell=k}^n \binom{\ell}{k} = \frac{k}{\binom{n}{k}} \binom{n+1}{k+1} = \frac{k(n+1)}{k+1}. $$ Overall, we get that the average distance to the left is $$ \frac{1}{k} \cdot \frac{k(n+1)}{k+1} = \frac{n+1}{k+1}. $$