ゲーム1/8192をクリアするのに必要な試行回数を求める～導出編～

　本記事は、下記記事の導出編である。

https://note.com/terapotan/n/nfc689607e15c

　問題を数学の言葉で厳密に書き下す。

$1 \leq x < N$のとき$f_X(x)$,$F_X(x)$の値は、それぞれ$f_X(x)=0,F_X(x)=0$である。$x=N$のとき$f_X(x)$,$F_X(x)$の値は、それぞれ$f_X(x)=p^N,F_X(x)=p^N$である。したがって、以降では$x > N$のときのみ考えることにする。

結果

　$p^N\rightarrow 0$のとき、確率変数$X$は平均$E_N$の指数分布に従う。よって確率密度関数$f_X(x)$・累積分布関数$F_X(x)$に関して、次の等式が成り立つ。
$$ \begin{align*} \lim_{p^N \rightarrow 0} f_X(x)&=\frac{1}{E_N}\exp(-\frac{1}{E_N} x)\\ \lim_{p^N \rightarrow 0}F_X(x)&=1-\exp(-\frac{1}{E_N}x) \end{align*} $$
　ただし、ここで$E_N$は次の式で求められる。
$$ E_N[X] = {{\frac{1-p^N}{(1-p)p^N}}} $$
　特に$p=1/2$のとき
$$ E_N[X] = 2^{N+1} - 2 $$

$x$回以下で$N$回連続成功する確率が$\alpha$であるとき、$x$は次の式で求められる。
$$ x=-E_N\ln(1-\alpha) $$

　上式は累積分布関数の式から、次のように求められる。
$$ \begin{align*} \alpha&=1-\exp(-\frac{1}{E_N}x)\\ -\exp(-\frac{1}{E_N}x)&=\alpha -1 \\ \exp(-\frac{1}{E_N}x)&=1 - \alpha  \\ \ln(1-\alpha)&=-\frac{1}{E_N}x\\ x&=-E_N\ln(1-\alpha) \end{align*} $$

導出過程の概略

1. 確率母関数を求める。
2. 期待値を求める。
3. 確率母関数から特性関数を求め、$p^N \rightarrow 0$のときその特性関数が、指数分布の特性関数に一致することを示す。特性関数と累積分布関数、特性関数と確率密度関数にはそれぞれ一対一対応があることが知られている。特性関数が一致するのであれば、累積分布関数や確率密度関数も一致すると言ってよいのである（※1）。

確率母関数の導出

$P(X=x)$ を $x$ 回で 初めて$N$ 回連続成功する確率、$P(T=k)$ を $k$ 回目に初めて失敗する確率（$k-1$ 回連続成功した後 $k$ 回目に失敗する確率）とする。$q = 1-p$ とする。

$P(T=k)$ は、その定義より、
$$ \begin{equation} P(T=k) = p^{k-1} q \quad \tag{1} \end{equation} $$
である。$P(X=x)$ は次式で表せる。

$$ P(X=x) = \sum_{k=1}^{N} P(X=x | T=k) P(T=k) \tag{2} $$

　式(2)はなぜ成り立つのだろうか。

　$x > N$のとき、最初の$N$回の内に少なくとも一回失敗している必要がある。なぜならもし最初の$N$回がすべて成功していたならば、その時点で試行は終了し、$x=N$となってしまうからである。これは$x > N$の仮定と矛盾する。
　前述の議論から「最初の$N$回で少なくとも一回失敗する」事象を$B$とすると
$$ \{X=x\} \subseteq B \tag{2A} $$
　が成り立つ。

　これらの事象の和は、事象$B$に一致する。「$k$回目の試行で初めて失敗が起こる事象」を$\{T=k\}$とすると
$$ B = \bigcup_{k=1}^{N}\{T=k\} $$
ここで、$\{T=1\},\{T=2\},\cdots,\{T=N\},$は互いに排反である。また$0 < p < 1$より、$P(\{T=k\}) > 0$が成り立つ。したがって全確率亜種公式が適用できるから、式(2)が成り立つ。

