かなり苦手な問題で困ってしまっていました．期待値に関する問題です．
問題概要
$ 1 $ から $ N $ までの番号が付けられた $ N $ 頂点からなる有向グラフが，隣接行列の形で与えられる (自己ループや多重辺はない)．
このグラフに対して以下の操作をグラフが空になるまで繰り返す．
- 削除されていないグラフの頂点を一様ランダムに選び，有向辺を辿ってその頂点から到達可能な頂点を全て削除する．
上記の操作が行われる回数の期待値を求めよ．
制約
- $ 1 \leq N \leq 100 $
考察
まず，$ N $ の大きさから操作手順を全探索するのは不可能．また，操作回数が $ x $ 回であるような操作手順の期待値を多項式時間で求めるのは難しいように見える．そこで，数え上げの典型っぽく頂点ごとの期待値への寄与 (その頂点が手順中で選ばれる回数の期待値) を足し上げていくことを思いつく．
恐らく競プロ典型っぽいのでそのまま進んでもいいが，自分はこういうのが苦手で混乱するタチなので確率変数を導入して考えたものを書き残しておく．
- 確率変数 $ X_i = 頂点iが選ばれた回数 ( 1 \leq i \leq N ) $
と定義すると，求める値は $$ E \left[\sum _ {i=1}^{N} X_i \right] = \sum _ {i=1}^{N} E \left[X_i \right] $$ と書ける．ここで期待値の線形性に基づく変形を行っている．この式から先述した各頂点の寄与を足し上げた値が答えだと確認できる．
次に $ E \left[X_i \right] $ を求めることを考える．各手順に於いて $ 1 $ つの頂点を選ぶ回数は高々 $ 1 $ 回であるから， $ E \left[X_i \right] $ は「手順中に頂点 $ i $ が選ばれる確率」と言い換えることができる．
有向辺を辿って頂点 $ i $ に到達可能な頂点の集合を $ S(i) $ とすると，手順中に頂点 $ i $ が選ばれるためには $ S(i) $ に属する頂点の中で一番最初に頂点 $ i $ が選ばれる必要がある．条件を満たす確率は $ E \left[X_i \right] = \frac{1}{|S(i)|} $ である．これも自明に感じる人も多いだろうが，自分は混乱するので下に詳しめに書き残しておく．
任意の操作手順は正則表現っぽく「任意回の $ \overline{S(i)} $ からの頂点選択 + $ 1 $ 回の $ S(i) $ からの頂点選択 + 任意回の頂点集合 $ V $ からの頂点選択」と表わせる．この表現の「 $ 1 $ 回の $ S(i) $ からの頂点選択」の部分を「 $ 1 $ 回の頂点 $ i $ の選択」とすることによって任意の頂点 $ i $ が選ばれる操作手順を表すようになり，その数は元の $ \frac{1}{|S(i)|} $ となることが分かる．これは $ v \in \overline{S(i)} $ を選択した際 $ S(i) $ に属する頂点は削除されず，初めて頂点 $ i $ が選ばれるまで $ S(i) $ に属する頂点はどれも削除されていないため．
$ E \left[X_i \right] = \frac{1}{|S(i)|} $ が分かった．$ |S(i)| $ は逆辺を張ってDFSをして到達可能な頂点の数であるため，$ O(N^{2}) $ で求められる．$ 1 \leq i \leq N $ についてこれを求めて足し上げるので全体の計算量は $ O(N^{3}) $ になり，十分高速である．
別解
最終的な式は同じだが，もう少しわかりやすい考察手法がある．
問題を次のように言っても意味が同じである．
- $ 1, 2, \cdots, N $ をランダムに並び変えて出来る列 $ p $に対して，$p_0, p_1, \cdots, p_N $ の順に頂点を見ていき，削除されていなければ操作回数を $+1 $ してその頂点とそこから辿り着ける頂点を全て削除する．
こう言いかえることによって，条件を満たす順列の数え上げの問題になる．具体的には「$ i $ が $ S(i) $ に属する他のどの頂点よりも前に来るような順列である確率」が $ E \left[X_i \right] $ と等しくなり，先ほどより比較的簡単に $ \frac{1}{|S(i)|} $ となることが分かると思われる．
個人的なポイント
- 期待値の問題が出て問題文通り素直に考えて難しいなら，線形性を利用した変形をして様子をみる．
- そもそも基本的に数え上げと本質は同じなので主客の入れ替えは典型として頭に入れておくべき．
- 操作の言い換えによって扱いやすい形にするのも一手
- 多分自分は場合の数系の自明っぽい計算が苦手なので，徹底して分解する．
- $ i $ に到達可能な頂点数は逆辺を張って簡単なDFS木DPをする．
