Задача 573
Нечестный забег

$n$ бегунов очень разной степени физической подготовки хотят соревноваться в беге. Каждому из них дан отличный стартовый номер $k$ $(1\leq k \leq n)$ в соответствии с его (неизменной) личной скоростью бега, равной $v_k=\frac{k}{n}$.
Для того, чтобы дать более медленным бегунам шанс победить в забеге, $n$ различных стартовых позиций выбираются случайно (с равномерным распределением) и независимо друг от друга на беговой дорожке длиной $1$. После этого ближайшая к финишу стартовая позиция назначается бегуну с номером $1$, следующая ближайшая стартовая позиция - бегуну с номером $2$, и так далее, пока, наконец, самая отдаленная от финиша стартовая позиция не будет назначена бегуну с номером $n$. Победителем забега является бегун, первый достигший финиша.

Любопытно, что ожидаемое время бега победителя равно $\frac{1}{2}$ независимо от количества бегунов. Более того, хоть и можно показать, что все бегуны имеют одинаковое ожидаемое время бега, равное $\frac{n}{n+1}$, забег все равно нечестен, так как шансы на победу могут значительно отличаться для разных стартовых номеров:

Пусть $P_{n,k}$ будет вероятностью, с которой бегун номер $k$ победит в забеге с $n$ участниками, и $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}$ и $E_3=\frac{17}{9}$ для забега с $3$ бегунами.
Вам дано, что $E_4=2.21875$, $E_5=2.5104$ и $E_{10}=3.66021568$.

Найдите $E_{1000000}$, округленное до 4 цифр после десятичной точки.

Оригинал
 
© Проект Эйлера | Translated problems from ProjectEuler.net