　本題に戻って、$P(X=x | T=k)$ の値を考える。これは$k$ 回目で失敗した後で、$x$ 回目に $N$ 回連続成功が起こる確率である。
　ベルヌーイ試行であるから$i$回目の試行の結果は、$i-1$回目以前の試行の結果に左右されない。よって$k$回目に失敗してから$x$回目で$N$回連続成功させる確率を考えるときには、以前の試行の結果、すなわち$k$回目に失敗したという情報を一切無視して考えてよいのである。
　以上を踏まえると、既に$k$回試行を行ってしまっているから、$x-k$回で$N$回連続成功させれば、$x$回目に連続成功する。$x-k$回で$N$回連続成功する確率とは$P(X=x-k)$に他ならない。したがって
$$ \begin{equation} P(X=x | T=k) = P(X=x-k) \quad \tag{3} \end{equation} $$
である。式(1)と式(3)を式(2)に代入して計算を進める。
$$ \begin{align*} P(X=x) &= \sum_{k=1}^{N} P(X=x-k) p^{k-1} q \\ &= q [ P(X=x-1) + p \cdot P(X=x-2) + p^2 \cdot P(X=x-3) + \cdots + p^{N-1} \cdot P(X=x-N) ] \end{align*} $$
$x > N$のときを考えているから、シグマの添え字は $x=N+1$ から始める必要がある。なお、$z \in \mathbb{R}$ かつ $|z| \leq 1$ とする。
$$ \begin{align*} \sum_{x=N+1}^{\infty} P(X=x) \cdot z^x &= q \sum_{x=N+1}^{\infty} \{ P(X=x-1) + p \cdot P(X=x-2) + \dots + p^{N-1} \cdot P(X=x-N) \} \cdot z^x \\ \end{align*} $$
$z^x = z \cdot z^{x-1}$ より、
$$ \begin{align*} &= qz \sum_{x=N+1}^{\infty} [ P(X=x-1) \cdot z^{x-1} + p \cdot P(X=x-2) \cdot z^{x-1} + \dots + p^{N-1} \cdot P(X=x-N) \cdot z^{x-1} ] \\ &= \sum_{x=N+1}^{\infty} qz [ P(X=x-1) \cdot z^{x-1} + pz P(X=x-2) \cdot z^{x-2} + \dots + (pz)^{N-1} \cdot P(X=x-N) \cdot z^{x-N} ] \end{align*} $$
また、上式は 確率母関数$G(z)$ を用いて次のようにも書ける。
$$ \begin{equation*} \sum_{x=N+1}^{\infty} P(X=x) \cdot z^x = \sum_{x=1}^{\infty} P(X=x) \cdot z^x - \sum_{x=1}^{N} P(X=x) z^x \end{equation*} $$
右辺第一項は、$G(z)$ そのものである。右辺第二項は、$P(X=x)$ が
$$ \begin{equation*} P(X=x) = \begin{cases} p^x & (x=N) \\ 0 & (0 \leq x < N) \end{cases} \end{equation*} $$
であるから、上式の値は
$$ \begin{equation*} = G(z) - (pz)^N \end{equation*} $$
となる。以上の議論より、
$$ \begin{align*} G(z) - (pz)^N &= \sum_{x=N+1}^{\infty} qz [ P(X=x-1) \cdot z^{x-1} + pz P(X=x-2) \cdot z^{x-2} + \cdots + (pz)^{N-1} \cdot P(X=x-N) \cdot z^{x-N} ] \\ &= qz \left[ \sum_{x=N+1}^{\infty} P(X=x-1) \cdot z^{x-1} + pz \sum_{x=N+1}^{\infty} P(X=x-2) \cdot z^{x-2} + \cdots + (pz)^{N-1} \sum_{x=N+1}^{\infty} P(X=x-N) \cdot z^{x-N} \right] \end{align*} $$
右辺第 $j$ 項（$j$ は $1 \le j \le N$ 以下の整数）において、$s = x-j$ とおくと、$x = s+j$。
$x=N+1$より$s+j = N+1$。よって、$s = N+1-j$。また、$x \to \infty$ のとき、$s \to \infty$。よって、右辺第 $j$ 項は、
$$ \begin{equation*} \sum_{s=N+1-j}^{\infty} P(X=s) z^s = \sum_{s=1}^{\infty} P(X=s) z^s - \sum_{s=1}^{N-j} P(X=s) z^s \end{equation*} $$
$P(X=s)$ は、$0 \le s \le N-j$ のとき $0$ である。また、右辺第一項は $G(z)$ そのものである。よって、
$$ \begin{equation*} = G(z) \end{equation*} $$
したがって、
$$ \begin{align*} G(z) - (pz)^N &= qz [ G(z) + pz G(z) + (pz)^2 G(z) + \cdots + (pz)^{N-1} G(z) ] \\ &= qz G(z) [ 1 + pz + (pz)^2 + \cdots + (pz)^{N-1} ] \end{align*} $$
$1 + pz + (pz)^2 + \cdots + (pz)^{N-1}$ は、初項 $1$、公比 $pz$、項数 $N$ の等比級数である。
$$ \begin{align*} G(z) - (pz)^N &= qz G(z) \frac{1 - (pz)^N}{1 - pz} \\ G(z) &= qz G(z) \frac{1 - (pz)^N}{1 - pz} + (pz)^N \\ G(z) - qz G(z) \frac{1 - (pz)^N}{1 - pz} &= (pz)^N \\ G(z) \left( 1 - \frac{qz \{ 1 - (pz)^N \}}{1 - pz} \right) &= (pz)^N \quad \tag{4} \end{align*} $$
$1 - [ qz \{ 1 - (pz)^N \} ] / (1 - pz)$ を整理する。
$$ \begin{align*} 1 - \frac{qz \{ 1 - (pz)^N \}}{1 - pz} &= \frac{1 - pz - qz \{ 1 - (pz)^N \}}{1 - pz} \\ &= \frac{1 - pz - qz + q p^N z^{N+1}}{1 - pz} \\ &= \frac{1 - z(p + q) + q p^N z^{N+1}}{1 - pz} \end{align*} $$
$p + q = p + (1-p) = 1$ より、
$$ \begin{equation} = \frac{1 - z + q p^N z^{N+1}}{1 - pz} \quad \tag{5} \end{equation} $$
式(4)式に式(5)式を代入すると
$$ \begin{align*} G(z) \left( \frac{1 - z + q p^N z^{N+1}}{1 - pz} \right) &= (pz)^N \\ G(z) &= \frac{(pz)^N (1 - pz)}{1 - z + q p^N z^{N+1}} \end{align*} $$

