問題はこちら
問題概要
頂点の有向グラフが与えられる. グラフが空になるまで以下の操作を繰り返す.- 残っている頂点のうちランダムに一つを選び, その頂点およびその頂点から辺をたどって到達できる頂点を削除する.
操作回数の期待値を求めよ.
思考の流れ
操作回数を回とする.求めるものはで, が求められれば良いが削除する頂点の候補の数が選択によって変わっていくので扱いづらく求めるのは困難なので別の方法を考える.
新たに以下の確率変数を導入する.
これを用いると,
となる. よって期待値の線形性を用いると,
したがって, 各頂点について, つまりその頂点を選ぶ確率を求めればいい.
これは, 頂点に到達可能な頂点の集合をとしたときに, のどの頂点よりも先に選ばれる必要があるのでとなり, この和が答えとなる.