平々毎々(アーカイブ)

はてなダイアリーのアーカイブです。

問題(ランダムウォーク)

神は細部に宿り給う ビルゲイツの面接試験ネタに便乗
いい問題だなあ。
以下回答。

この状態から

この状態になる確率をxと置く。
「そんな単純なことでいいの?もっと複雑な式を立てるとか……」いいんです。
さて、最初の状態から2回コインを振ったらどうなるか。
「コインは1回ずつじゃないの?」いや、2回のほうが簡単なんです。

そうすると、3段目、5段目、7段目のどこかにたどり着いているはず。4段目と6段目はありえないことに注意すること。
さて、3段目にいる人は、最初の状態から2連敗(コインが2連続で裏)の人だから、ここにいる確率は1/4。
逆に7段目にいる人(おめでとう!)は、最初の状態から2連勝した人だから、ここにいる確率も1/4。
5段目に戻ってきた人は、1勝1敗であり、確率は1/2。
「その次のステップを考えていくと数列になるんだけど……」数列にはしません。
さらに、その位置にいる人が生存する確率を考える。
7段目にいる人が生存する確率は100%、つまり1。
5段目にいる人が生存する確率は、最初に置いたとおりx。
3段目にいる人が生存する確率は
「え、そんなのわかるの?」わかるんだな。
3段目にいる人が生存する確率は、(1 - 3段目にいる人が死ぬ確率)である。
「そうなの?」感覚的には無限に階段を彷徨っている人もいそうなもんだけどね。数学上はそれはありえない。
そして3段目にいる人が死ぬ確率は、対称性より、5段目にいる人が生存する確率に等しい。
「あ!」そういうわけ。
ということで方程式が立てられる。
x = 1/4 * 1 + 1/2 * x + 1/4 * (1-x)
これを解いて、x=2/3。