期待値問題、確率問題のDPをほんのちょっと勉強した

初めに

自分はこの記事で勉強しました(まだ読み切ってないけど、必要な分だけ)
https://compro.tsutaj.com//archive/180220_probability_dp.pdf
期待値と条件付確率 - math314のブログ

特に上のほうのリンクの「初級編」の話（以下、初級編）の話が中心です。

自分が記事を読んで解釈したこと(やそこから発展した妄想)から、AtCoderの過去問を一問解説します。記事には不十分な点があると思います。ごめんなさい。
間違いがあることに気づいた方は一報くださると幸いです。修正します。
自分もまだまだ勉強中です。新しいノウハウを手に入れたらまた記事にしたいですね。

この記事では理論的な話や証明はほぼほぼ無しで、感覚的な話のみで構成されています。そういうのが苦手な方はブラウザバックか、別の記事で理論を補完するなどお願いします。

理論的な部分は上で紹介したリンクや、「条件つき期待値」等で調べると役に立つかもしれません

今回の問題

ABC194-D Journey
atcoder.jp

ABC194バチャやりたい人とかいたら困るのでここで「続きをみる」さんに登場してもらいます。

問題概要
N頂点辺無しのグラフに高橋君が頂点1から次の操作をする

等確率でN頂点のなかから1頂点を選び出し、現在いる頂点から選んだ頂点に辺を作り、選んだ頂点に移動する(多重辺や自己ループができるかもしれない)

グラフが連結になるまでの操作回数の期待値を求めよ
$1 \le N \le 10^5$

期待値とは
「なんかしら」と「そうなる確率」の積を起こりうる状態全て足し合わせたものです。
サイコロの値の期待値だと
$1 \times \frac{1}{6} + 2 \times \frac{1}{6} + \cdots + 6 \times \frac{1}{6}\ =\ 3.5$

今回の問題は操作回数なので
$\sum_{回数 i} i \times (i回でグラフを連結にできる確率)$
を十分高速に解くことができればACです。

愚直にこれを考える

(DPだけ見に来た人は飛ばして良いです)
$N = 2$ の時
頂点1から頂点2に移動することができればグラフは連結になる

常に $\frac{1}{2}$ のガチャ

式は $ans = \sum_{i = 1}^\infty i \times \frac{1}{2} \times (\frac{1}{2})^{i - 1}$
となります。

分数の部分は実際にグラフを連結にするのに有効になった操作は最後の1回、それ以外のi - 1回は1 -> 1と無駄な辺を作ってしまったという意味ですね。

この式は高校の数学の教科書にも載っていそうな典型の式ですね。
~~(確かこれができない生徒にブチ切れている鉄緑会のプリントみたいなのがTwitterでバズっていたような)~~
$ans - \frac{1}{2} ans$ を計算することで最初のiを落とすことができます
$ans - \frac{1}{2} ans = \sum_0^\infty \frac{1}{2} \times (\frac{1}{2})^{i - 1}$

これは等比級数の総和なので公式が使えて
$\frac{1}{2} ans = lim_{i \rightarrow \infty} \frac{\frac{1}{2}(1 - (\frac{1}{2})^i)}{1 - \frac{1}{2}}$

これを整理して極限も計算すると
$ans = 2$
がでます。

Nが他の値でもこのようにうまくいくでしょうか?
$N = 3$ の時

この状態から

この状態になるのに常に $\frac{2}{3}$ ガチャ
ここからさらに最後の１個を引き当ててグラフを連結にするのに $\frac{1}{3}$ ガチャ

よって操作回数の期待値の式は
$ans = \sum_{i = 2}^\infty i \times \sum_{j = 0}^{i - 2} ((1 - \frac{2}{3})^j \times \frac{2}{3} \times (1 - \frac{1}{3})^{i - 2 - j} \times \frac{1}{3})$

んんんん無理みがふかくないか？

実際に無限じゃなくて10^3くらいで概算をプログラムに書かせたらしっかりと正しい値4.5をだしてくれました。

でも一般のNで立式して解かせるのは現実的では無いです。

Nが大きい時、2秒いっぱいいっぱい計算させても想定誤差以下の値を出してくれるとは思えません。
- そもそも操作回数iでグラフを連結にする確率を求める計算を毎回してTL間に合わない気がする
本当にゴリゴリに式変形して殴る解法もあるかもしれませんが、これはABCのD問題です。まずもっと簡単に解く方法があると睨むべきでしょう。

問題の見通しを良くする->DPに気づく

上の $N = 3$ の時の、「ガチャ」の確率の変化を見てみます。
①繋がなくてはいけない頂点が二つの時に $\frac{2}{3}$ ガチャ
②繋がなくてはいけない頂点が一つの時に $\frac{1}{3}$ ガチャ
③グラフが連結になりました！

①のガチャを成功すると②へ移動し、失敗すると①にとどまります。
②のガチャを成功すると③へ移動し、失敗すると②にとどまります。

これを一般の $N$ で考えるとどうなるでしょうか。
(集合体恐怖症の人にはちょっと嫌な画像かもしれない。ごめんなさい)

「繋がなくてはいけない頂点が残り $i$ 個」の状態の時、
操作でその $i$ 個のなかから選ぶことに成功したら「繋がなくてはいけない頂点が残り $i - 1$ 個」の状態に移動する。
失敗し、 $N - i$ 個の既に連結である頂点から選んでしまったら、「繋がなくてはいけない頂点が残り $i$ 個」の状態にとどまる。

要するに $\frac{i}{N}$ の確率で次の状態に移動、 $1 - \frac{i}{N}$ の確率で今の状態にとどまる。

なので、「繋がなくてはいけない頂点が残り $i$ 個」という状態を $i = 0, 1, 2, \cdots , N - 1, N$ の時に考えれば問題の見通しがかなり良くなります。

ある程度DP問題に慣れている人ならばこの時点で
$DP(i) = 繋がなくてはいけない頂点が残りi 個の時のグラフを連結にするまでの操作回数の期待値$
というDPの定義が見えると思います。

典型的な考察で漸化式をたてる

「初級編」の記事の例題解説にもあるテクニックを用いてこのDPの遷移を決めます。

ゴールの状態での操作回数の期待値は0

自分で勝手に作った言葉なので意味不明な響きがしますが、今回の状態だと「「繋がなくてはならない頂点が残り0個の時」からグラフを連結にするための操作回数の期待値は0」
グラフが既に連結なのに操作はしなくて良いですよね。

$DP(0) = 0$

これがDPの初期値になります。

DPの遷移は上で求めた見通しを良くした遷移をそのまま使いましょう。
$\frac{i}{N}$ の確率で次の状態に移動、 $1 - \frac{i}{N}$ の確率で今の状態にとどまる。
ですね。状態に移動するかしないかのガチャ一回で操作回数は一回増加するので

DPの遷移式は
$DP(i) = \frac{i}{N}(DP(i - 1) + 1) + (1 - \frac{i}{N})(DP(i) + 1)$
となります。