この記事は Mathlog Advent Calendar 2023 (高校数学部門) 12月23日の記事です。
私メリーさん。今0番出口にいるの
私メリーさん。今1番出口にいるの
私メリーさん。今2番出口にいるの
私メリーさん。今0番出口にいるの
私メリーさん。今0番出口にいるの
私メリーさん。今1番出口にいるの
私メリーさん。今2番出口にいるの
私メリーさん。今3番出口にいるの
私メリーさん。今0番
https://twitter.com/MRKM_kreuzungen/status/1731649129351365118
メリーさんは8番出口のルールを知らないのでランダムに「進む」または「引き返す」を選択するものとする。進めない異常の場合も1/2の確率で正解(引き返す)を選択し、残り半分の確率でゲームオーバーになる(0番出口に戻される)行動をとるものとする。
メリーさんは8番出口から脱出することができるだろうか?
$ 10 $個の状態$ E_0, E_1, \cdots, E_8, G $からなるマルコフ過程を考える。遷移確率は以下のとおりとする。
このとき、$ E_0 $から$ n $回の遷移で$ G $に到達する確率を$ q_n $とする。また、初めて$ G $に到達したときの遷移回数を確率変数$ X $とし、その期待値を$ E $で表す。
(3)については一応値は出ましたが、厳密な解法になっているかはわかりません。もし議論に問題点があればコメント欄でご指摘ください。
$ E_0 $から$ n $回の遷移で初めて$ G $に到達する確率を$ p_n $とする。
わかりやすさのため、元ネタの用語を用いる。
$ r_n = 1 - q_n $とする。
「メリーさんが1回も間違えずに8番出口から脱出する」シナリオを考えた場合、これは$ 9 $回遷移後に発生し、その確率は$ 1 - \frac{1}{2^9} $である。
$ 9 $回遷移後に脱出しない場合、さらに$ 9 $回後に脱出できる確率は$ 1 - \frac{1}{2^9} $以上であり、したがって$ r_{9 \cdot 2} < \left(1 - \frac{1}{2^9}\right)^2 $である。
同様にして、任意の自然数$ n \geq 1 $に対し$ r_{9n} < \left(1 - \frac{1}{2^9}\right)^n $が成り立つ。
$ r_n $はその定義から明らかに単調減少であるから、$ r_{n} < \left(1 - \frac{1}{2^9}\right)^{n/9-1} $が従う。
任意の自然数$ n \geq 1 $に対し$ r_n > 0, p_n > 0 $であるから、$ p_{n+1} - p_n = r_n $の関係より$ p_n < \left(1 - \frac{1}{2^9}\right)^{n/9-1} $が成り立つ。
$ A = \left(1 - \frac{1}{2^9}\right)^{-1}, B = \left(1 - \frac{1}{2^9}\right)^{1/9} $とすると、$ 0 < p_n < A \cdot B^n $である。よって、
\begin{equation}
\sum_{k=0}^{\infty} k \cdot A \cdot B^k
\end{equation}
が収束することを示せばよいが、これは$ 0 < B < 1 $から即座に従う。
$ E_0 $から$ n $回の遷移で$ E_i (0 \leq i \leq 8) $に到達する確率を$ p_{n, i} $とする。
このとき、
\begin{align} p_{n, 0} &= \frac{1}{2}(1 - q_{n-1}) \tag{1} \\ p_{n, i} &= \frac{1}{2} p_{n-1, i-1} (1 \leq n, 1 \leq i \leq 7) \tag{2} \\ p_{n, 8} &= \frac{1}{2} p_{n-1, 7} + \frac{1}{4} p_{n-1, 8} (1 \leq n) \tag{3} \\ p_n &= \frac{1}{4} p_{n-1, 8} (1 \leq n) \tag{4} \end{align}
が成り立つ。十分に大きい$ n $に対して、(4)を変形する。
\begin{align} & p_n \\ =& \frac{1}{2^2} p_{n-1, 8} \\ =& \frac{1}{2^3} p_{n-2, 7} + \frac{1}{2^4} p_{n-2, 8} \\ =& \frac{1}{2^4} p_{n-3, 6} + \frac{1}{2^4} p_{n-2, 8} \\ =& \cdots \\ =& \frac{1}{2^{10}} p_{n-9, 0} + \frac{1}{2^4} p_{n-2, 8} \\ =& \frac{1}{2^{11}}(1 - q_{n-10}) + \frac{1}{2^4} p_{n-2, 8} \\ =& \frac{1}{2^{11}}(1 - q_{n-10}) + \frac{1}{2^2} p_{n-1} \\ \end{align}
$ p_n = q_n - q_{n-1} $であるから、
\begin{equation} q_n - q_{n-1} = \frac{1}{2^{11}}(1 - q_{n-10}) + \frac{1}{2^2} (q_{n-1} - q_{n-2}) \end{equation}
これを移項して
\begin{equation} q_n - \frac{5}{4} q_{n-1} + \frac{1}{4} q_{n-2} + \frac{1}{2^{11}} q_{n-10} = \frac{1}{2^{11}} \end{equation}
を得る。
(1)より$ E $は有限であるため、「$ E_0 $から次に$ E_0 $または$ G $に行くまでのシナリオ」を考え、それをもとに$ E $に関する方程式を立てて解く。
このとき、次のシナリオが考えられる:
したがって、次の方程式が成り立つ:
\begin{equation} E = \sum_{k=1}^9 \frac{E+k}{2^k} + \sum_{k=1}^{\infty} \frac{E+9+k}{2^{9+2k}} + \sum_{k=0}^{\infty} \frac{9+k}{2^{10+2k}} \end{equation}
これを解くと、
\begin{align} E &= \sum_{k=1}^9 \frac{E+k}{2^k} + \sum_{k=1}^{\infty} \frac{E+9+k}{2^{9+2k}} + \sum_{k=0}^{\infty} \frac{9+k}{2^{10+2k}} \\ E &= \frac{511E + 1013}{2^9} + \frac{3E + 31}{2^9 \cdot 9} + \frac{7}{2^6 \cdot 9} \\ E &= \frac{767}{768} E + \frac{767}{384} \\ \frac{1}{768} E &= \frac{767}{384} \\ E &= 1534 \end{align}
となり、$ E = 1534 (= 2^9 \cdot 3 - 2) $が得られる。
それっぽい数字が出てきたので正解のような気がするのですが、この議論が本当に正しいのかはわかりません。
8番出口から始めて0番出口に戻されずに脱出できる確率は2進法で0.010101...と表され、これは1/3に等しいので、因数に3を持つことも不自然ではないと思います。
議論の間違いがある場合はコメント欄でご指摘ください。