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$

  • 2
    $\begingroup$ Did you read the comments? They provide an explanation. What parts do you understand, and what part are you stuck on? I worry we're going to try to explain again and you're going to say you didn't understand that, either. It would help to edit the question to tell us which parts of the explanation you understood, which you didn't, and what exactly is confusing you. Also try working through an example with small values of $n,k$ (e.g., $n=1$, $n=2$), and see what happens. $\endgroup$ – D.W. Jun 1 '17 at 15:59
  • $\begingroup$ Like, I know how to calculate the expectation of a random variable, but I just couldn't understand why the average distance was $(n+1) / (k+1)$ $\endgroup$ – Rockstar5645 Jun 2 '17 at 16:24

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

| cite | improve this answer | |
  • $\begingroup$ Thank you, it may have been obvious to others but it completely flew over my head. This explanation gave me a good understanding. $\endgroup$ – Rockstar5645 Jun 2 '17 at 16:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.