0

2025年 東京科学大学 理工学系 第3問

0
0
$$$$
2025年 東京科学大学 理工学系 第3問

$0 < p < 1$ とする。表が出る確率が $p$,裏が出る確率が $1-p$ である1枚のコインを使って次のゲームを行う。

  • ゲームの開始段階で点数は0点。
  • コインを投げ続け,表が出るごとに1点加算し,裏が出たときは点数はそのまま。
  • 2回続けて裏が出たらゲームは終了。
    0以上の整数 $n$ に対し,ゲームが終わったときに $n$ 点となっている確率を $Q_n$ とする。
  1. $Q_1$,$Q_2$ を $p$ を用いて表せ。
  2. $Q_n$ を $n$ と $p$ を用いて表せ。
  3. $0 < x < 1$ を満たす実数 $x$ に対して次式が成り立つことを示せ。
    $$ \frac{1}{(1-x)^2}=\sum_{n=0}^{\infty}(n+1)x^n $$
    必要ならば $0 < x < 1$ のとき $\displaystyle\lim_{n\to\infty}nx^n=0$ であることを証明なしで使ってもよい。
  4. 無限級数 $\displaystyle\sum_{n=0}^{\infty}nQ_n$ を $p$ を用いて表せ。

1. 問題の構造

1.1 記法と確率モデル

以下の記号は原題の外で導入する。

  • 表を $\mathrm{H}$,裏を $\mathrm{T}$ と書く。$q=1-p$,$a=p(1+q)=p(2-p)=1-q^2$ とおく。$0 < p < 1$ より $0 < q < 1$,$0 < a < 1$ である。
  • 第 $j$ 投の結果を $C_j$ とする。$C_1,C_2,\ldots$ は独立で $\mathbb{P}(C_j=\mathrm{H})=p$ である。ゲームの終了後も投球を続けると考え,ゲームの経過はこの無限列から定まるものとする(終了後の投球は得点に影響しない)。
  • $\mathrm{H},\mathrm{T}$ からなる有限語 $w$ について,長さを $\lvert w\rvert$,含まれる $\mathrm{H},\mathrm{T}$ の個数を $\lvert w\rvert_{\mathrm{H}},\lvert w\rvert_{\mathrm{T}}$ とし,投球列が $w$ で始まる事象を $[w]$ と書く。$\mathbb{P}([w])=p^{\lvert w\rvert_{\mathrm{H}}}q^{\lvert w\rvert_{\mathrm{T}}}$ であり,2語の一方が他方の接頭辞でなければ $[w]\cap[w']=\varnothing$ である。
  • 終了までの投球回数を $\tau=\min\lbrace m\geqq2 : C_{m-1}=C_m=\mathrm{T}\rbrace$(存在しなければ $\tau=\infty$),第 $m$ 投までの表の個数を $H_m$,終了時の得点を $N=H_\tau$ とする。$Q_n=\mathbb{P}(\tau < \infty,\ N=n)$ である。
  • $n$ 回目の表が出る時刻を $\theta_n$($\theta_0=0$,表が $n$ 回出なければ $\theta_n=\infty$)とし,$n$ 点目を獲得するまでゲームが続く事象を $A_n=\lbrace\theta_n < \tau\rbrace$,$n$ 点で終了する事象を $E_n=\lbrace\tau < \infty,\ N=n\rbrace$ とおく。$A_0$ は全事象,$Q_n=\mathbb{P}(E_n)$ である。
  • 期待値を $\mathbb{E}$,事象 $B$ の指示関数を $\mathbf{1}_B$,第 $t$ 投までの結果で定まる事象の全体を $\mathcal{F}_t$ と書く。$s\wedge t=\min\lbrace s,t\rbrace$ とする。
    本記事で用いる確率の計算は,最初の有限回の結果で定まる事象($[w]$ の有限個または可算個の排反和)と,その単調極限に帰着する。

1.2 再生時点と終了列の一意分解

終了判定に必要な履歴は「直前の投球が $\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])$ と,この排反分解との組み合わせである。

1.3 終了の確実性と Wald 型等式

期待値を扱う解法では,終了の確実性と投球回数の可積分性が必要になる。

終了の確実性と投球回数の可積分性

$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}$)でも起こるので,組ごとの判定でゲームを置き換えることはできない。

Wald 型等式

終了までに出る表の個数 $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.4 観測の単位と分解の選択

同じ投球列を,どの単位で区切って観測するかにより,問題は異なる数学的対象に翻訳される。

観測の単位区切り方現れる構造対応する解法
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 数)である。同じ過程でも,得点という観測量は再生時点と同期しているため低次元化する。これが本解の短さの源である。

1.5 作問の設計

以下は問題文と設定からの分析であり,出題者の意図に関する推定を含む。

  • 隠れた幾何分布:終了条件は履歴に依存するが,得点はちょうど再生ブロックの個数に等しい。したがって得点は「成功確率 $a$ の試行を,初めて失敗するまで繰り返したときの成功回数」と同分布であり,$Q_n=Q_0(1-Q_0)^n$ という1母数の分布になる。問題の核心は,この観測単位を発見させることにある。
  • 終了パターンを $\mathrm{T}$ のみからなる語にした選択:終了パターン $\mathrm{TT}$ が $\mathrm{H}$ を含まないため,$\mathrm{H}$ は途中まで一致したパターンを完全に消去し,正確な再生点になる。$\mathrm{THT}$ のように,表の直後に残る一致の途中経過が履歴によって異なるパターンでは,得点は幾何分布にならない( 4.3 節 )。一方 $\mathrm{TT}$ は自己重複($\mathrm{TTT}$ に $\mathrm{TT}$ が2回現れる)をもつ。この重なりは時刻で観測すると平均待ち時間 $\frac{1+q}{q^2}\neq\frac{1}{q^2}$ に現れるが,得点で観測すると表に出ない。
  • (1) の役割:$Q_1$ は $\mathrm{HTT},\mathrm{THTT}$ の2列,$Q_2$ は $\mathrm{HHTT},\mathrm{HTHTT},\mathrm{THHTT},\mathrm{THTHTT}$ の4列から求まり,$Q_2=p^2q^2(1+2q+q^2)$ に二項係数 $1,2,1$ が現れる。これは (2) へ向けて,再生による $a^n$ と二項定理による $(1+q)^n$ の両方の入口を与える。
  • $n=0$ を含めた定義:$Q_0=q^2=1-a$ は一般式の初期条件であり,同時に分布の正規化 $\sum Q_n=1$ を支える。
  • $0 < p < 1$ の意味:$p=0$ なら常に0点,$p=1$ ならゲームは終わらない。$0 < p < 1$ は終了の確実性と $0 < a < 1$ を同時に保証する。
  • (3) の誘導:「$\lim nx^n=0$ を用いてよい」という付記は,有限部分和の差分をとり剰余項 $(m+2)x^{m+1}$ などを処理する証明を想定したものと読める。範囲を $0 < x < 1$ に限ったのは,(4) で $x=a\in(0,1)$ を代入すれば足りるからである。
  • (4) の形式:求める量は終了時の得点の期待値 $\mathbb{E}[N]$ であるが,期待値の語を用いず無限級数として問うている。高校の課程で扱う期待値が主に有限個の値をとる確率変数のものであることを考慮した形と解される。計算は $1-a=q^2$ により $\frac{q^2a}{(1-a)^2}=\frac{a}{q^2}$ と簡約され,答 $\frac{1}{(1-p)^2}-1=\frac{1}{Q_0}-1$ は再生構造をそのまま映している。

1.6 構造から導かれる解法の分岐

着目する構造導かれる解法
$\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 節

2. 本解:得点更新時点での再生

2.1 方針

観測の単位を「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$ を代入する。

2.2 解答

(1),(2)

$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$ である。

(3)

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

(4)

  1. より $nQ_n=q^2na^n$ であり,$0 < a < 1$ だから (3) において $x=a$ とできる。$n=0$ の項は $0$ であるから
    $$ \sum_{n=0}^{\infty}nQ_n=q^2a\sum_{n=1}^{\infty}na^{n-1}=q^2a\sum_{k=0}^{\infty}(k+1)a^k=\frac{q^2a}{(1-a)^2}=\frac{a}{q^2}. $$
    最後に $1-a=q^2$ を用いた。ゆえに
    $$ \sum_{n=0}^{\infty}nQ_n=\frac{p(2-p)}{(1-p)^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} } $$

2.3 検証・検算

  • 直接列挙:$n=0$ の終了列は $\mathrm{TT}$ のみで $Q_0=q^2$。$n=1$ は $\mathrm{HTT},\mathrm{THTT}$ で $Q_1=pq^2+pq^3=pq^2(1+q)$。$n=2$ は $\mathrm{HHTT},\mathrm{HTHTT},\mathrm{THHTT},\mathrm{THTHTT}$ で $Q_2=p^2q^2(1+2q+q^2)=p^2q^2(1+q)^2$。いずれも一般式に一致する。
  • 総和:$\sum_{n\geqq0}Q_n=\frac{q^2}{1-a}=1$。 1.2 節 の等式 $\sum_{n < M}Q_n+\mathbb{P}(A_M)=1$ と $\mathbb{P}(A_M)=a^M\to0$ より,ゲームが確率 $1$ で終了することも従う。
  • 次数と零点:$Q_n=(1-p)^2p^n(2-p)^n$ は $p$ の $2n+2$ 次式で,$p=0$ に $n$ 位,$p=1$ に $2$ 位の零点をもつ。$n$ 点で終わるには表が $n$ 回,裏が少なくとも $2$ 回必要であることと整合する。
  • 特殊値:$p=\frac12$ では $a=\frac34$,$Q_n=\frac14\left(\frac34\right)^n$,$\sum nQ_n=3$。$p=\frac13$ では $\sum nQ_n=\frac{5/9}{4/9}=\frac54$。
  • 極限:$p\to+0$ で $\sum nQ_n\sim2p\to0$,$p\to1-0$ で $\sum nQ_n\sim(1-p)^{-2}\to\infty$。表がほとんど出ない場合と裏の連続がまれな場合の直観に合う。
  • 構造的な形:$Q_n=Q_0(1-Q_0)^n$,$\sum nQ_n=\frac{1}{Q_0}-1$。分布は $0$ 点終了の確率だけで決まる。
  • 別経路:(3) を用いない計算( 3.4 節 ),投球回数経由の計算 $\mathbb{E}[\tau]=\frac{1+q}{q^2}$,$\mathbb{E}[N]=p\,\mathbb{E}[\tau]$( 別解4 )が同じ値を与える。

3. 別解と参考解

解法は,最初に構成する数学的対象と証明原理によって区別する。同じ対象の記号・図式・計算順序の違いは 3.14 節 にまとめ,独立の解法として数えない。3.1〜3.3 節は (3) の別証,3.4 節は (4) の他の導出である。

3.1 (3) の別証1:等比級数の積と格子点

着想・方針

$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 節 )。

3.2 (3) の別証2:別の確率実験による正規化

着想・方針

