$0 < p < 1$ とする。表が出る確率が $p$,裏が出る確率が $1-p$ である1枚のコインを使って次のゲームを行う。
以下の記号は原題の外で導入する。
終了判定に必要な履歴は「直前の投球が $\mathrm{T}$ か否か」の1ビットだけである。表が出るとこの1ビットは初期値に戻り,同時に得点が1増える。すなわち $\mathrm{H}$ は得点と履歴の消去を同時に担う。開始時と $\mathrm{H}$ の直後を再生時点と呼ぶ。再生時点から,次の再生時点または終了までの投球は次の3つの語のいずれかである。
| 語 | 確率 | 結果 |
|---|---|---|
| $\mathrm{H}$ | $p$ | 1点獲得して再生 |
| $\mathrm{TH}$ | $qp$ | 1点獲得して再生 |
| $\mathrm{TT}$ | $q^2$ | 得点せず終了 |
$p+qp+q^2=1$ であり,どの語も他の語の接頭辞ではない($\lbrace\mathrm{H},\mathrm{TH},\mathrm{TT}\rbrace$ は完全な接頭符号である)。この事実を事象の分解として定式化する。
$\mathcal{B}=\lbrace\mathrm{H},\mathrm{TH}\rbrace$ の元を $n$ 個連結した語の全体を $\mathcal{B}^n$ とする($\mathcal{B}^0$ は空語のみからなる)。$n=0,1,2,\ldots$ について次が成り立つ。
(i) $\mathcal{B}^n$ の相異なる2語は,一方が他方の接頭辞になることがない。
(ii) $A_n=\bigsqcup_{w\in\mathcal{B}^n}[w]$。
(iii) $E_n=\bigsqcup_{w\in\mathcal{B}^n}[w\mathrm{TT}]$ かつ $A_n=A_{n+1}\sqcup E_n$。
ここで $\bigsqcup$,$\sqcup$ は互いに排反な事象の和を表す。
(i) 相異なる $w=b_1\cdots b_n$,$w'=b'_1\cdots b'_n$($b_i,b'_i\in\mathcal{B}$)に対し,$b_i\neq b'_i$ となる最小の $i$ をとる。$b_1\cdots b_{i-1}=b'_1\cdots b'_{i-1}$ であり,$\lbrace b_i,b'_i\rbrace=\lbrace\mathrm{H},\mathrm{TH}\rbrace$ の2語は先頭の文字が異なるから,$w$ と $w'$ は同じ位置に異なる文字をもつ。したがって一方が他方の接頭辞になることはない。
(ii) $n=0$ では両辺とも全事象である。$n\geqq1$ とし,$\theta_n < \tau$ とする。語 $C_1\cdots C_{\theta_n}$ を各 $\mathrm{H}$ の直後で区切ると,$\mathrm{T}^k\mathrm{H}$($k\geqq0$)の形の $n$ 個の語に分かれる。$k\geqq2$ のものがあれば時刻 $\theta_n$ より前に $\mathrm{TT}$ が完成して $\tau < \theta_n$ となるから,$k\in\lbrace0,1\rbrace$ であり,$C_1\cdots C_{\theta_n}\in\mathcal{B}^n$ である。逆に投球列が $w\in\mathcal{B}^n$ で始まるとき,$w$ の各 $\mathrm{T}$ の直後は $\mathrm{H}$ だから $w$ は $\mathrm{TT}$ を含まず,$w$ は $\mathrm{H}$ を $n$ 個含んで $\mathrm{H}$ で終わるから $\theta_n=\lvert w\rvert < \tau$ である。排反性は (i) による。
(iii) $w\in\mathcal{B}^n$ に対し,$[w]$ は $[w\mathrm{H}]$,$[w\mathrm{TH}]$,$[w\mathrm{TT}]$ に排反に分割される。$\mathcal{B}^{n+1}=\lbrace wb : w\in\mathcal{B}^n,\ b\in\mathcal{B}\rbrace$ と (ii) より,$[w\mathrm{H}]\sqcup[w\mathrm{TH}]$ を $w$ について合併したものは $A_{n+1}$ である。$[w\mathrm{TT}]$ 上では,$w$ が $\mathrm{TT}$ を含まず $\mathrm{T}$ で終わらないから $\tau=\lvert w\rvert+2$,$N=n$ である。よって $A_n=A_{n+1}\sqcup\bigsqcup_w[w\mathrm{TT}]$ かつ $\bigsqcup_w[w\mathrm{TT}]\subset E_n$ である。逆に $E_n$ 上では,$C_\tau=\mathrm{T}$ より $\theta_n\neq\tau$ なので $\theta_n < \tau < \theta_{n+1}$ であり,$E_n\subset A_n\setminus A_{n+1}=\bigsqcup_w[w\mathrm{TT}]$ となる。
補題1
(iii) を繰り返し用いると,各 $M$ について
$$
A_0=E_0\sqcup E_1\sqcup\cdots\sqcup E_{M-1}\sqcup A_M,\qquad \sum_{n=0}^{M-1}Q_n+\mathbb{P}(A_M)=1
$$
が成り立つ。「表の直後にゲームが初めからやり直される」という再生の主張は,確率的には独立性による等式 $\mathbb{P}([wb])=\mathbb{P}([w])\,\mathbb{P}([b])$ と,この排反分解との組み合わせである。
期待値を扱う解法では,終了の確実性と投球回数の可積分性が必要になる。
$m=0,1,2,\ldots$ について $\mathbb{P}(\tau > 2m)\leqq(1-q^2)^m$ が成り立つ。特に $\mathbb{P}(\tau < \infty)=1$ かつ $\mathbb{E}[\tau]\leqq\dfrac{2}{q^2}$ である。
$\tau > 2m$ ならば,互いに重ならない $m$ 組 $(C_1,C_2),(C_3,C_4),\ldots,(C_{2m-1},C_{2m})$ のいずれも $(\mathrm{T},\mathrm{T})$ ではない。各組は独立で,$(\mathrm{T},\mathrm{T})$ でない確率は $1-q^2$ であるから第1式を得る。$\mathbb{P}(\tau=\infty)\leqq\mathbb{P}(\tau > 2m)\to0$ である。さらに $\mathbb{P}(\tau > 2m+1)\leqq\mathbb{P}(\tau > 2m)$ より
$$
\mathbb{E}[\tau]=\sum_{j=0}^{\infty}\mathbb{P}(\tau > j)\leqq2\sum_{m=0}^{\infty}\mathbb{P}(\tau > 2m)\leqq2\sum_{m=0}^{\infty}(1-q^2)^m=\frac{2}{q^2}.
$$
固定した2投ずつの組は上からの評価にのみ用いている。実際の終了は組の境界をまたぐ $\mathrm{TT}$(たとえば $\mathrm{HTT}$)でも起こるので,組ごとの判定でゲームを置き換えることはできない。
終了までに出る表の個数 $N$ と裏の個数 $X$ について
$$
\mathbb{E}[N]=p\,\mathbb{E}[\tau],\qquad \mathbb{E}[X]=q\,\mathbb{E}[\tau]
$$
が成り立ち,いずれも有限である。
$I_j=\mathbf{1}_{\lbrace C_j=\mathrm{H}\rbrace}$ とおくと,$\tau < \infty$ のもとで $N=\sum_{j\geqq1}I_j\mathbf{1}_{\lbrace\tau\geqq j\rbrace}$ である。$\lbrace\tau\geqq j\rbrace=\lbrace\tau\leqq j-1\rbrace^{c}$ は $C_1,\ldots,C_{j-1}$ で定まるので,$C_j$ と独立である。非負項の級数なので和と期待値を交換でき,
$$
\mathbb{E}[N]=\sum_{j\geqq1}\mathbb{P}(C_j=\mathrm{H})\,\mathbb{P}(\tau\geqq j)=p\sum_{j\geqq1}\mathbb{P}(\tau\geqq j)=p\,\mathbb{E}[\tau].
$$
$X$ も同様である。有限性は
補題2
による。
「表は平均して割合 $p$ で出るから」という説明は証明にならない。終了時刻 $\tau$ は投球結果に依存するからである。本質は,第 $j$ 投を行うか否かが第 $j-1$ 投までの結果で決まる($\tau$ が停止時刻である)ことにある。なお各経路で $\tau=N+X$ である。
同じ投球列を,どの単位で区切って観測するかにより,問題は異なる数学的対象に翻訳される。
| 観測の単位 | 区切り方 | 現れる構造 | 対応する解法 |
|---|---|---|---|
| 1点 | $\mathrm{H}$,$\mathrm{TH}$,$\mathrm{TT}$ | 再生,幾何分布 | 本解,3.4 節 |
| 終了列全体 | $\mathcal{B}^n\mathrm{TT}$ | 接頭符号,二項定理 | 別解1 |
| 1投 | 状態 $S_0,S_1$ と吸収状態 | 有限状態の遷移 | 別解2,参考解2 |
| 裏1個 | $\mathrm{H}^g\mathrm{T}$ | 独立な幾何分布のランダム和 | 別解3 |
| 時刻 | $\tau$,裏の個数,$\mathrm{TT}$ の出現 | 停止時刻,自己重複 | 別解4,別解5,参考解1,3,4 |
単位の選択は計算の複雑さを決める。得点で観測すると,$Q_{n}=aQ_{n-1}$ という1階の漸化式に従う。一方,時刻で観測すると,第1ブロックで分解して $\tau=1+\tau'$($\mathrm{H}$),$\tau=2+\tau'$($\mathrm{TH}$),$\tau=2$($\mathrm{TT}$)($\tau'$ は $\tau$ と同分布で第1ブロックと独立)となるから,$f_m=\mathbb{P}(\tau=m)$ は
$$
f_2=q^2,\qquad f_m=pf_{m-1}+pqf_{m-2}\quad(m\geqq3,\ f_1=0)
$$
という2階の(Fibonacci 型の)漸化式に従う。$p=\frac12$ では $f_m=F_{m-1}/2^m$($F_k$ は $F_1=F_2=1$ の Fibonacci 数)である。同じ過程でも,得点という観測量は再生時点と同期しているため低次元化する。これが本解の短さの源である。
以下は問題文と設定からの分析であり,出題者の意図に関する推定を含む。
| 着目する構造 | 導かれる解法 |
|---|---|
| $\mathrm{H}$ による履歴の消去(再生時点) | 本解,3.4 節 |
| 終了列の接頭符号分解 $\mathcal{B}^n\mathrm{TT}$ | 別解1 |
| 終了判定に必要な履歴の1ビット化 | 別解2,参考解2 |
| 裏で終わる連の独立性 | 別解3 |
| 停止時刻と Wald 型等式 | 別解4,別解5 |
| パターン $\mathrm{TT}$ の自己重複 | 参考解1,参考解3,参考解4 |
| 係数 $n+1$ の生成原理 | 本解 (3),3.1〜3.3 節 |
観測の単位を「1投」から「1点」に変える。再生時点から次の1点を獲得する確率は履歴によらず $a$ であり,その前に終了する確率は $q^2$ である( 1.2 節 )。$n$ 点目に到達する確率 $\mathbb{P}(A_n)$ を1階の漸化式で求め,$Q_n=q^2\,\mathbb{P}(A_n)$ を得る。(3) は有限部分和の差分をとってから極限をとり,(4) は (3) に $x=a$ を代入する。
$q=1-p$ とし,$n$ 点目を獲得するまでゲームが続く事象を $A_n$ とする($A_0$ は全事象)。開始時および表が出た直後は直前の投球が裏でないから,その後の終了判定はそれまでの投球によらない。この時点から次の1点を獲得するか終了するまでの投球は $\mathrm{H}$,$\mathrm{TH}$,$\mathrm{TT}$ のいずれかで,確率はそれぞれ $p$,$qp$,$q^2$ である。
$n$ 点目を獲得した時点までの投球列 $w$ は,$\mathrm{H}$ または $\mathrm{TH}$ を $n$ 個並べた語であり,相異なる2つの語の一方が他方の始まりの部分になることはない。よって $A_n$ は,そのような $w$ で投球列が始まる互いに排反な事象 $[w]$ の和である(
補題1
)。各 $[w]$ の上で,続く投球が $\mathrm{H}$ または $\mathrm{TH}$ ならば $A_{n+1}$ に属し,$\mathrm{TT}$ ならばちょうど $n$ 点で終了する。逆に $n$ 点で終了する投球列はすべて,ある $w$ について $w\mathrm{TT}$ で始まる。投球の独立性より
$$
\mathbb{P}([w\mathrm{H}])+\mathbb{P}([w\mathrm{TH}])=(p+qp)\,\mathbb{P}([w]),\qquad \mathbb{P}([w\mathrm{TT}])=q^2\,\mathbb{P}([w])
$$
であり,$w$ について和をとると,$a=p+qp=p(2-p)$ として
$$
\mathbb{P}(A_{n+1})=a\,\mathbb{P}(A_n),\qquad Q_n=q^2\,\mathbb{P}(A_n)\qquad(n=0,1,2,\ldots).
$$
$\mathbb{P}(A_0)=1$ より $\mathbb{P}(A_n)=a^n$ である。したがって (2) の答は
$$
Q_n=q^2a^n=(1-p)^2\lbrace p(2-p)\rbrace^n\qquad(n=0,1,2,\ldots).
$$
$n=1,2$ として (1) の答
$$
Q_1=p(1-p)^2(2-p),\qquad Q_2=p^2(1-p)^2(2-p)^2
$$
を得る。なお $a+q^2=1$,$0 < a < 1$ である。
$0 < x < 1$ とし,$s_m=\displaystyle\sum_{n=0}^{m}(n+1)x^n$ とおく。
$$
\begin{aligned}
(1-x)s_m&=\sum_{n=0}^{m}(n+1)x^n-\sum_{n=1}^{m+1}nx^n=\sum_{n=0}^{m}x^n-(m+1)x^{m+1}\\
&=\frac{1-x^{m+1}}{1-x}-(m+1)x^{m+1}
\end{aligned}
$$
であるから,両辺に $1-x$ を掛けて
$$
(1-x)^2s_m=1-(m+2)x^{m+1}+(m+1)x^{m+2}.
$$
$\lim_{n\to\infty}x^n=0$ と $\lim_{n\to\infty}nx^n=0$ より,$m\to\infty$ のとき
$$
(m+2)x^{m+1}=(m+1)x^{m+1}+x^{m+1}\to0,\qquad (m+1)x^{m+2}=x\cdot(m+1)x^{m+1}\to0.
$$
よって $\lim_{m\to\infty}(1-x)^2s_m=1$ であり,$(1-x)^2 > 0$ より
$$
\sum_{n=0}^{\infty}(n+1)x^n=\frac{1}{(1-x)^2}.
$$
$$ \boxed{ \begin{aligned} &Q_1=p(1-p)^2(2-p),\qquad Q_2=p^2(1-p)^2(2-p)^2,\\ &Q_n=(1-p)^2\lbrace p(2-p)\rbrace^n,\qquad \sum_{n=0}^{\infty}nQ_n=\frac{p(2-p)}{(1-p)^2} \end{aligned} } $$
解法は,最初に構成する数学的対象と証明原理によって区別する。同じ対象の記号・図式・計算順序の違いは 3.14 節 にまとめ,独立の解法として数えない。3.1〜3.3 節は (3) の別証,3.4 節は (4) の他の導出である。
$n+1$ は $i+j=n$ を満たす非負整数の組 $(i,j)$ の個数である。したがって $\sum(n+1)x^n$ は,格子点 $(i,j)$ に重み $x^{i+j}$ を与えた和を対角線 $i+j=n$ ごとにまとめたものであり,$\left(\sum x^i\right)^2$ に等しいはずである。無限和の並べ替えを避けるため,三角形領域の部分和を二つの正方形領域の和ではさむ。
$0 < x < 1$ とし,$g_k=\displaystyle\sum_{i=0}^{k}x^i=\frac{1-x^{k+1}}{1-x}$ とおく。$s_m=\displaystyle\sum_{n=0}^{m}(n+1)x^n$ は,$i,j\geqq0$,$i+j\leqq m$ を満たす組 $(i,j)$ についての $x^{i+j}$ の和に等しい。各項は正であり,
$$
\lbrace (i,j) : 0\leqq i,j\leqq\lfloor m/2\rfloor\rbrace\subset\lbrace (i,j) : i,j\geqq0,\ i+j\leqq m\rbrace\subset\lbrace (i,j) : 0\leqq i,j\leqq m\rbrace
$$
であるから
$$
g_{\lfloor m/2\rfloor}^{\,2}\leqq s_m\leqq g_m^{\,2}.
$$
$m\to\infty$ のとき両端はともに $\dfrac{1}{(1-x)^2}$ に収束するので,はさみうちの原理より
$$
\sum_{n=0}^{\infty}(n+1)x^n=\frac{1}{(1-x)^2}.
$$
$(1+x+x^2+\cdots)^2=1+2x+3x^2+\cdots$ の係数は対角線上の格子点の個数 $1,2,3,\ldots$ である。この証明は $x^k\to0$ だけを用い,問題文の付記 $\lim nx^n=0$ を必要としない。逆に,級数の収束から一般項が $0$ に収束するので,付記の事実そのものが系として従う。格子点を $r$ 次元にすれば $(1-x)^{-r}$ の係数 $\binom{n+r-1}{r-1}$ が得られる( 5.8 節 )。
$(n+1)(1-x)^2x^n$ を確率として実現する実験を作り,全確率が $1$ であることを使う。成功確率 $1-x$ の独立試行で,2回目の成功までの失敗回数を考える(負の二項分布)。全確率の確認を有限回の試行の範囲で行えば,無限回の試行を扱う必要がない。
$0 < x < 1$ とし,成功確率 $1-x$,失敗確率 $x$ の独立試行を $M$ 回($M\geqq2$)行う。$0\leqq n\leqq M-2$ について,2回目の成功が第 $n+2$ 回に起こるのは,第 $n+2$ 回が成功で,それ以前の $n+1$ 回に成功がちょうど1回ある場合であり,その確率は $(n+1)(1-x)^2x^n$ である。これらの事象と「$M$ 回中の成功が1回以下」という事象(確率 $x^M+M(1-x)x^{M-1}$)は互いに排反で全体を尽くすから
$$
(1-x)^2\sum_{n=0}^{M-2}(n+1)x^n=1-x^M-M(1-x)x^{M-1}.
$$
$M\to\infty$ のとき $x^M\to0$,$Mx^{M-1}=\frac1x\cdot Mx^M\to0$ であるから右辺は $1$ に収束する。$(1-x)^2 > 0$ で割って結論を得る。
$n=0$ は最初の2回がともに成功する確率 $(1-x)^2$ に一致する。上の有限等式で $M=m+2$ とおくと,右辺は
$$
1-x^{m+2}-(m+2)(1-x)x^{m+1}=1-(m+2)x^{m+1}+(m+1)x^{m+2}
$$
となり,本解 (3) の等式 $(1-x)^2s_m=1-(m+2)x^{m+1}+(m+1)x^{m+2}$ そのものである。すなわち本解の剰余項は「$m+2$ 回の試行で成功が1回以下である確率」という意味をもつ。ここで導入した試行は原題のコインとは無関係であり,成功確率は $1-x$ である。
$(n+1)x^n=\dfrac{d}{dx}x^{n+1}$ であるから,係数 $n+1$ は微分によって生成される。無限級数を項別微分する代わりに,有限等比和を微分してから極限をとる。
$0 < x < 1$ において
$$
\sum_{n=0}^{m}x^{n+1}=\frac{x-x^{m+2}}{1-x}.
$$
両辺は $x\neq1$ で微分可能であり,微分すると
$$
s_m=\frac{\lbrace 1-(m+2)x^{m+1}\rbrace(1-x)+(x-x^{m+2})}{(1-x)^2}=\frac{1-(m+2)x^{m+1}+(m+1)x^{m+2}}{(1-x)^2}.
$$
以下,本解 (3) と同様に $m\to\infty$ として結論を得る。
得られる有限等式は本解 (3) と同一であり,差分(本解)と微分(本法)は同じ剰余項に別の経路で到達する。べき級数は収束半径の内部で項別微分できるという定理を用いれば,$\frac{d}{dx}\frac{x}{1-x}=\frac{1}{(1-x)^2}$ から直ちに結論が出るが,これは高校数学の範囲外である。また $f(x)=(1-x)^{-2}$ について $f^{(n)}(0)/n!=n+1$ を確かめるだけでは,Taylor 級数が $f$ に収束することは示されない(剰余項の評価が別に要る)。
$\sum nQ_n$ は分布を重み $n$ で「縦に」足したものである。$n=\sum_{k=1}^{n}1$ と分解して「横に」足し直すと,到達確率 $\mathbb{P}(A_k)=a^k$ の和になる。本解ですでに $\mathbb{P}(A_k)$ が得られているので,(3) を経由せずに済む。
$M\geqq1$ とする。$\sum_{n=k}^{M}Q_n=\mathbb{P}(A_k)-\mathbb{P}(A_{M+1})=a^k-a^{M+1}$ であるから
$$
\sum_{n=1}^{M}nQ_n=\sum_{n=1}^{M}\sum_{k=1}^{n}Q_n=\sum_{k=1}^{M}\sum_{n=k}^{M}Q_n=\sum_{k=1}^{M}\left(a^k-a^{M+1}\right)=\frac{a(1-a^M)}{1-a}-Ma^{M+1}.
$$
$M\to\infty$ のとき $a^M\to0$,$Ma^{M+1}\to0$(問題文の付記)であるから
$$
\sum_{n=0}^{\infty}nQ_n=\frac{a}{1-a}=\frac{a}{q^2}=\frac{p(2-p)}{(1-p)^2}.
$$
$\mu=\sum_{n\geqq0}nQ_n$ とおく。$N\leqq\tau$ と
補題2
より $\mu < \infty$ である。$Q_n=aQ_{n-1}$($n\geqq1$)と $\sum_{k\geqq0}Q_k=1$ より
$$
\mu=\sum_{n=1}^{\infty}n\,aQ_{n-1}=a\sum_{k=0}^{\infty}(k+1)Q_k=a(\mu+1),
$$
よって $\mu=\dfrac{a}{1-a}$ である。確率 $a$ で1点を得て再生し,以後の期待得点は再び $\mu$ である,という再生構造の期待値版である。
$G(z)=\sum_{n\geqq0}Q_nz^n=\dfrac{q^2}{1-az}$ は $\lvert z\rvert < 1/a$ で収束し,$1 < 1/a$ だから $z=1$ は収束円の内部にある。項別微分により $\mu=G'(1)=\dfrac{aq^2}{(1-a)^2}=\dfrac{a}{q^2}$ である。
三つの導出は一致する。(a) は非負整数値確率変数に対する公式 $\mathbb{E}[N]=\sum_{k\geqq1}\mathbb{P}(N\geqq k)$ の有限版(Abel の部分和変形)であり,誘導 (3) の代わりに付記の極限だけを用いる。$p=\frac12$ では $\sum_{k\geqq1}\left(\frac34\right)^k=3$。(b) では $\mu < \infty$ の確認を省くと,$\mu=\infty$ も方程式 $\mu=a(\mu+1)$ を形式的に満たすので結論が出ない。
$n$ 点で終了する投球列そのものを数える。 補題1 より,それは $\mathcal{B}^n\mathrm{TT}$ の語で始まる列であり,$n$ 個の表のそれぞれの直前に裏を高々1個置き,末尾に $\mathrm{TT}$ を付けたものである。$\mathrm{TH}$ ブロックの個数で分類し,二項定理で合計する。
$w\in\mathcal{B}^n$ のうち $\mathrm{TH}$ を $k$ 個含むものは $\binom{n}{k}$ 個あり,そのそれぞれについて $\lvert w\mathrm{TT}\rvert_{\mathrm{H}}=n$,$\lvert w\mathrm{TT}\rvert_{\mathrm{T}}=k+2$ であるから $\mathbb{P}([w\mathrm{TT}])=p^nq^{k+2}$ である。
補題1
(iii) より
$$
Q_n=\sum_{k=0}^{n}\binom{n}{k}p^nq^{k+2}=q^2p^n\sum_{k=0}^{n}\binom{n}{k}q^k=q^2p^n(1+q)^n=(1-p)^2\lbrace p(2-p)\rbrace^n.
$$
$n=1$ の終了列は $\mathrm{HTT},\mathrm{THTT}$,$n=2$ の終了列は $\mathrm{HHTT},\mathrm{HTHTT},\mathrm{THHTT},\mathrm{THTHTT}$ であり,(1) の値は直接にも確かめられる。
裏を置ける位置は各 $\mathrm{H}$ の直前の $n$ 箇所に限られる。最後の $\mathrm{H}$ と末尾の $\mathrm{TT}$ の間に裏を置くと $\mathrm{TTT}$ となり,終了は1投早まってしまう。$n=0$ では $\mathcal{B}^0\mathrm{TT}=\lbrace\mathrm{TT}\rbrace$ で $Q_0=q^2$ である。
副産物として,終了前に孤立して現れる裏($\mathrm{TH}$ ブロック)の個数を $K$ とすると
$$
\mathbb{P}(N=n,\ K=k)=\binom{n}{k}p^nq^{k+2},\qquad K\mid(N=n)\sim\operatorname{Bin}\left(n,\ \frac{q}{1+q}\right)
$$
である。$\tau=N+K+2$ だから $\mathbb{E}[\tau\mid N=n]=n+2+\frac{nq}{1+q}$ であり,(4) の値と合わせると
$$
\mathbb{E}[\tau]=\frac{p(1+q)}{q^2}\cdot\frac{1+2q}{1+q}+2=\frac{p(1+2q)+2q^2}{q^2}=\frac{1+q}{q^2}
$$
となって,
別解4
で独立に求める値と一致する。
1投ずつ追う。終了判定に必要な情報は「直前が裏か」の1ビットだから,状態を $S_0$(開始時または直前が表)と $S_1$(直前が裏で未終了)の2つに圧縮し,第1投で場合分けする。
状態 $S_0$ から始めたゲーム(通常のゲーム)と,状態 $S_1$ から始めたゲーム(直前に裏が出ているとみなして始めるゲーム)について,その後に獲得する点数がちょうど $n$ となる確率をそれぞれ $u_n$,$v_n$ とし,$u_{-1}=0$ と定める。$u_n=Q_n$ である。第2投以降の投球列は第1投と独立で,元の投球列と同じ分布に従うから,第1投の結果で場合分けして
$$
u_n=pu_{n-1}+qv_n\quad(n\geqq0),\qquad v_0=q,\qquad v_n=pu_{n-1}\quad(n\geqq1)
$$
を得る。$S_0$ から表なら1点を得て $S_0$ へ,裏なら $S_1$ へ移り,$S_1$ から表なら1点を得て $S_0$ へ移り,裏なら $0$ 点のまま終了するからである。
$n=0$ のとき $u_0=qv_0=q^2$。$n\geqq1$ のとき $u_n=pu_{n-1}+qpu_{n-1}=au_{n-1}$。よって
$$
Q_n=u_n=q^2a^n=(1-p)^2\lbrace p(2-p)\rbrace^n.
$$
$S_1$ から裏が出ると即座に終了するため,$v_n$ は $n=0$ と $n\geqq1$ で式が異なる。ここを $v_n=pu_{n-1}+q$ とすると $u_n$ が過大になる。公比 $p(1+q)$ が $1$ 以上になれば立式の誤りである。母関数 $F_0(z)=\sum u_nz^n$,$F_1(z)=\sum v_nz^n$ は $F_0=pzF_0+qF_1$,$F_1=pzF_0+q$ を満たし,$F_0(z)=\frac{q^2}{1-az}$ となる。終了条件を裏 $r$ 連続に変えれば状態は $S_0,\ldots,S_{r-1}$ の $r$ 個になる。
表ではなく裏を区切りにする。投球列を「表が $g$ 個続いた後に裏が1個」という連 $\mathrm{H}^g\mathrm{T}$ に区切ると,各連の表の個数は独立同分布の幾何分布に従う。ゲームは,表を含まない連(直前の裏に続く裏)が初めて現れたときに終わる。得点を,幾何分布に従う確率変数のランダムな個数の和として表す。
$\mathbb{P}(C_j=\cdots=C_{j+m-1}=\mathrm{H})=p^m\to0$ より裏は確率 $1$ で無限回現れるので,投球列を
$$
\mathrm{H}^{G_0}\mathrm{T}\ \mathrm{H}^{G_1}\mathrm{T}\ \mathrm{H}^{G_2}\mathrm{T}\cdots
$$
と区切れる。列が $\mathrm{H}^{g_0}\mathrm{T}\cdots\mathrm{H}^{g_j}\mathrm{T}$ で始まる確率は $\prod_{i=0}^{j}p^{g_i}q$ であるから,$G_0,G_1,\ldots$ は独立で,いずれも $\mathbb{P}(G=g)=p^gq$($g\geqq0$)に従う。$\mathrm{TT}$ は,$i\geqq1$ で $G_i=0$ となる連(直前の連の裏に続く裏)で初めて完成する。そこで $K=\min\lbrace i\geqq1 : G_i=0\rbrace-1$ とおくと
$$
N=G_0+\sum_{i=1}^{K}G_i,\qquad G_1,\ldots,G_K\geqq1
$$
である。$\mathbb{P}(G_i\geqq1)=p$ より $\mathbb{P}(K=k)=p^kq$ である。さらに $G'_0=G_0$,$G'_i=G_i-1$($1\leqq i\leqq K$)とおくと $N=K+\sum_{i=0}^{K}G'_i$ であり,任意の非負整数 $g_0,\ldots,g_k$ について
$$
\mathbb{P}(K=k,\ G'_0=g_0,\ldots,G'_k=g_k)=p^{g_0}q\prod_{i=1}^{k}p^{1+g_i}q\cdot q=\mathbb{P}(K=k)\prod_{i=0}^{k}p^{g_i}q.
$$
すなわち,$K=k$ のもとで $G'_0,\ldots,G'_k$ は独立に同じ幾何分布に従う。和が $n-k$ となる非負整数の組 $(g_0,\ldots,g_k)$ は $\binom{n}{k}$ 組あるから,$0\leqq k\leqq n$ について
$$
\mathbb{P}(N=n\mid K=k)=\binom{n}{k}p^{n-k}q^{k+1},
$$
$$
Q_n=\sum_{k=0}^{n}p^kq\cdot\binom{n}{k}p^{n-k}q^{k+1}=q^2p^n(1+q)^n=(1-p)^2\lbrace p(2-p)\rbrace^n.
$$
$K=0$ のとき $N=G_0$ であり,最初の裏の直後にもう一度裏が出て終了する場合に一致する。裏の直後に出て継続を決める表は $K$ に1個ずつ数えられ,$G'_i$ では数えない。$K=k$ のとき足し合わせる $G'_i$ は $k$ 個ではなく $k+1$ 個である。同時確率 $\mathbb{P}(N=n,\ K=k)=\binom{n}{k}p^nq^{k+2}$ は 別解1 と一致する。$K$ は同じ量(孤立した裏の個数)であるが,別解1 は終了列を固定してから数え,本法は $K$ で条件付けてから幾何分布の和を数える。
得点の分布を経由しない。まず終了までの投球回数 $\tau$ の期待値を,最初の裏で分解する更新方程式で求め, 補題3 の $\mathbb{E}[N]=p\,\mathbb{E}[\tau]$ で得点に変換する。
最初に裏が出る時刻を $\sigma$ とすると $\mathbb{P}(\sigma=k)=p^{k-1}q$ であり,(3) で $x=p$ として $\mathbb{E}[\sigma]=\sum_{k\geqq1}kp^{k-1}q=\frac{q}{(1-p)^2}=\frac1q$ である。第 $\sigma+1$ 投が裏なら $\tau=\sigma+1$ である。表なら,その時点で直前が表であるから,そこから $\mathrm{TT}$ が完成するまでの投球回数 $\tau''$ は $(\sigma,C_{\sigma+1})$ と独立で $\tau$ と同分布である。よって $\tau=\sigma+1+\mathbf{1}_{\lbrace C_{\sigma+1}=\mathrm{H}\rbrace}\tau''$ であり
$$
\mathbb{E}[\tau]=\frac1q+1+p\,\mathbb{E}[\tau].
$$
補題2
より $\mathbb{E}[\tau] < \infty$ なので移項でき,$q\,\mathbb{E}[\tau]=\frac1q+1$,すなわち
$$
\mathbb{E}[\tau]=\frac{1+q}{q^2}.
$$
補題3
より
$$
\sum_{n=0}^{\infty}nQ_n=\mathbb{E}[N]=p\,\mathbb{E}[\tau]=\frac{p(1+q)}{q^2}=\frac{p(2-p)}{(1-p)^2}.
$$
$p=\frac12$ では $\mathbb{E}[\tau]=6$,$\mathbb{E}[N]=3$,$\mathbb{E}[X]=3$ で,$\tau=N+X$ と整合する。$\mathbb{E}[\tau]$ は「パターンの確率の逆数」$\frac{1}{q^2}$($p=\frac12$ で $4$)ではない。$\mathrm{TT}$ が自己重複をもつためであり, 参考解4 でこの差を説明する。値は 補題2 の上界 $\frac{2}{q^2}$ 以下である。
各終了列で成り立つ個数の恒等式(経路ごとの保存則)から出発する。終了までの裏の総数 $X$ と,連続する $\mathrm{TH}$ の出現回数 $Y$ の間には,すべての終了列で $X=Y+2$ が成り立つ。これと,各裏の次の1投の独立性を組み合わせる。
$\tau < \infty$ とする。最後の2個以外の裏は直後に表を伴い(さもなければその時点で終了している),最後の2個の裏の後にゲーム内の投球はないから
$$
X=Y+2
$$
である。$Y=\sum_{j\geqq1}\mathbf{1}_{\lbrace C_j=\mathrm{T},\ \tau > j,\ C_{j+1}=\mathrm{H}\rbrace}$ と表され,事象 $\lbrace C_j=\mathrm{T},\ \tau > j\rbrace$ は $\mathcal{F}_j$ に属するので $C_{j+1}$ と独立である。また $\sum_{j\geqq1}\mathbf{1}_{\lbrace C_j=\mathrm{T},\ \tau > j\rbrace}$ は終了時の裏 $C_\tau$ を除く裏の個数 $X-1$ に等しい。よって
$$
\mathbb{E}[Y]=p\sum_{j\geqq1}\mathbb{P}(C_j=\mathrm{T},\ \tau > j)=p\,(\mathbb{E}[X]-1).
$$
$\mathbb{E}[X]\leqq\mathbb{E}[\tau] < \infty$(
補題2
)であるから,$\mathbb{E}[X]=\mathbb{E}[Y]+2=p\,\mathbb{E}[X]-p+2$ より $q\,\mathbb{E}[X]=1+q$,すなわち $\mathbb{E}[X]=\frac{1+q}{q}$ である。
補題3
より $\mathbb{E}[N]=p\,\mathbb{E}[\tau]=\frac{p}{q}\,\mathbb{E}[X]$ であるから
$$
\sum_{n=0}^{\infty}nQ_n=\frac{p(1+q)}{q^2}=\frac{p(2-p)}{(1-p)^2}.
$$
$\mathrm{THTT}$ では $X=3$,$Y=1$ で $X=Y+2$ が成り立つ。$\mathbb{E}[Y]=p(\mathbb{E}[X]-1)$ は「$X$ を固定すると $Y\sim\operatorname{Bin}(X-1,p)$」という意味ではない。実際 $X$ を固定すれば $Y=X-2$ は確定している。この等式は,各時刻で次の1投が独立であることから期待値の水準でのみ成り立つ。$\mathbb{E}[X]-2=\frac{p}{q}$ は,孤立した裏の個数 $K$($=Y$)の期待値 $\frac{p}{q}$( 別解3 )と一致する。
終了後も投げ続けた無限列で,$\mathrm{TT}$ のすべての出現(重なりを許す)を重み付きで数えることは容易である。各時刻での出現は局所的な条件だからである。一方,初回の出現より後の出現は,初回の出現への重なり($\mathrm{TTT}$ による直後の出現)と,初回の出現の後の独立な投球列での出現に分けられる。この関係から初回出現の得点母関数を取り出す。
$0 < z < 1$ とし,$F(z)=\mathbb{E}[z^N]$(
補題2
より $N$ は確率 $1$ で有限)とおく。$\mathrm{TT}$ のすべての出現を数える量
$$
R(z)=\mathbb{E}\left[\sum_{m=2}^{\infty}z^{H_m}\mathbf{1}_{\lbrace C_{m-1}=C_m=\mathrm{T}\rbrace}\right]
$$
を考える。$C_{m-1}=C_m=\mathrm{T}$ のとき $H_m=H_{m-2}$ であり,$H_{m-2}$ は $C_{m-1},C_m$ と独立で $\mathbb{E}[z^{H_{m-2}}]=(pz+q)^{m-2}$ だから
$$
R(z)=\sum_{m=2}^{\infty}q^2(pz+q)^{m-2}=\frac{q^2}{1-(pz+q)}=\frac{q^2}{p(1-z)}.
$$
出現の時刻 $m$ を $\tau$ との関係で分類する。$m < \tau$ はあり得ない。$m=\tau$ の寄与は $\mathbb{E}[z^N]=F(z)$ である。$m=\tau+1$ の出現は $C_{\tau+1}=\mathrm{T}$ のときに限って起こり,$H_{\tau+1}=N$ であるから寄与は $qF(z)$ である。$m\geqq\tau+2$ の出現は,列 $C'_k=C_{\tau+k}$ における時刻 $m-\tau\geqq2$ の出現であり,$H_m=N+H'_{m-\tau}$ である。列 $(C'_k)$ は $(\tau,N)$ と独立で元の列と同分布である($\tau=\lvert w\rvert$ となる各語 $w$ について $[w]$ と $(C'_k)$ に関する事象が独立であることによる)から,この寄与は $F(z)R(z)$ である。したがって
$$
R(z)=F(z)+qF(z)+F(z)R(z),\qquad F(z)=\frac{R(z)}{1+q+R(z)}=\frac{q^2}{p(1+q)(1-z)+q^2}=\frac{q^2}{1-az}.
$$
最後に $p(1+q)+q^2=a+q^2=1$ を用いた。$0 < z < 1$ で $\sum Q_nz^n=\sum q^2a^nz^n$ が成り立つから,べき級数の係数の一意性より $Q_n=q^2a^n=(1-p)^2\lbrace p(2-p)\rbrace^n$ である。
$\lim_{z\to1-0}F(z)=\frac{q^2}{1-a}=1$ は正規化に一致する。重なりの項 $qF(z)$ を落とすと $F=\frac{R}{1+R}=\frac{q^2}{p(1-z)+q^2}$ となり,$F(1)=1$ は満たすが $Q_0=\frac{q^2}{p+q^2}\neq q^2$ となって誤る。$R(z)$ は $z=1$ で発散する(出現は無限回)ので,$0 < z < 1$ で式を立てる必要がある。係数 $1+q$ は $\mathrm{TT}$ の相関多項式の $u=1$ での値である( 5.5 節 )。
分布の方程式を先に立てず,1投の前後で条件付き期待値が変わらない状態の関数を構成し,開始時と終了時の値を比べる。第 $t$ 投直後に連続している裏の個数を $D_t$($D_0=0$)とし,$f(h,d)=z^hg(d)$ の形の関数を探す。調和性の条件は
$$
g(0)=pz\,g(0)+q\,g(1),\qquad g(1)=pz\,g(0)+q\,g(2)
$$
であり,$g(0)=1$ と正規化すると $g(1)=\frac{1-pz}{q}$,$g(2)=\frac{1-az}{q^2}$ と決まる。$g(d)=z+(1-z)q^{-d}$ はこれらを満たす閉じた形である。
$0 < z < 1$ とし,
$$
W_t=z^{H_{t\wedge\tau}}\left\lbrace z+(1-z)q^{-D_{t\wedge\tau}}\right\rbrace
$$
とおく。終了前は $D_t\in\lbrace0,1\rbrace$,終了時は $D_\tau=2$ である。$t < \tau$ で $H_t=h$,$D_t=d$ とすると,次が表なら $(h+1,0)$,裏なら $(h,d+1)$ に移るから
$$
\mathbb{E}[W_{t+1}\mid\mathcal{F}_t]=pz^{h+1}\lbrace z+(1-z)\rbrace+qz^h\left\lbrace z+(1-z)q^{-(d+1)}\right\rbrace=z^h\left\lbrace z+(1-z)q^{-d}\right\rbrace=W_t.
$$
$t\geqq\tau$ では $W_{t+1}=W_t$ である。よって $\mathbb{E}[W_t]=W_0=1$ がすべての $t$ で成り立つ。$0\leqq W_t\leqq q^{-2}$ であり,$\tau < \infty$ が確率 $1$ で成り立つから,有界収束定理より $\mathbb{E}[W_\tau]=\lim_{t\to\infty}\mathbb{E}[W_t]=1$ である。$H_\tau=N$,$D_\tau=2$ より
$$
\mathbb{E}[z^N]\left\lbrace z+(1-z)q^{-2}\right\rbrace=1,\qquad \mathbb{E}[z^N]=\frac{q^2}{1-(1-q^2)z}=\sum_{n=0}^{\infty}q^2a^nz^n.
$$
係数を比較して $Q_n=q^2a^n$ を得る。
期待値だけなら $M_t=q^{-D_{t\wedge\tau}}-H_{t\wedge\tau}$ を用いる。$t < \tau$ で
$$
\mathbb{E}[M_{t+1}\mid\mathcal{F}_t]=p\lbrace1-(h+1)\rbrace+q\left\lbrace q^{-(d+1)}-h\right\rbrace=q^{-d}-h=M_t
$$
であり,$M_0=1$ である。$\lvert M_t\rvert\leqq q^{-2}+\tau$ かつ $\mathbb{E}[\tau] < \infty$(
補題2
)であるから,優収束定理より $\mathbb{E}[M_\tau]=1$,すなわち $q^{-2}-\mathbb{E}[N]=1$ となり
$$
\sum_{n=0}^{\infty}nQ_n=\frac{1}{q^2}-1=\frac{p(2-p)}{(1-p)^2}.
$$
$z\to+0$ とすると $Q_0=q^2$ を得る。$-\left.\partial_zW_t\right\rvert_{z=1}=q^{-D_{t\wedge\tau}}-H_{t\wedge\tau}-1=M_t-1$ であり,$M$ は $W$ を $z=1$ で微分したものに当たるから,$\mathbb{E}[N]=F'(1)$ と整合する。$M$ は非有界なので,$\mathbb{E}[\tau] < \infty$ を確かめずに停止時刻で期待値をとってはならない。終了条件を裏 $r$ 連続に変えても同じ $W_t$ がそのまま使え,$\mathbb{E}[z^N]=\frac{q^r}{1-(1-q^r)z}$ を与える。
各投球の直前に賭け手が1人ずつ参加し,パターン $\mathrm{TT}$ の文字を順に公平な倍率で賭ける(Li の方法)。参加者全体の期待収支は $0$ であるが,終了時に正の所持金をもつ参加者はパターンの自己重複だけで決まる。
$\tau\geqq j$ のとき,第 $j$ 投の直前に1円をもつ賭け手 $j$ が参加する。賭け手は第 $j$ 投で裏に全額を賭け,裏なら所持金を $q^{-1}$ 倍,表なら $0$ 円とする。裏が出てゲームが続いていれば,第 $j+1$ 投でも裏に全額を賭ける。2回賭けるか,ゲームが終了した時点で賭けを終える。賭け手 $j$ の最終所持金を $V_j$(参加しなければ $0$)とする。
$q\cdot q^{-1}+p\cdot0=1$ だから各賭けは公平である。第2回の賭けについて $\mathcal{F}_j$ で条件付けると $\mathbb{E}[q^{-1}\mathbf{1}_{\lbrace C_{j+1}=\mathrm{T}\rbrace}\mid\mathcal{F}_j]=1$ であり,$\lbrace\tau\geqq j\rbrace\in\mathcal{F}_{j-1}$ は $C_j$ と独立だから
$$
\mathbb{E}[V_j]=\mathbb{E}\left[\mathbf{1}_{\lbrace\tau\geqq j\rbrace}\,q^{-1}\mathbf{1}_{\lbrace C_j=\mathrm{T}\rbrace}\right]=\mathbb{P}(\tau\geqq j).
$$
非負項の和であるから
$$
\mathbb{E}\left[\sum_{j\geqq1}V_j\right]=\sum_{j\geqq1}\mathbb{P}(\tau\geqq j)=\mathbb{E}[\tau].
$$
一方,各経路で終了時の所持金を数える。$j\leqq\tau-2$ の賭け手が2回とも勝つには $C_j=C_{j+1}=\mathrm{T}$ が必要であるが,それは $\tau\leqq j+1 < \tau$ を意味し不可能だから $V_j=0$ である。賭け手 $\tau-1$ は $C_{\tau-1}=C_\tau=\mathrm{T}$ に2回勝って $q^{-2}$ 円,賭け手 $\tau$ は $C_\tau=\mathrm{T}$ に勝ったところでゲームが終わり $q^{-1}$ 円をもつ。よって $\sum_jV_j=q^{-2}+q^{-1}$ が確率 $1$ で成り立ち
$$
\mathbb{E}[\tau]=\frac{1}{q^2}+\frac1q=\frac{1+q}{q^2},\qquad \sum_{n=0}^{\infty}nQ_n=p\,\mathbb{E}[\tau]=\frac{p(2-p)}{(1-p)^2}
$$
(後者は
補題3
)。
$p=\frac12$ では $4+2=6$ で 別解4 と一致する。二つの項は $\mathrm{TT}$ の重なりに対応する。$q^{-2}$ はパターン全体,$q^{-1}$ は「接尾辞 $\mathrm{T}$ が接頭辞 $\mathrm{T}$ と一致する」重なりに由来する。重なりをもたない $\mathrm{HT}$ では平均待ち時間は $\frac{1}{pq}$ だけになる。終了時の総所持金が定数になるため,この議論は $\mathbb{E}[\tau] < \infty$ を前提とせず,その値まで与える。
個々のゲームではなく無限の投球列を定常過程とみる。$\mathrm{TT}$ の出現頻度は $q^2$ であり,Kac の再帰定理により出現間隔の平均は $\frac{1}{q^2}$ である。出現直後から次の出現までの時間を「重なりによる即時の再出現」と「再出発」に分け,初回待ち時間と結びつける。
$Y_m=(C_{m-1},C_m)$($m\geqq2$)は4状態 $\lbrace\mathrm{HH},\mathrm{HT},\mathrm{TH},\mathrm{TT}\rbrace$ 上の既約な Markov 連鎖で,定常分布は $\pi(xy)=\mathbb{P}(C_1=x)\,\mathbb{P}(C_2=y)$ である。有限既約 Markov 連鎖の平均再帰時間は定常確率の逆数であるから,状態 $\mathrm{TT}$ から出発して次に $\mathrm{TT}$ に戻るまでの時間 $L$ について $\mathbb{E}[L]=\frac{1}{q^2}$ である。
$\mathrm{TT}$ の直後の1投が裏なら $L=1$ である。表なら,その時点で直前が表であるから,そこから $\mathrm{TT}$ が完成するまでの時間は $\tau$ と同分布であり,$L=1+\tau'$ となる。よって
$$
\frac{1}{q^2}=\mathbb{E}[L]=q\cdot1+p\left(1+\mathbb{E}[\tau]\right)=1+p\,\mathbb{E}[\tau].
$$
補題3
より
$$
\sum_{n=0}^{\infty}nQ_n=p\,\mathbb{E}[\tau]=\frac{1}{q^2}-1=\frac{p(2-p)}{(1-p)^2}.
$$
$p=\frac12$ では $\mathbb{E}[L]=4$,$\mathbb{E}[\tau]=6$ である。$\frac{1}{q^2}$ は定常的な出現間隔の平均であり,開始時からの初回待ち時間ではない。両者の差は,$\mathrm{TT}$ の直後に確率 $q$ で即座に再出現する重なりに由来する。得られた関係 $\mathbb{E}[N]=\mathbb{E}[L]-1$ は「期待得点は定常出現間隔より1小さい」と読める。Kac の再帰定理は高校数学の範囲外である。
以下は独立の解法とは数えず,既出の解法の表現違い,図式化,部分的な短縮として扱う。
| 解法 | 主に利用する構造 | 対象 | 範囲 | 長所 | 注意点 |
|---|---|---|---|---|---|
| 本解 | 得点時点での再生 | 全設問 | 高校 | 最短で,問題の本質を表す | 排反分解と独立性の明示 |
| 3.1 格子点 | 等比級数の積 | (3) | 高校 | 係数の意味が明瞭,付記の極限が不要 | 無限和の並べ替えを避ける |
| 3.2 確率実験 | 負の二項分布の正規化 | (3) | 高校 | 剰余項に確率的意味を与える | 原題のコインと混同しない |
| 3.3 微分 | 有限等比和の微分 | (3) | 高校 | 機械的に計算できる | 項別微分と混同しない |
| 3.4 到達確率 | 裾確率の和,自己再生 | (4) | 高校 | (3) を経由しない | 期待値の有限性の確認 |
| 別解1 | 接頭符号分解 | (1)(2) | 高校 | 直接の数え上げで検証が容易 | 裏の挿入位置 |
| 別解2 | 2状態遷移 | (1)(2) | 高校 | 一般のパターンへ拡張できる | 添字と $n=0$ の扱い |
| 別解3 | 連の独立性,ランダム和 | (1)(2)(4) | 高校〜大学 | 同時分布と条件付き構造が見える | 継続の表の二重計上 |
| 別解4 | 停止時刻,Wald 型等式 | (4) | 高校〜大学 | 分布を経由しない | 可積分性と独立性の根拠 |
| 別解5 | 経路保存則 | (4) | 高校〜大学 | 個数の恒等式から出発する | 条件付き二項分布と誤認しない |
| 参考解1 | 全出現と初回出現 | (1)(2) | 大学 | 一般のパターンへ拡張できる | 重なりの項 $qF$ |
| 参考解2 | マルチンゲール | (1)(2)(4) | 大学 | 保存量から一挙に求まる | 停止時刻での可積分性 |
| 参考解3 | 公平な賭け | (4) | 大学 | 自己重複が賞金として見える | Wald 型等式との併用 |
| 参考解4 | Kac の再帰定理 | (4) | 大学 | $\mathbb{E}[N]=\mathbb{E}[L]-1$ が直接出る | 再帰時間と初回待ち時間の区別 |
試験場での第一選択は,本解(再生)と (3) の差分法である。発想の飛躍がなく,(1) から (4) までが同じ量 $a$ の上に一貫して構成され,各段階に検算点がある。別解1 は組合せ的な構造認識,別解2 は状態遷移という汎用技法を代表し,誘導のない類題ではこちらが主役になりうる。別解3〜5 は分布全体を経由せずに確率変数の分解や個数の恒等式から期待値に至る道を示す。参考解は試験の答案には過剰であるが,$\mathrm{TT}$ の自己重複という,得点で観測すると隠れる構造を,母関数・保存量・賭け・定常頻度という四つの異なる理論から説明する。
本問から抽出される,「独立試行を,あるパターンが現れるまで続け,途中で生じる量を数える」型の問題に対する探索手順を述べる。
| 症状 | 検討する表現・道具 | 本問での例 |
|---|---|---|
| ある出来事で履歴が完全に消える | 再生時点,到達確率,幾何分布 | 本解,3.4 節 |
| 終了列の形が確定する | 接頭符号分解,二項定理,正規表現 | 別解1 |
| 終了判定に有限の履歴が要る | 状態遷移,連立漸化式,母関数 | 別解2 |
| 別の文字で区切ると独立な塊が現れる | 連への分解,ランダム和 | 別解3 |
| 期待値だけが問われ,停止時刻が絡む | 更新方程式,Wald 型等式 | 別解4 |
| 経路ごとに個数の関係が成り立つ | 経路保存則 | 別解5 |
| パターンが自分自身と重なる | 全出現と初回出現,相関多項式 | 参考解1 |
| 状態の関数で期待値が保存される | マルチンゲール,調和関数 | 参考解2 |
| パターンの平均待ち時間 | 公平な賭け(Li の方法) | 参考解3 |
| 長期頻度は易しく初回は難しい | Kac の再帰定理 | 参考解4 |
| 係数が $n+1$ や二項係数 | 差分,格子点,負の二項分布,微分 | (3),3.1〜3.3 節 |
裏 $r$ 連続で終了する場合。表は依然として再生点であり,再生時点から次の1点の前に終了する確率は $q^r$ である。終了時の得点 $N_r$ と終了までの投球回数 $\tau_r$ について
$$
\mathbb{P}(N_r=n)=q^r(1-q^r)^n,\qquad \mathbb{E}[N_r]=q^{-r}-1,\qquad \mathbb{E}[\tau_r]=\frac{q^{-r}-1}{p}=\sum_{k=1}^{r}q^{-k}
$$
である。$\mathbb{E}[\tau_r]$ は
補題3
と同じ議論による。
参考解3
で各賭け手が裏に最大 $r$ 回賭けるとしても,終了時に所持金が残る $r$ 人の賞金 $q^{-r},q^{-(r-1)},\ldots,q^{-1}$ の和として直接得られる。
裏の個数を数える場合。再生時点を「終了していない裏の直後」に取り替える。そこで表が出れば継続し,裏が出れば終了するから,孤立した裏の個数 $K$ は $\mathbb{P}(K=k)=p^kq$ に従い,裏の総数は $X=K+2$ である。$\mathbb{E}[X]=2+\frac{p}{q}=\frac{1+q}{q}$ は
別解5
の結果と一致する。
一般のパターンで終了する場合。表の直後の照合状態が履歴によらず一つに定まれば,その状態が再生点となり,得点は(ずらした)幾何分布に従う。$\mathrm{HT}$,$\mathrm{HH}$ はこの条件を満たす(表の直後は常に「$\mathrm{H}$ まで一致」)。$\mathrm{THT}$ は満たさない(直前が裏なら「$\mathrm{TH}$ まで一致」,そうでなければ一致なし)。照合状態を「一致なし」「$\mathrm{T}$」「$\mathrm{TH}$」として
別解2
と同様に解くと
$$
\mathbb{E}[z^N]=\frac{q^2z}{1-pz-pqz^2},\qquad \mathbb{E}[N]=\frac{1+pq}{q^2}
$$
となり,分母が2次式であるから得点は幾何分布ではない。期待値は,
5.5 節
の公式による $\mathbb{E}[\tau]=\frac{1}{pq^2}+\frac1q$ と
補題3
からも得られる。
| 事項 | 高校数学での扱い | 一般理論 |
|---|---|---|
| 再出発の議論 | 投球列の場合分けと独立性 | 再生過程,強 Markov 性 |
| 2状態の漸化式 | 連立漸化式 | 吸収的 Markov 連鎖,基本行列 |
| 終了列の一意分解 | 二項定理による数え上げ | 接頭符号,正規言語,記号的方法 |
| 期待値と級数 | 有限部分和の極限 | 確率母関数,非負項級数の交換(Tonelli) |
| 停止時刻での期待値 | 更新方程式で代替 | Wald の等式,任意停止定理 |
| パターンの待ち時間 | 状態の場合分け | Li の方法,相関多項式 |
| 長期的な出現頻度 | 扱わない | Kac の再帰定理,エルゴード理論 |
| (3) の級数 | 差分,はさみうち | べき級数の項別微分,負の二項分布 |
本解,3.1〜3.4 節(3.4 節 (c) を除く),別解1〜2 は左欄の範囲で完結する。別解3〜5 は高校数学の言葉で書けるが,条件付き分布や停止時刻の独立性の扱いに大学の確率論の視点を要する。参考解1〜4 は右欄の理論の具体例である。
非負整数値の確率変数 $N$ が無記憶性 $\mathbb{P}(N\geqq m+n\mid N\geqq m)=\mathbb{P}(N\geqq n)$($\mathbb{P}(N\geqq m) > 0$ となる任意の $m,n$)をもつとき,$g(n)=\mathbb{P}(N\geqq n)$ は $g(m+n)=g(m)g(n)$ を満たし,$g(n)=g(1)^n$ となる。すなわち無記憶性は幾何分布を特徴付ける。本問の得点は,再生時点ごとに確率 $a$ で次へ進む構造からこの無記憶性をもつ。
Feller は,生起するたびに過程が新しく始まる事象を再帰事象(recurrent event)と呼び,その理論を展開した。いつかは生起する確率 $f$ が $1$ 未満の(一時的な)再帰事象では,生起回数が少なくとも $n$ である確率は $f^n$ である。本問は「得点の増加」を再帰事象とみなし,その待ち時間が確率 $q^2$ で無限大となる($f=a$ の)場合にあたる。再生時点 $\theta_n$ は停止時刻であり,独立試行列は停止時刻の後で過去と独立に新しく始まる(強 Markov 性)。
補題1
は,接頭辞の事象への分解によってこの性質を本問の範囲で初等的に示したものである。
一時的な状態 $S_0,S_1$ の間の推移行列と,その基本行列は
$$
\Lambda=\begin{pmatrix}p&q\\p&0\end{pmatrix},\qquad (I-\Lambda)^{-1}=\frac{1}{q^2}\begin{pmatrix}1&q\\p&q\end{pmatrix}
$$
である。$(i,j)$ 成分は,$S_i$ から出発して終了までに状態 $S_j$ から投げる回数の期待値である。第1行の和 $\frac{1+q}{q^2}$ は $\mathbb{E}[\tau]$ に一致し,どの状態からの投球も確率 $p$ で表だから $\mathbb{E}[N]=p\,\mathbb{E}[\tau]$ となる。表に変数 $z$ を付けた行列 $\Lambda(z)=\begin{pmatrix}pz&q\\pz&0\end{pmatrix}$ については $\det(I-\Lambda(z))=1-az$ であり,終了への推移ベクトル $(0,q)^{\top}$ と合わせて
$$
\mathbb{E}[z^N]=\begin{pmatrix}1&0\end{pmatrix}(I-\Lambda(z))^{-1}\begin{pmatrix}0\\q\end{pmatrix}=\frac{q^2}{1-az}
$$
を得る。得点の母関数の分母は行列式であり,その次数が1であることが幾何分布の代数的な表れである。
終了列の全体は曖昧さのない正規表現 $(\mathrm{H}\mid\mathrm{TH})^{\ast}\mathrm{TT}$ で表される。$\mathrm{H}$ に重み $pzu$,$\mathrm{TH}$ に $pqzu^2$,$\mathrm{TT}$ に $q^2u^2$ を与えると,反復は等比級数に,連結は積に対応し(記号的方法),得点と投球回数の同時母関数
$$
\mathbb{E}[z^Nu^\tau]=\frac{q^2u^2}{1-pzu-pqzu^2}
$$
を得る。$u=1$ とすれば $\frac{q^2}{1-az}$,$z=1$ とすれば
1.4 節
の Fibonacci 型の分布の母関数になる。また $N=n$ のもとでは $n$ 個のブロックが独立に確率 $\frac{q}{1+q}$ で $\mathrm{TH}$ となり,孤立した裏の個数は二項分布 $\operatorname{Bin}\left(n,\frac{q}{1+q}\right)$ に従う。
一般のパターン $w$ でも,照合状態(直近の列の接尾辞に一致する $w$ の最長の接頭辞)を状態とする有限オートマトンが構成でき(Knuth–Morris–Pratt の失敗関数と同じ構造),得点の母関数は常に有理関数になる。本問では分母が1次式 $1-az$ であることが幾何分布に対応し,$\mathrm{THT}$ では分母が2次式になる(
4.3 節
)。
長さ $L$ のパターン $w=w_1\cdots w_L$ が $d$ 文字ずらして自分自身と重なる($w_{d+1}\cdots w_L=w_1\cdots w_{L-d}$)とき $c_d=1$,そうでないとき $c_d=0$ とする($0\leqq d\leqq L-1$,$c_0=1$)。独立同分布の文字列で $w$ が初めて完成する時刻 $\tau_w$ について
$$
\mathbb{E}[\tau_w]=\sum_{d=0}^{L-1}\frac{c_d}{\mathbb{P}(w_1\cdots w_{L-d})}
$$
が成り立つ(Conway の算法の一般形。公平な賭けによる証明は Li による)。$\mathrm{TT}$ では $c_0=c_1=1$ で $\frac{1}{q^2}+\frac1q$ となり,参考解3 の二つの賞金に一致する。さらに相関多項式 $C_w(u)=\sum_dc_d\,\mathbb{P}(w_{L-d+1}\cdots w_L)\,u^d$ を用いると
$$
\sum_{m}\mathbb{P}(\tau_w=m)\,u^m=\frac{\mathbb{P}(w)u^L}{\mathbb{P}(w)u^L+(1-u)C_w(u)}
$$
である(Guibas–Odlyzko)。$\mathrm{TT}$ では $C(u)=1+qu$ で,右辺は $\frac{q^2u^2}{1-pu-pqu^2}$ に一致する。参考解1 の係数 $1+q$ は $C(1)$ である。自己相関の違いは,2人がパターンを選んで先に出た方が勝つ Penney のゲームの非推移性の原因でもある。
$(M_t)$ をマルチンゲール,$\tau$ を確率 $1$ で有限な停止時刻とする。$\tau$ が有界である,$(M_{t\wedge\tau})$ が一様に有界である,$\mathbb{E}[\tau] < \infty$ かつ増分 $\lvert M_{t+1}-M_t\rvert$ が一様に有界である,のいずれかが成り立てば $\mathbb{E}[M_\tau]=\mathbb{E}[M_0]$ である(Doob の任意停止定理)。参考解2 の $W$ は第2の条件,$M$ は第3の条件(増分は $q^{-2}$ 以下)を満たす。条件を外すと結論は成り立たない。たとえば 0 から出発する対称な単純ランダムウォーク $S_t$ を初めて $1$ に達した時刻で止めると,止めた時刻は確率 $1$ で有限だが $\mathbb{E}[S_\tau]=1\neq0$ である(このとき $\mathbb{E}[\tau]=\infty$)。
参考解2 の $W=z^Hg(D)$ は,状態 $(H,D)$ の連鎖に対する調和関数であり,境界(終了状態)での値から内部の値を決める離散 Dirichlet 問題の解とみなせる。参考解3 は,賭け手全体の純益がマルチンゲールであることに任意停止定理を適用したものにあたる。
定常かつエルゴード的な過程で $\mathbb{P}(B) > 0$ である事象 $B$ について,$B$ が起きた時点から次に $B$ が起きるまでの時間の平均は $\frac{1}{\mathbb{P}(B)}$ である(Kac,1947)。有限既約 Markov 連鎖では,状態 $i$ の平均再帰時間が定常確率の逆数 $\frac{1}{\pi_i}$ になることに対応する。再帰時間と初回到達時間は一般に異なり,本問では $\mathbb{E}[\tau]-\mathbb{E}[L]=\frac1q$ が $\mathrm{TT}$ の重なりの寄与にあたる。
正の整数 $r$ と $0 < x < 1$ について
$$
\frac{1}{(1-x)^r}=\sum_{n=0}^{\infty}\binom{n+r-1}{r-1}x^n
$$
が成り立つ。係数は $r$ 個の非負整数の和が $n$ となる組の個数($r$ 次元の格子点,重複組合せ)であり,$(1-x)^r\binom{n+r-1}{r-1}x^n$ は成功確率 $1-x$ の試行で $r$ 回目の成功までの失敗回数が $n$ である確率(負の二項分布)である。(3) は $r=2$ の場合であり,3.1 節と 3.2 節はそれぞれ組合せ的解釈と確率的解釈に対応する。別解3 で用いた「$k+1$ 個の幾何分布の和」の分布も,この $r=k+1$ の場合である。
成功の連(run)の確率は de Moivre の『The Doctrine of Chances』以来の古典的主題である。Feller の教科書(初版 1950)は,連の問題を再帰事象の理論の典型例として扱った。停止時刻と和の期待値の関係は Wald(1944)に,平均再帰時間の公式は Kac(1947)に,マルチンゲールの理論は Doob(1953)に遡る。パターン当てのゲームは Penney(1969)が提起し,Conway による平均待ち時間の算法が Gardner の紹介(1974)で広まった。その確率論的証明を公平な賭けによって与えたのが Li(1980),相関多項式による母関数の体系を与えたのが Guibas と Odlyzko(1981)である。正規言語と母関数の対応は,Flajolet と Sedgewick の解析的組合せ論(2009)で体系化されている。
$$ \begin{aligned} &a=p(2-p)=1-(1-p)^2,\\ &Q_1=p(1-p)^2(2-p),\qquad Q_2=p^2(1-p)^2(2-p)^2,\\ &Q_n=(1-p)^2\lbrace p(2-p)\rbrace^n\quad(n=0,1,2,\ldots),\\ &\sum_{n=0}^{\infty}(n+1)x^n=\frac{1}{(1-x)^2}\quad(0 < x < 1),\\ &\sum_{n=0}^{\infty}nQ_n=\frac{p(2-p)}{(1-p)^2}=\frac{1}{(1-p)^2}-1. \end{aligned} $$