メリーさんは8番出口から脱出することができる

この記事は 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番出口から脱出することができるだろうか?

問題の定式化

おことわり

(3)については一応値は出ましたが、厳密な解法になっているかはわかりません。もし議論に問題点があればコメント欄でご指摘ください。

解法

$ E_0 $から$ n $回の遷移で初めて$ G $に到達する確率を$ p_n $とする。

(1)

わかりやすさのため、元ネタの用語を用いる。

$ 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 $から即座に従う。

(2)

$ 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}

を得る。

(3)

(1)より$ E $は有限であるため、「$ E_0 $から次に$ E_0 $または$ G $に行くまでのシナリオ」を考え、それをもとに$ E $に関する方程式を立てて解く。

このとき、次のシナリオが考えられる:

• $ E_0 \rightarrow E_0 $: 確率$ \frac{1}{2^1} $、$ G $までの遷移回数は$ 1 $回遷移後に$ E_0 $に戻ったのでトータル$ E + 1 $回
• $ E_0 \rightarrow E_1 \rightarrow E_0 $: 確率$ \frac{1}{2^2} $、$ G $までの遷移回数は$ E + 2 $回
• $ \cdots $
• $ E_0 \rightarrow E_1 \rightarrow E_8 \rightarrow E_0 $: 確率$ \frac{1}{2^9} $、$ G $までの遷移回数は$ E + 9 $回
• $ E_0 \rightarrow E_1 \rightarrow E_8 \rightarrow G $: 確率$ \frac{1}{2^{10}} $、$ G $までの遷移回数は$ 9 $回
• $ E_0 \rightarrow E_1 \rightarrow E_8 \rightarrow E_8 \rightarrow E_0 $: 確率$ \frac{1}{2^{11}} $、$ G $までの遷移回数は$ E + 10 $回
• $ E_0 \rightarrow E_1 \rightarrow E_8 \rightarrow E_8 \rightarrow G $: 確率$ \frac{1}{2^{12}} $、$ G $までの遷移回数は$ 10 $回
• $ \cdots $

したがって、次の方程式が成り立つ:

\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を持つことも不自然ではないと思います。

議論の間違いがある場合はコメント欄でご指摘ください。