期待値の導出

$E_N[X]$の値を求める前に、$E_N[X] < \infty$を証明する。試行を$N$回ずつのブロックに分けることを考える。すなわち第1ブロックは試行1回目から$N$回目を指し、第2ブロックは試行$N+1$回目から$2N$回目を指し、第$\beta$ブロックは試行$(\beta - 1)N+1$から$\beta N$回目を指している。
　各ブロックにおいて、各ブロックに属する試行がすべて成功する確率は$p^N$である。またベルヌーイ試行の仮定から、各ブロック同士の試行は独立である。以降第$\beta$ブロックが成功したとは、第$\beta$ブロックに属する試行がすべて成功した事象を指すものとする。
　ここで初めて第$Z$ブロックが成功したと仮定する（ブロック単位で初めて成功したのが第$Z$ブロックなだけであって、$N$回連続成功自体は既に達成している可能性があることに注意せよ。例えば第2ブロックと第3ブロックをまたぐ形で$N$回連続成功している可能性がある）。すると$X$は$NZ$よりも大きな値になることはない（既に$NZ$回目で$N$回連続達成してしまっているため）から、次の不等式が成り立つ。
$$ X \le NZ $$
したがって$E_N[X]$は
$$ E_N[X]\le E_N[NZ] = NE_N[Z] $$
となる。確率変数$Z$はパラメーター$p^N$の幾何分布に従う。よって
$$ E_N[X]\le E_N[NZ] = NE_N[Z] = \frac{N}{p^N} $$
今$0 < p < 1$だから、$N/p^N$は有限の値となる。以上の議論より$E_N[X] < \infty$が示された。

