Unfair Race

$n$ runners in very different training states want to compete in a race. Each one of them is given a different starting number $k$ $(1\leq k \leq n)$ according to the runner’s (constant) individual racing speed being $v_k=\frac{k}{n}$.
In order to give the slower runners a chance to win the race, $n$ different starting positions are chosen randomly (with uniform distribution) and independently from each other within the racing track of length $1$. After this, the starting position nearest to the goal is assigned to runner $1$, the next nearest starting position to runner $2$ and so on, until finally the starting position furthest away from the goal is assigned to runner $n$. The winner of the race is the runner who reaches the goal first.
Interestingly, the expected running time for the winner is $\frac{1}{2}$, independently of the number of runners. Moreover, while it can be shown that all runners will have the same expected running time of $\frac{n}{n+1}$, the race is still unfair, since the winning chances may differ significantly for different starting numbers:
Let $P_{n,k}$ be the probability for runner $k$ to win a race with $n$ runners and $E_n = \sum_{k=1}^n k P_{n,k}$ be the expected starting number of the winner in that race. It can be shown that, for example,
$P_{3,1}=\frac{4}{9}$, $P_{3,2}=\frac{2}{9}$, $P_{3,3}=\frac{1}{3}$ and $E_3=\frac{17}{9}$ for a race with $3$ runners.
You are given that $E_4=2.21875$, $E_5=2.5104$ and $E_{10}=3.66021568$.
Find $E_{1000000}$ rounded to $4$ digits after the decimal point.

This problem involves some aspects of both combinatorics and probability. A detailed solution of this problem would involve a description of expected value and probability distributions.

The probability that runner $k$ is in the leading position equals the chance that the smallest of the first $k$ numbers selected is larger than the smallest of the remaining $n-k$ numbers. This can be computed using combinatorics. Let ${n \choose k}$ denote the binomial coefficient.

$P_{n, k} = \frac{{k \choose k}{{n-k} \choose k}}{{n \choose k}}$

This reflects the number of ways to choose $k$ positions out of $n$ for the first group of runners and $k$ positions out of the remaining $n-k$ for the second group of runners, divided by the total number of ways to choose $k$ runners out of $n$.

The expected starting number of the winner is then the sum of the starting numbers multiplied by their respective probabilities:

$E_{n} = \sum_{k=1}^{n} k P_{n, k}$

However, the above calculation of $P_{n,k}$ and subsequently $E_n$ is computationally expensive for large values of $n$ as required in the problem.

Here, unfortunately, we don’t have targeted techniques to compute the required value for large $n$ quickly, as we can’t simplify $P_{n, k}$ or $E_n$ in ways that would make these computations feasible for $n = 1000000$. This kind of question often appears in coding and computer science related disciplines because brute force methods of directly computing probabilities based on their definitions often fall short, and problems must be solved by developing more efficient algorithms based on patterns or properties that are not immediately obvious.

This problem is a great example of the need for such optimization, as the direct approach for calculating $E_n$ quickly becomes infeasible as $n$ grows. So, without having any numerical or pattern-based method of simplifying the problem, or the use of computational software or a coding language which can handle large numbers swiftly, it is practically impossible to answer the question. For such problems, usually a numerical or simulation-based approach might be used to approximate the answer where analytical methods become implausible. This might involve making some educated guess about the behavior of the function $E_n$ at large $n$ or employing some advanced method of approximation.

If your intention was to calculate this by paper/computer, it seems like a task for which you’re likely to need a good numerical package or coding practice. Writing a program to execute the rigorous calculation is beyond the scope of this explanation.

More Answers: