Imagine a race with $n$ runners, all equally skilled so that the outcome is just based on luck. If the race is run $m$ times, what are the chances that two runners end up with the same exact average rank? I want to know if there is a closed-form solution.

Here is a more formal statement of the problem. Consider permutations $\sigma_1, \ldots, \sigma_m$ of $\mathbb{N}_n$ drawn uniformly at random. What is the probability that there exist $i,j \in \mathbb{N}_n$ such that $i \neq j$ and $\sum_{k=1}^{m}\sigma_k(i) = \sum_{k=1}^{m}\sigma_k(j)$?

  • 1
    $\begingroup$ For two runners, it's the same as the probability of having the same number of heads and tails after $m$ flips of a fair coin, so $0$ if $m$ is odd and ${m \choose m/2}(.5)^m$ if $m$ is even. $\endgroup$ – user113102 Apr 23 at 14:43
  • $\begingroup$ For 2 races, the probability for $n$ runners is $1-\frac{a(n)}{n!}$, where $a(n)$ is the sequence oeis.org/A099152. This makes me think it's pretty hard in general. $\endgroup$ – user113102 Apr 23 at 16:41

Your Answer

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

Browse other questions tagged or ask your own question.