$(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$ である。

3.3 (3) の別証3:有限等比和の微分

着想・方針

$(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$ に収束することは示されない(剰余項の評価が別に要る)。

3.4 (4) の他の導出:到達確率の和と自己再生方程式

着想・方針

$\sum nQ_n$ は分布を重み $n$ で「縦に」足したものである。$n=\sum_{k=1}^{n}1$ と分解して「横に」足し直すと,到達確率 $\mathbb{P}(A_k)=a^k$ の和になる。本解ですでに $\mathbb{P}(A_k)$ が得られているので,(3) を経由せずに済む。

解答

(a) 部分和の変形

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

(b) 自己再生方程式

$\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$ である,という再生構造の期待値版である。

(c) 確率母関数(大学の範囲)

$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)$ を形式的に満たすので結論が出ない。

3.5 別解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 で独立に求める値と一致する。

3.6 別解2:2状態の連立漸化式

着想・方針

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$ 個になる。

3.7 別解3:裏で終わる連の独立性と幾何分布のランダム和

着想・方針

表ではなく裏を区切りにする。投球列を「表が $g$ 個続いた後に裏が1個」という連 $\mathrm{H}^g\mathrm{T}$ に区切ると,各連の表の個数は独立同分布の幾何分布に従う。ゲームは,表を含まない連(直前の裏に続く裏)が初めて現れたときに終わる。得点を,幾何分布に従う確率変数のランダムな個数の和として表す。

解答

(1),(2)

$\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. $$

(4)
  1. で $x=p$ として $\mathbb{E}[K]=\mathbb{E}[G'_i]=\sum_{g\geqq0}gp^gq=\frac{p}{q}$ であり,$\mathbb{E}[N\mid K=k]=k+(k+1)\frac{p}{q}$ だから
    $$ \mathbb{E}[N]=\mathbb{E}[K]\left(1+\frac{p}{q}\right)+\frac{p}{q}=\frac{p}{q}\cdot\frac{1}{q}+\frac{p}{q}=\frac{p(1+q)}{q^2}=\frac{p(2-p)}{(1-p)^2}. $$

検証・検算

$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$ で条件付けてから幾何分布の和を数える。

3.8 別解4:終了までの投球回数と Wald 型等式

着想・方針

得点の分布を経由しない。まず終了までの投球回数 $\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}$ 以下である。

3.9 別解5:裏の総数と $\mathrm{TH}$ 遷移の経路保存

着想・方針

各終了列で成り立つ個数の恒等式(経路ごとの保存則)から出発する。終了までの裏の総数 $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 )と一致する。

3.10 参考解1:全出現と初回出現の重複補正

着想・方針

終了後も投げ続けた無限列で,$\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 節 )。

3.11 参考解2:確率的保存量(マルチンゲール)

着想・方針

分布の方程式を先に立てず,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}$ はこれらを満たす閉じた形である。

解答

(1),(2)

$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$ を得る。

(4)

期待値だけなら $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}$ を与える。

3.12 参考解3:公平な賭けによる平均待ち時間

着想・方針

各投球の直前に賭け手が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$ を前提とせず,その値まで与える。

3.13 参考解4:長期出現頻度と平均再帰時間

着想・方針

個々のゲームではなく無限の投球列を定常過程とみる。$\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.14 同じ系列に属する変形

以下は独立の解法とは数えず,既出の解法の表現違い,図式化,部分的な短縮として扱う。

  • 再生(本解)の系列
    • $Q_n=Q_0(1-Q_0)^n$:$Q_0=q^2$ だけを求め,$\mathbb{P}(A_1)=1-Q_0$ を再生で繰り返す。
    • 最初のブロックを取り除く語の全単射 $bw\mathrm{TT}\leftrightarrow(b,\ w\mathrm{TT})$($b\in\mathcal{B}$,$w\in\mathcal{B}^{n-1}$)と $\mathbb{P}([bw\mathrm{TT}])=\mathbb{P}([b])\,\mathbb{P}([w\mathrm{TT}])$ による $Q_n=aQ_{n-1}$。
    • 確率木,自己相似な無限木,「1点ごとに成功確率 $a$ の新しいコインを投げる」という読み替え,正方形の再帰分割:本解の図式化。
    • 2状態の期待得点方程式 $\mu_0=p(1+\mu_0)+q\mu_1$,$\mu_1=p(1+\mu_0)$ から $\mu_0=a(1+\mu_0)$ を得る計算,1サイクルを単位とする Wald の等式(サイクル数は幾何分布): 3.4 節 (b) と同値。
    • ヒストグラムの「横切り」による期待値の図形的解釈: 3.4 節 (a)。
  • 一意分解(別解1)の系列:タイル張り,正規表現 $(\mathrm{H}\mid\mathrm{TH})^{\ast}\mathrm{TT}$,接頭符号 $\lbrace\mathrm{H},\mathrm{TH},\mathrm{TT}\rbrace$ による記述,条件付き二項分布 $K\mid(N=n)$。
  • 状態遷移(別解2)の系列:2状態の確率母関数,推移行列と基本行列( 5.3 節 ),投球回数を添字とする2変数の漸化式(本問では煩雑になるだけで新しい情報を生まない)。
  • 停止時刻(別解4)の系列:マルチンゲール $\sum_{j\leqq t\wedge\tau}(I_j-p)$ を止める表示,2状態の期待投球回数方程式 $e_0=1+pe_0+qe_1$,$e_1=1+pe_0$(解は $e_0=\frac{1+q}{q^2}$)。
  • (3) の系列:部分和公式 $(1-x)^2s_m=1-(m+2)x^{m+1}+(m+1)x^{m+2}$ を帰納法で確かめる方法(本解 (3) の検証形),Maclaurin 展開・負の二項展開・項別積分(3.3 節),「最初の成功までの試行回数の期待値は $\frac{1}{1-x}$」を用いる確率的証明(3.2 節。ただしこの期待値を (3) から引用すると循環論法になる),階段図・2箱への分配(3.1 節)。
    次のものは採用しない。
  • 2投ずつ固定した組で $\mathrm{TT}$ を判定する方法:組の境界をまたぐ $\mathrm{TT}$ を見落とす。 補題2 の上界評価にのみ使える。
  • 「表の割合が $p$ だから $\mathbb{E}[N]=p\,\mathbb{E}[\tau]$」とだけ述べる議論:$\tau$ が投球結果に依存するので論証として不完全である( 補題3 が必要)。
  • $\mathbb{E}[\tau]=\frac{1}{q^2}$ とする議論:定常出現間隔と初回待ち時間の混同である( 参考解4 )。
  • 差分 $Q_{n+1}-Q_n$ を用いた整理:等比型の漸化式の言い換えにすぎない。

