0%

Problem 573


Problem 573


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 his (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.


不公平的比赛

$n$名处于不同训练状态的跑步选手想要进行一场比赛。他们每个人拥有一个不同的初始编号$k$ $(1\leq k \leq n)$,相应地他们各自(固定的)跑步速度为$v_k=\frac{k}{n}$。
为了让跑得慢的选手也有获胜的机会,在长度为1的跑道上独立地(遵循均匀分布)随机选择$n$个不同的起跑位置,然后,离终点最近的起跑位置被指派给1号选手,次近的起跑位置被指派给2号选手,依此类推,最远的起跑位置被指派给$n$号选手;最先到达终点的选手获胜。

有趣的是,无论有多少名选手参赛,获胜者的跑步时长的期望总是$\frac{1}{2}$。进一步地,尽管可以计算得出,任意一名选手的跑步时长的期望都是$\frac{n}{n+1}$,比赛仍然是不公平的,表现在不同初始编号的选手获胜的概率仍然有巨大的差别。

记$P_{n,k}$为有$n$名选手参赛时$k$号选手获胜的概率,则$E_n = \sum_{k=1}^n k P_{n,k}$为获胜选手编号的期望值。例如,通过计算可以得出,
$P_{3,1}=\frac{4}{9}$,$P_{3,2}=\frac{2}{9}$,$P_{3,3}=\frac{1}{3}$,因此对于有3名选手参加的比赛$E_3=\frac{17}{9}$。
已知$E_4=2.21875$,$E_5=2.5104$以及$E_{10}=3.66021568$。

求$E_{1000000}$,保留小数点后4位小数。