　本題に戻って期待値を求める。$N-1$ 回連続成功するまでにかかった回数を $Y$、$N-1$ 回連続成功してから $N$ 回連続成功するまでにかかった回数を $Z$ とする。定義から
$$ \begin{equation*} X = Y + Z \end{equation*} $$
が成り立つ。$E_N[X]$ は、期待値の線形性から、
$$ \begin{equation*} E_N[X] = E_N[Y+Z] = E_N[Y] + E_N[Z] \quad \tag{6} \end{equation*} $$
である。ここで、$N-1$ 回連続成功した次の試行が成功した事象を $B_s$、失敗した事象を $B_F$ とする。$0 < p < 1$ より、$P(B_s) > 0, P(B_F) > 0$ であり、定義から明らかに $\bigcup_{k=1}^{\infty}\{Z=k\}=B_s\cup B_F,B_s \cap B_F = \phi$ であるから全期待値亜種公式が適用できる。条件付き期待値の存在については、後に、その具体的な値を求めることによって示す。
$$ \begin{equation*} E_N[Z] = E_N[Z|B_s]P(B_s) + E_N[Z|B_F]P(B_F) \quad \tag{7} \end{equation*} $$
式(6)に代入すると、
$$ \begin{equation*} E_N[X] = E_N[Y] + E_N[Z|B_s]P(B_s) + E_N[Z|B_F]P(B_F) \end{equation*} $$
ここで $E_N[Y]$ は定義から $E_{N-1}[X]$ に他ならない。
$$ \begin{equation*} E_N[X] = E_{N-1}[X] + E_N[Z|B_s]P(B_s) + E_N[Z|B_F]P(B_F) \end{equation*} $$
以下、条件付き期待値の値を求める。条件付き期待値の定義から、
$$ \begin{equation*} E_N[Z|B_s] = \sum_{k=1}^{\infty} k P(\{Z=k\}|B_s) \end{equation*} $$
ここで、$P(\{Z=k\}|B_s)$ は、
$$ \begin{equation*} P(\{Z=k\}|B_s) = \begin{cases} 1 & (k=1) \\ 0 & (k \neq 1) \end{cases} \end{equation*} $$
であるから、
$$ \begin{align} E_N[Z|B_s] &= 1 \cdot P(\{Z=1\}|B_s) + 2 \cdot P(\{Z=2\}|B_s) + 3 \cdot P(\{Z=3\}|B_s) + \cdots \nonumber \\ &= 1 \cdot 1 + 2 \cdot 0 + 3 \cdot 0 + \cdots \nonumber \\ &= 1 \quad \tag{8} \end{align} $$
となる。続いて $E_N[Z|B_F]$ を求める。
$$ \begin{equation*} E_N[Z|B_F] = \sum_{k=1}^{\infty} k P(\{Z=k\}|B_F) \quad \tag{9} \end{equation*} $$
ここで、$P(\{Z=k\}|B_F)$ は、
$$ \begin{equation*} P(\{Z=k\}|B_F) = \begin{cases} 0 & (1 \le k \le N-1) \\ P(Z = k-1) & (k \ge N) \end{cases} \quad \tag{10} \end{equation*} $$
である。$1 \le k \le N-1$ のとき 0 なのは、$N-1$回以下の試行回数では$N$回連続成功しようがないからである。$k\ge N$のとき$P(\{Z=k\})$ではなく$P(\{Z=k-1\})$なのは$N$回目に失敗した分を差し引いているためである。

式(9)に式(10)を代入する。
$$ \begin{align*} \sum_{k=1}^{\infty} k P(\{Z=k\}|B_F) &= \sum_{k=1}^{N-1} k P(\{Z=k\}|B_F) + \sum_{k=N}^{\infty} k P(\{Z=k\}|B_F) \\ &= \sum_{k=1}^{N-1} k \cdot 0 + \sum_{k=N}^{\infty} k P(\{Z=k\}|B_F) \\ &= \sum_{k=N}^{\infty} k P(\{Z=k\}|B_F) \\ &= \sum_{k = N}^{\infty} k P(\{ Z=k-1 \} ) \\ &= \sum_{k=N-1}^{\infty} (k+1) P(\{Z=k\}) \\ &= \sum_{k=N-1}^{N-1} (k+1) P(\{Z=k\}) + \sum_{k=N}^{\infty} (k+1) P(\{Z=k\}) \\ &= \sum_{k=N}^{\infty} (k+1) P(\{Z=k\}) \\ &= 0 + \sum_{k=N}^{\infty} (k+1) P(\{Z=k\}) \\ &= \sum_{k=1}^{N-1} (k+1) P(\{Z=k\}) + \sum_{k=N}^{\infty} (k+1) P(\{Z=k\}) \\ &= \sum_{k=1}^{\infty} (k+1) P(\{Z=k\}) \\ &= \sum_{k=1}^{\infty} k P(\{Z=k\}) + \sum_{k=1}^{\infty} P(\{Z=k\}) \end{align*} $$