3.15 解法の比較

解法主に利用する構造対象範囲長所注意点
本解得点時点での再生全設問高校最短で,問題の本質を表す排反分解と独立性の明示
3.1 格子点等比級数の積(3)高校係数の意味が明瞭,付記の極限が不要無限和の並べ替えを避ける
3.2 確率実験負の二項分布の正規化(3)高校剰余項に確率的意味を与える原題のコインと混同しない
3.3 微分有限等比和の微分(3)高校機械的に計算できる項別微分と混同しない
3.4 到達確率裾確率の和,自己再生(4)高校(3) を経由しない期待値の有限性の確認
別解1接頭符号分解(1)(2)高校直接の数え上げで検証が容易裏の挿入位置
別解22状態遷移(1)(2)高校一般のパターンへ拡張できる添字と $n=0$ の扱い
別解3連の独立性,ランダム和(1)(2)(4)高校〜大学同時分布と条件付き構造が見える継続の表の二重計上
別解4停止時刻,Wald 型等式(4)高校〜大学分布を経由しない可積分性と独立性の根拠
別解5経路保存則(4)高校〜大学個数の恒等式から出発する条件付き二項分布と誤認しない
参考解1全出現と初回出現(1)(2)大学一般のパターンへ拡張できる重なりの項 $qF$
参考解2マルチンゲール(1)(2)(4)大学保存量から一挙に求まる停止時刻での可積分性
参考解3公平な賭け(4)大学自己重複が賞金として見えるWald 型等式との併用
参考解4Kac の再帰定理(4)大学$\mathbb{E}[N]=\mathbb{E}[L]-1$ が直接出る再帰時間と初回待ち時間の区別

試験場での第一選択は,本解(再生)と (3) の差分法である。発想の飛躍がなく,(1) から (4) までが同じ量 $a$ の上に一貫して構成され,各段階に検算点がある。別解1 は組合せ的な構造認識,別解2 は状態遷移という汎用技法を代表し,誘導のない類題ではこちらが主役になりうる。別解3〜5 は分布全体を経由せずに確率変数の分解や個数の恒等式から期待値に至る道を示す。参考解は試験の答案には過剰であるが,$\mathrm{TT}$ の自己重複という,得点で観測すると隠れる構造を,母関数・保存量・賭け・定常頻度という四つの異なる理論から説明する。


4. 汎用的な探索手順

本問から抽出される,「独立試行を,あるパターンが現れるまで続け,途中で生じる量を数える」型の問題に対する探索手順を述べる。

