問題

$N-1$ 個の白いボールと $1$ 個の黒いボールがある。はじめ黒いボールは一番左にある。

以下の操作を $K$ 回繰り返す。

• $1$ 以上 $N$ 以下の整数を一様ランダムに2つ選び、それぞれ $a, b$ とする。$a \neq b$ のとき、左から $a$ 番目のボールと左から $b$ 番目のボールを交換する。

$K$ 回の操作後に、黒いボールがある位置を左から $x$ 番目としたとき、$x$ の期待値は？

考察ミス

• $a \neq b$ のときに、$a,b$ 選び直し（回数カウントしない）と勘違いをしてしまった。
• 黒いボールが一番左以外にあるときに、黒いボールが一番左に移動する場合を、 $(a=1, b\neq 1)$ or $(a\neq 1 , b=1)$と勘違いしてしまった
  • これだと、白ボールと白ボールの交換するケースもある。正しくは、$a= 1$, $b$ は黒のボールの場所、またはその逆である必要があった。
  • 「一番左→一番左以外」であればこれで正しかった。「一番左以外→一番左」もこれと同じであると勘違いをしてしまった。
• $K$ 回操作後、一番左に黒いボールがある確率が $\mathrm{dp}[K]$ で求まっているとき、$x \geq 2$ を1つ固定したとき、黒が $x$ 番目 にある確率を $1-\mathrm{dp}[k]$ として計算してしまった $(1-\mathrm{dp}[k])/(N-1)$ が正しい

解法

マルコフ連鎖を考えれば良い

その他

• 確率といっても場合の数から計算できるので愚直を書いてしまっても良かったかもしれない