右辺第一項はベルヌーイ試行であるから$i$回目の試行結果は、$i-1$回目以前の試行結果に左右されない。これは上式の$Z$を$X$と置き換えて良いことを示している。
$$ \begin{align*} \sum_{k=1}^{\infty} k P(\{Z=k\}) + \sum_{k=1}^{\infty} P(\{Z=k\}) &= \sum_{k=1}^{\infty} k P(\{X=k\}) + \sum_{k=1}^{\infty} P(\{X=k\}) \end{align*} $$

右辺第一項は $E_N[X]$ に他ならない。右辺第二項は確率の公理から 1 となる。よって
$$ \begin{equation*} E_N[Z|B_F] = E_N[X] + 1 \quad \tag{11} \end{equation*} $$
となる。$E_N[X] < \infty$であるから、$1 + E_N[X]$も有限の値となる。また
$$ \begin{equation*} P(B_s) = p, \quad P(B_F) = 1-p \quad \tag{12} \end{equation*} $$
であるから、式(8)、式(11)、式(12)を式(7)に代入すると、
$$ \begin{equation*} E_N[Z] = p \cdot 1 + (1-p)(E_N[X] + 1) \end{equation*} $$
したがって、$E_N[X]$ は
$$ E_N[X] = E_{N-1}[X] + p + (1-p)(1 + E_N[X]) $$
となる。

上式を整理する。
$$ \begin{aligned} E_N[x] &= E_{N-1}[x] + p + (1-p)(1 + E_N[x]) \\ &= E_{N-1}[x] + p + 1 - p + (1-p)E_N[x] \\ &= E_{N-1}[x] + 1 + (1-p)E_N[x]\\ E_N[x] - (1-p)E_N[x] &= E_{N-1}[x] + 1 \\ E_N[x] - E_N[x] + p E_N[x] &= E_{N-1}[x] + 1 \\ p E_N[x] &= E_{N-1}[x] + 1 \\ E_N[x] &= \frac{1}{p} E_{N-1}[x] + \frac{1}{p} \\ E_{N+1}[x] &= \frac{1}{p} E_N[x] + \frac{1}{p} \\ \end{aligned} $$

上式漸化式の一般項を求めるには、下式の特性方程式を解けばよい。
$$\alpha = \frac{1}{p} \alpha + \frac{1}{p}$$

上式を $\alpha$ について解くと
$$ \begin{aligned} \alpha &= \frac{1}{p} \alpha + \frac{1}{p} \\ \alpha - \frac{1}{p} \alpha &= \frac{1}{p} \\ \left(1 - \frac{1}{p}\right) \alpha &= \frac{1}{p} \\ \frac{p-1}{p} \alpha &= \frac{1}{p} \\ \alpha &= \frac{1}{p} \times \frac{p}{p-1} = \frac{1}{p-1} = -\frac{1}{1-p} \end{aligned} $$

であるから
$$E_{N+1}[x] + \frac{1}{1-p} = \frac{1}{p} \left( E_N[x] + \frac{1}{1-p} \right)$$

上式より、$b_N = E_N[x] + 1/(1-p)$ とすれば
$$b_{N+1} = \frac{1}{p} b_N$$

と変形出来て、これは初項 $b_0$、公比 $1/p$ の等比数列の漸化式を表している。よって $b_N$ は、$E_0[X] = 0$ より
$$b_N = \frac{1}{1-p} \times \left( \frac{1}{p} \right)^N$$

この式に$b_N = E_N[x] + 1/(1-p)$を代入すると
$$ \begin{aligned} E_N[x] + \frac{1}{1-p} &= \frac{1}{1-p} \times \left( \frac{1}{p} \right)^N \\ E_N[x] &= \frac{1}{1-p} \times \left( \frac{1}{p} \right)^N - \frac{1}{1-p} = {{\frac{1-p^N}{(1-p)p^N}}} \end{aligned} $$

以上より、$E_N[x] = {1-p^N}/\{{(1-p)p^N}\}$ である。特に$p = 1/2$ のとき
$$ \begin{aligned} E_N[x] &= \frac{1 - \left(\frac{1}{2}\right)^N}{\left(1 - \frac{1}{2}\right)\left(\frac{1}{2}\right)^N} \\ &=\frac{1 - \left(\frac{1}{2}\right)^N}{\left(\frac{1}{2}\right)\left(\frac{1}{2}\right)^N} \\ &= \frac{2 - \left(\frac{1}{2}\right)^{N-1}}{\left(\frac{1}{2}\right)^N} \\ &= \frac{2 - \frac{1}{2^{N-1}}}{\left(\frac{1}{2^N}\right)} \\ &= 2 \cdot 2^N - \frac{1}{2^{N-1}} \cdot 2^N \\ &= 2^{N+1} - 2 \end{aligned} $$
である。