4.1 意思決定の流れ

  1. 求める量と時間を分離する。求める量(本問では表の個数)が時間そのものでなければ,すべての時刻を追う必要があるかをまず問う。
  2. 再生時点を探す。どの出来事で終了判定に必要な履歴が初期化されるか,初期化後の将来が過去と独立であることを排反分解と独立性で示せるか,1サイクルで起こり得る結果とその確率は何か,の3点を確かめる。求める量が再生ごとに一定量ずつ増えるなら,到達確率 $\mathbb{P}(N\geqq n)=a^n$ と幾何分布に帰着する。
  3. 再生がなければ,終了判定に必要な最小限の履歴を状態にする。パターンの初出問題では「直近の投球列の接尾辞に一致するパターンの接頭辞のうち最長のもの」が状態であり,状態数はパターンの長さで足りる。連立漸化式,母関数,推移行列で処理する。
  4. 終了条件を語の制約に翻訳する。最後に必ず現れるパターン,それ以前に禁止されるパターン,自由に反復できるブロックを分離し,接頭符号による一意分解を得る。数え上げ,二項定理,有理型の母関数につながる。
  5. 分布の前に到達確率を調べる。$\mathbb{P}(N=n)$ が難しくても $\mathbb{P}(N\geqq n)$ が簡単なら,差で分布を,和で期待値を得る。
  6. 期待値だけが必要なら分布を経由しない。自己再生方程式,停止時刻と Wald 型等式,経路ごとの保存則,保存量を検討する。停止時刻で期待値をとるときは,有界性または $\mathbb{E}[\tau] < \infty$ を確認し,「平均して割合 $p$」といった直観を独立性の論証で置き換える。
  7. 級数は係数の生成原理を読む。係数 $n+1$ には差分,格子点,確率分布,微分の四つの入口がある。無限和の操作は,有限部分和の等式と極限に置き換えて正当化する。
  8. 検算する。$\sum Q_n=1$,$Q_0$ の直接計算,小さな $n$ の列挙,$p$ の多項式としての次数と零点,$p\to0$,$p\to1$ の極限,別ルートによる再計算を行う。

4.2 症状と有効な表現

症状検討する表現・道具本問での例
ある出来事で履歴が完全に消える再生時点,到達確率,幾何分布本解,3.4 節
終了列の形が確定する接頭符号分解,二項定理,正規表現別解1
終了判定に有限の履歴が要る状態遷移,連立漸化式,母関数別解2
別の文字で区切ると独立な塊が現れる連への分解,ランダム和別解3
期待値だけが問われ,停止時刻が絡む更新方程式,Wald 型等式別解4
経路ごとに個数の関係が成り立つ経路保存則別解5
パターンが自分自身と重なる全出現と初回出現,相関多項式参考解1
状態の関数で期待値が保存されるマルチンゲール,調和関数参考解2
パターンの平均待ち時間公平な賭け(Li の方法)参考解3
長期頻度は易しく初回は難しいKac の再帰定理参考解4
係数が $n+1$ や二項係数差分,格子点,負の二項分布,微分(3),3.1〜3.3 節

4.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 からも得られる。


5. 発展事項

5.1 高校数学と一般理論の境界

事項高校数学での扱い一般理論
再出発の議論投球列の場合分けと独立性再生過程,強 Markov 性
2状態の漸化式連立漸化式吸収的 Markov 連鎖,基本行列
終了列の一意分解二項定理による数え上げ接頭符号,正規言語,記号的方法
期待値と級数有限部分和の極限確率母関数,非負項級数の交換(Tonelli)
停止時刻での期待値更新方程式で代替Wald の等式,任意停止定理
パターンの待ち時間状態の場合分けLi の方法,相関多項式
長期的な出現頻度扱わないKac の再帰定理,エルゴード理論
(3) の級数差分,はさみうちべき級数の項別微分,負の二項分布

本解,3.1〜3.4 節(3.4 節 (c) を除く),別解1〜2 は左欄の範囲で完結する。別解3〜5 は高校数学の言葉で書けるが,条件付き分布や停止時刻の独立性の扱いに大学の確率論の視点を要する。参考解1〜4 は右欄の理論の具体例である。

