試行回数の期待値は確率の逆数？ABC194Dの解説と考え方

問題

ABC194 の D 問題

[要約]n 個の頂点のグラフがあり、最初は頂点 1 にいる。
一回の試行でランダムに頂点を選び連結にしていく。
すべての頂点を連結にするときの、試行回数の期待値を求める。

つまり、頂点すべてを一回以上訪れるまで平均して何回試行を行うかを求める問題。

「私の知らない知識が載っている、ほう」

確率$p(p \neq 0)$で成功する試行を、成功するまで行うときの試行回数(最後の成功した回も含む) の期待値は$\frac{1}{p}$である
https://atcoder.jp/contests/abc194/editorial/823

「そうか、期待値は確率の逆数なんだ！完全に理解した！」(← 圧倒的早とちり）

「そしたら n 個をすべて連結にする確率は、

$$\frac{n-1}{n} \times \frac{n-2}{n} \times \frac{n-3}{n} \times \cdots \times \frac{1}{n} = \frac{(n-1)!}{n^{n-1}}$$

で、期待値は$\frac{n^{n-1}}{(n-1)!}$！？！？」

もちろんこんなはずもなく、この固定観念に縛られなかなか抜け出せなかった。

唐突に導き出した、$\frac{(n-1)!}{n^{n-1}}$。これはもちろんすべてを連結にするときの確率だが、正確には「n-1 回の試行回数で、n 個の頂点すべてを連結にするときの確率」であって、

このマルコフモデルを最短でゴールまでたどりつくときの確率である。

本来ならばゴールにつくまでに、1,2,3,3,3,4,4,5,6,7,7,n のように同じところで何周も自己ループしたり、必ずどこかで道草を食うはず。

つまり、「n-1 回の試行回数で、n 個の頂点すべてを連結にするときの確率」を逆数にして「n 個の頂点すべてを連結にするときの試行回数の期待値」などと騒ぎ立てるは圧倒的に間違っている！！！

(自問自答おわり)

n 個の頂点のうち、すでに訪れた(連結)頂点の個数のマルコフモデルを考える。

ここで、それぞれの状態にいるとき、前のデータの影響を受けないことが大事。

例えば状態 1 から 2 になる時と状態 2 から 3 になる時は、互いに影響を与えることはないので、独立に考えることができる。

そして、頭をこんがらがらせるこの定理

確率$p$で起きる事象が起きるまでの試行回数の期待値は$\frac{1}{p}$
http://zakii.la.coocan.jp/enumeration/32_bernoulli_k.htm

abc194 の問題のように状態が次から次へ変わっていく問題では落ち着いて考えることが必要。

あくまでこの定理は状態 A から状態 B に推移する、そのときのみに使える定理であって abc194 の問題を考える時は、ステップごとに分けて考える。

まず、連結の大きさが 1 の状態から、連結の大きさが 2 である状態になる確率と期待値を求める

全体で n 個ある頂点から、まだ訪れていない頂点 n-1 個を訪れる確率は$\frac{n-1}{n}$

そしてその期待値は、確率 p で起きる事象が起きるまでの試行回数の期待値は$1/p$を使うと$\frac{n}{n-1}$

よって、状態 1 から状態 2 になるまで、平均して$\frac{n}{n-1}$回の試行を行えば次のステップへすすめる。

連結の大きさが 2 の状態から、連結の大きさが 3 である状態になる確率と期待値を求める

全体で n 個ある頂点から、まだ訪れていない頂点 n-2 個を訪れる確率は$\frac{n-2}{n}$

そしてその期待値は、$\frac{n}{n-2}$

よって、状態 2 から状態 3 になるまで、平均して$\frac{n}{n-2}$回の試行を行えば次のステップへすすめる。

また、状態 1 から状態 3 になるまで、平均して$\frac{n}{n-1} + \frac{n}{n-2}$試行を行えば次のステップへすすめる。

連結の大きさが i の状態から、連結の大きさが i+1 である状態になる確率と期待値を求める

全体で n 個ある頂点から、まだ訪れていない頂点 n-i 個を訪れる確率は$\frac{n-i}{n}$

そしてその期待値は、$\frac{n}{n-i}$

よって、状態 i から状態 i+1 になるまで、平均して$\frac{n}{n-i}$回の試行を行えば次のステップへすすめる。

また、状態 1 から状態 i になるまで、平均して$\frac{n}{n-1} + \frac{n}{n-2} + \cdots + \frac{n}{n-i}$試行を行えば次のステップへすすめる。

以上のことから、状態 1 から状態 n になるまでの操作回数の期待値は、平均して何回試行を行うかということに等しいので、

$$\frac{n}{n-1} + \frac{n}{n-2} + \cdots \frac{n}{1} = \sum_{i=1}^{n-1} \frac{n}{n-i}$$