特性関数の近似

$Y = {X}/{E_N}$ という確率変数を考える。
特性関数 $\phi_Y(\theta)$ は、
$$ \begin{align*} \phi_Y(\theta) &= E[e^{i\theta Y}] \\ &= E[e^{i\theta \cdot \frac{X}{E_N}}] \\ &= E[e^{i \frac{\theta}{E_N} X}] \end{align*} $$
ここで、$\phi_X(t) = E[e^{itX}]$ と比較すると、$\phi_X(t)$ を $\phi_Y(\theta)$ とするためには、$t = {\theta}/{E_N}$ と置けばよいことが分かる。したがって
$$ \begin{equation*} \phi_X \left( \frac{\theta}{E_N} \right) = \phi_Y(\theta) \end{equation*} $$
となる。$p^N \rightarrow 0$のとき$\phi_X \left( {\theta}/{E_N} \right)$ が ${1}/{(1 - i\theta)}$ になることを示す。これが示せれば、$\theta = E_N t$ より $\phi_X(t)$ は
$$ \begin{equation*} \phi_X(t) = \frac{1}{1 - i E_N t} \end{equation*} $$
であることが分かり、これは平均 $E_N$ の指数分布の特性関数である。

確率母関数 $G(z)$ は
$$ \begin{equation*} G(z) = \frac{(pz)^N (1 - pz)}{1 - z + q p^N z^{N+1}} \end{equation*} $$
であった。ここで、特性関数 $\phi_X(t)$ は、
$$ \begin{equation*} \phi_X(t) = G(e^{it}) \end{equation*} $$
であるから、
$$ \begin{equation*} \phi_X(t) = \frac{(p \exp(it))^N (1 - p \exp(it))}{1 - \exp(it) + q p^N \exp(it(N+1))} \end{equation*} $$
である。また、$\phi_X(t) = \phi_Y(\theta)$ より、
$$ \begin{equation} \phi_Y(\theta) = \frac{(p \exp( \frac{i\theta}{E_N} ))^N (1 - p \exp( \frac{i\theta}{E_N} ))}{1 - \exp( \frac{i\theta}{E_N} ) + q p^N \exp( \frac{i\theta(N+1)}{E_N} )} \quad \tag{13} \end{equation} $$
$E_N = {(1 - p^N)}/{q p^N}$ より、$p^N \rightarrow 0$のとき、$E_N \rightarrow \infty$となる。したがって$1/E_N$は微小量となる。

分母から変形を進める。$x \ll 1$ のとき、$e^{ix} \approx 1 + ix$ と近似できる（※2）。
また、$q p^N = {(1 - p^N)}/{E_N}$ でもあるから、前述の近似式と合わせて式(13)に代入する。
$$ \begin{align*} \langle \text{分母} \rangle &\approx 1 - \left( 1 + \frac{i\theta}{E_N} \right) + \frac{1 - p^N}{E_N} \left( 1 + \frac{i\theta(N+1)}{E_N} \right) \\ &= - \frac{i\theta}{E_N} + \frac{1 - p^N}{E_N} + \frac{i\theta(1 - p^N)(1 + N)}{E_N^2} \\ &= \frac{- i\theta + 1 - p^N}{E_N} + \frac{i\theta(1 - p^N)(1 + N)}{E_N^2} \end{align*} $$
右辺第2項は、右辺第1項と比べて非常に小さい(※3)。よって右辺第2項は無視できる。
$$ \begin{equation*} \langle \text{分母} \rangle \approx \frac{- i\theta + 1 - p^N}{E_N} \end{equation*} $$
となる。