5.2 再生と幾何分布

非負整数値の確率変数 $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 は,接頭辞の事象への分解によってこの性質を本問の範囲で初等的に示したものである。

5.3 吸収的 Markov 連鎖と基本行列

一時的な状態 $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であることが幾何分布の代数的な表れである。

5.4 正規言語,照合オートマトン,二変数母関数

終了列の全体は曖昧さのない正規表現 $(\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 節 )。

5.5 パターンの自己相関

長さ $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 のゲームの非推移性の原因でもある。

5.6 マルチンゲールと任意停止定理

$(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 は,賭け手全体の純益がマルチンゲールであることに任意停止定理を適用したものにあたる。

5.7 Kac の再帰定理

定常かつエルゴード的な過程で $\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}$ の重なりの寄与にあたる。

5.8 負の二項分布と級数恒等式

正の整数 $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$ の場合である。

5.9 歴史的背景

成功の連(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)で体系化されている。


6. 最終整理

6.1 全体の構造マップ

  • 終了条件 $\mathrm{TT}$,得点は表の個数
    • 観測の単位を選ぶ( 1.4 節 )
      • 1点 → 再生,$\mathbb{P}(A_n)=a^n$ → 本解
      • 終了列 → $\mathcal{B}^n\mathrm{TT}$,二項定理 → 別解1
      • 1投 → 2状態 → 連立漸化式(別解2),保存量(参考解2)
      • 裏1個 → 連の独立性,ランダム和 → 別解3
      • 全出現 → 重複補正 → 参考解1
    • 結論 $Q_n=q^2a^n=(1-p)^2\lbrace p(2-p)\rbrace^n$
  • 級数 (3)
    • 差分(本解),格子点(3.1 節),確率実験(3.2 節),微分(3.3 節)
  • 期待値 (4)
    • 分布から → (3) に $x=a$(本解),到達確率の和・自己再生(3.4 節)
    • 時刻で観測 → $\mathbb{E}[N]=p\,\mathbb{E}[\tau]$ → 更新方程式(別解4),経路保存(別解5)
    • 自己重複から $\mathbb{E}[\tau]$ → 公平な賭け(参考解3),定常頻度(参考解4)
    • 保存量 $q^{-D}-H$ → 参考解2
    • 結論 $\sum nQ_n=\frac{a}{q^2}=\frac{p(2-p)}{(1-p)^2}$

6.2 解答一覧

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

6.3 数学的教訓

  • 時間の進行をそのまま追う必要はない。求める量が更新される時点だけを観測すると,履歴に依存する過程が独立な反復試行に変わることがある。
  • 再生の主張は,接頭辞の事象への排反分解と独立性による積の公式として証明できる。「やり直しになる」という直観をこの形に落とせば論証は完全になる。
  • 同じ過程でも観測量の選択で複雑さが変わる。本問の得点は1階の漸化式(幾何分布)に,投球回数は2階の漸化式(Fibonacci 型)に従う。
  • 終了条件は語の制約に翻訳できる。接頭符号による一意分解は,組合せ的な数え上げと確率論的な再生を同じ構造の二つの読み方として結び付ける。
  • 期待値だけなら分布は要らない。到達確率の和,自己再生方程式,Wald 型等式,経路保存則,保存量のどれもが短い経路を与える。ただし停止時刻で期待値をとる際の可積分性と独立性は省略できない。
  • パターンの自己重複は,得点で観測すると隠れ,時刻で観測すると $\mathbb{E}[\tau]=\frac{1}{q^2}+\frac1q$ の第2項として現れる。平均待ち時間をパターンの確率の逆数と取り違えない。
  • 級数の係数には生成原理がある。係数 $n+1$ は差分,格子点,負の二項分布,微分のいずれからも読め,有限部分和で処理すれば無限操作の正当化を避けられる。
投稿日:11時間前
数学の力で現場を変える アルゴリズムエンジニア募集 - Mathlog served by OptHub

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

投稿者

医学部・難関大受験生の指導を行っています。

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中