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

325

この著者は初心者として投稿しています。間違いや考慮が足りていない点が含まれている可能性が高いです。見つけたらコメント欄で優しく指摘してあげましょう。

この記事は 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}, \dots, E_{8}, G$ からなるマルコフ過程を考える。遷移確率は以下のとおりとする。

$0 \leq i \leq 7$ に対し、 $E_{i}$ から $E_{0}$ に遷移する確率が $\frac{1}{2}$ 、 $E_{i}$ から $E_{i + 1}$ に遷移する確率が $\frac{1}{2}$
$E_{8}$ から $E_{0}$ に遷移する確率が $\frac{1}{2}$ 、 $E_{8}$ から $G$ に遷移する確率が $\frac{1}{4}$ 、 $E_{8}$ から $E$ に遷移する確率が $\frac{1}{8}$
$G$ から $G$ に遷移する確率が $1$

このとき、 $E_{0}$ から $n$ 回の遷移で $G$ に到達する確率を $q_{n}$ とする。また、初めて $G$ に到達したときの遷移回数を確率変数 $X$ とし、その期待値を $E$ で表す。

$E$ が有限であることを示せ。
$q_{n}$ の漸化式を求めよ。
$E$ を求めよ。

おことわり

(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} < {(1 - \frac{1}{2^{9}})}^{2}$ である。
同様にして、任意の自然数 $n \geq 1$ に対し $r_{9 n} < {(1 - \frac{1}{2^{9}})}^{n}$ が成り立つ。
$r_{n}$ はその定義から明らかに単調減少であるから、 $r_{n} < {(1 - \frac{1}{2^{9}})}^{n / 9 - 1}$ が従う。
任意の自然数 $n \geq 1$ に対し $r_{n} > 0, p_{n} > 0$ であるから、 $p_{n + 1} - p_{n} = r_{n}$ の関係より $p_{n} < {(1 - \frac{1}{2^{9}})}^{n / 9 - 1}$ が成り立つ。
$A = {(1 - \frac{1}{2^{9}})}^{- 1}, B = {(1 - \frac{1}{2^{9}})}^{1 / 9}$ とすると、 $0 < p_{n} < A \cdot B^{n}$ である。よって、
$\sum_{k = 0}^{\infty} k \cdot A \cdot B^{k}$
が収束することを示せばよいが、これは $0 < B < 1$ から即座に従う。

(2)

$E_{0}$ から $n$ 回の遷移で $E_{i} (0 \leq i \leq 8)$ に到達する確率を $p_{n, i}$ とする。

このとき、

$\begin{aligned} (1) & p_{n, 0} & = \frac{1}{2} (1 - q_{n - 1}) \\ (2) & p_{n, i} & = \frac{1}{2} p_{n - 1, i - 1} (1 \leq n, 1 \leq i \leq 7) \\ (3) & p_{n, 8} & = \frac{1}{2} p_{n - 1, 7} + \frac{1}{4} p_{n - 1, 8} (1 \leq n) \\ (4) & p_{n} & = \frac{1}{4} p_{n - 1, 8} (1 \leq n) \end{aligned}$

が成り立つ。十分に大きい $n$ に対して、(4)を変形する。

$\begin{aligned} 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} \\ = & \dots \\ = & \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{aligned}$

$p_{n} = q_{n} - q_{n - 1}$ であるから、

$q_{n} - q_{n - 1} = \frac{1}{2^{11}} (1 - q_{n - 10}) + \frac{1}{2^{2}} (q_{n - 1} - q_{n - 2})$

これを移項して

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

を得る。

(3)

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

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

$E_{0} \to E_{0}$ : 確率 $\frac{1}{2^{1}}$ 、 $G$ までの遷移回数は $1$ 回遷移後に $E_{0}$ に戻ったのでトータル $E + 1$ 回
$E_{0} \to E_{1} \to E_{0}$ : 確率 $\frac{1}{2^{2}}$ 、 $G$ までの遷移回数は $E + 2$ 回
$\dots$
$E_{0} \to E_{1} \to E_{8} \to E_{0}$ : 確率 $\frac{1}{2^{9}}$ 、 $G$ までの遷移回数は $E + 9$ 回
$E_{0} \to E_{1} \to E_{8} \to G$ : 確率 $\frac{1}{2^{10}}$ 、 $G$ までの遷移回数は $9$ 回
$E_{0} \to E_{1} \to E_{8} \to E_{8} \to E_{0}$ : 確率 $\frac{1}{2^{11}}$ 、 $G$ までの遷移回数は $E + 10$ 回
$E_{0} \to E_{1} \to E_{8} \to E_{8} \to G$ : 確率 $\frac{1}{2^{12}}$ 、 $G$ までの遷移回数は $10$ 回
$\dots$

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

$E = \sum_{k = 1}^{9} \frac{E + k}{2^{k}} + \sum_{k = 1}^{\infty} \frac{E + 9 + k}{2^{9 + 2 k}} + \sum_{k = 0}^{\infty} \frac{9 + k}{2^{10 + 2 k}}$

これを解くと、

$\begin{aligned} E & = \sum_{k = 1}^{9} \frac{E + k}{2^{k}} + \sum_{k = 1}^{\infty} \frac{E + 9 + k}{2^{9 + 2 k}} + \sum_{k = 0}^{\infty} \frac{9 + k}{2^{10 + 2 k}} \\ E & = \frac{511 E + 1013}{2^{9}} + \frac{3 E + 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{aligned}$