分子も分母と同様の手順で計算を進める。
$$ \begin{align*} \langle \text{分子} \rangle &\approx p^N \left( 1 + i \frac{N\theta}{E_N} \right) \left\{ 1 - p \left( 1 + i \frac{\theta}{E_N} \right) \right\} \\ &= p^N \left( 1 + i \frac{N\theta}{E_N} \right) \left\{ 1 - p - \frac{i p \theta}{E_N} \right\} \\ &= p^N \left( 1 + i \frac{N\theta}{E_N} \right) \left( q - \frac{i p \theta}{E_N} \right) \\ &= p^N \left[ q - \frac{i p \theta}{E_N} + \frac{i N \theta q}{E_N} + \frac{N p \theta^2}{E_N^2} \right] \end{align*} $$
$p^N$ が十分小さいとき、定数 $q$ 以外の項は無視できる。なぜなら$q$以外の項には微小量$1/E_N$がかかっているからである。よって
$$ \begin{equation*} \langle \text{分子} \rangle \approx p^N q = \frac{1 - p^N}{E_N} \end{equation*} $$
以上の結果をふまえると、$\phi_Y(\theta)$ は
$$ \begin{align*} \phi_Y(\theta) &\approx \frac{\left( \frac{1 - p^N}{E_N} \right)}{\left( \frac{1 - i\theta - p^N}{E_N} \right)} \\ &= \frac{1 - p^N}{1 - i\theta - p^N} \end{align*} $$

$p^N \rightarrow 0$のとき
$$ \begin{equation*} \phi_Y(\theta) = \frac{1}{1 - i\theta} \end{equation*} $$
となる。本章冒頭の議論より$\phi_Y(\theta)$が上の値に収束するとき、$\phi_X(t)$は
$$ \begin{equation*} \phi_X(t) = \frac{1}{1 - i E_N t} \end{equation*} $$
に収束するから、レヴィの連続性定理（Lévy's continuity theorem）（※4）より$X$は平均$E_N$の指数分布に分布収束する。

シミュレーション値と理論値との比較

理論値

$N=13,p=1/2$の場合（ゲーム1/8192の状況）、$E_N$は
$$ E_N=2^{13+1}-2=16384-2=16382 $$
である。よって$F_X(x)$は
$$ F_X(x)=1-\exp(-\frac{1}{16382} x) $$
となる。

理論値と計算値の比較

　シミュレーションは下記のコードで実施した。10000回、13回連続成功するまでシミュレーションを実行し（10000回は試行回数ではないことに注意せよ）、値を計算した。

      import random
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt

# ===== Parameters =====
N = 13          # required number of consecutive correct choices
t = 1.0        # time per gate [seconds]
num_trials = 10000  # Monte Carlo trials
output_path = "times.csv"
# ======================================

times = []

for _ in range(num_trials):
    print(_)
    consecutive = 0
    steps = 0
    while consecutive < N:
        correct = random.choice([0, 1])
        choice = random.choice([0, 1])
        steps += 1
        if choice == correct:
            consecutive += 1
        else:
            consecutive = 0
    times.append(steps * t)

times = np.array(times)

# ---- File output ----
df = pd.DataFrame({"time_until_success_s": times})
df.to_csv(output_path, index=False)
    

　シミュレーションで求まった期待値は16225回（小数点第一位四捨五入）であった。理論値との相対誤差は-0.95%である。
　12000回までの理論値と計算値の比較を表に記す。

　理論値と計算値はほぼ一致している。12000回試行しても成功する確率は50%程度しかない。1/8192をクリアするのがいかに大変かが分かる。
　ちなみに95%の確率でクリアするには、50000回以上試行しなければならない。1秒1回であればぶっ通しでやり続けても13時間強かかる計算になる。それだけやってもまだ5%の確率で外れる可能性があるのである。

　下記リンクからシミュレーション結果が記載されたExcelファイルをダウンロードできる。

https://docs.google.com/spreadsheets/d/1bc721rqEY3KVO0VHEdSgmocD_vcRUYXx/edit?usp=sharing&ouid=107061852394405139731&rtpof=true&sd=true

導出に使う定理

全確率の公式に近い公式

全期待値の公式に近い公式

脚注

※1：証明は、例えば（鶴見,1964）のp.70に記載されている定理13.3の証明を参照のこと。
※2：$e^{ix}$のマクローリン展開を一次項で打ち切った式。
※3：一般に微小量の二乗は微小量と比べて極めて小さい値となる。例えば$\Delta x=1/100$のとき、$(\Delta x)^2$は$\Delta x$の1/100になる。
※4：レヴィの連続性定理については、（久保川,2016）のp.23に記載されている定理2.17や、（鶴見,1964）のpp.86-88に記載されている定理16.3を参照のこと。後者の文献ではレヴィの連続性定理の証明が載っている。