AtCoder Begginer Contest 194 D Journey　の特に期待値に関して

１．はじめに

AtCoder Begginer Contest 194 D Journey について書きたいと思います。問題概要は、1からNまで、同様に確からしく 1/N で出るとき、2～N までのすべてが出るまでの回数の期待値を求めよというものです。数Ⅲの無限等比級数を使った計算が途中で出てきます。

２．例　サイコロで１の目が出るまでのサイコロを振る回数の期待値

　サイコロで１の目が出るまでのサイコロを振る回数の期待値は、

　のように無限等比級数で得られます。両辺5/6倍して、引き算すると、

　が得られるので、右辺を公式で計算すると、E=6 が得られます。
また、最初の式を変形して、

と変形して、E=6 を得ることもできます。
さて、最後の 式は、

と変形できます。このことは、1回は必ず試行し、確率5/6 で、またE回の試行を行うということを意味しています。AtCoderの公式解説に書かれている式はこのように導出されます。確率p の事象が起こるまでの回数の期待値は、E=1+(1-p)E から、E=1/p となることが分かります。

３．Journeyの実装

はじめは、2～Nの何が出てもよいので、確率は (N-1)/N となるから、期待値は、N/(N-1) となります。その後は、所望の数字が出るごとに、確率は、
(N-2)/N , (N-3)/N , ・・・1/N となっていくので、対応する期待値は、その逆数となります。それらを足し合わせれば答えになります。

n=int(input())
ans=0
for i in range(n-1):
 ans+=n/(n-1-i)
print(ans)