$0 < r < 1$ とする。表が出る確率が $r$,裏が出る確率が $1-r$ の硬貨を投げ,表が出た場合は白玉を $2$ つ横並びに置き,裏が出た場合は黒玉を $1$ つ置く。この要領で硬貨を繰り返し投げ,左から右に $1$ 列になるように白玉と黒玉を順に並べていく。
例えば,$3$ 回硬貨を投げ,結果が順に「裏,表,表」であれば,左から順に「黒,白,白,白,白」と $5$ つの玉が並ぶ。
$n$ を自然数とする。$n+2$ 回硬貨を投げたとき,左から $n$,$n+1$,$n+2$ 番目の玉がすべて黒である確率を $p_n$ とする。以下の問いに答えよ。
(1) $p_1$,$p_2$ を求めよ。
(2) $n\geqq 2$ とする。$n+2$ 回硬貨を投げたとき,左から $1$,$n$,$n+1$,$n+2$ 番目の玉がすべて黒である確率を $p_{n-1}$ を用いて表せ。
(3) $n\geqq 3$ のとき,$p_n$ を $p_{n-2}$,$p_{n-1}$ を用いて表せ。
(4) $p_n$ を求めよ。
黒玉は 1 個ずつ置かれるから,黒玉の直前は必ず境界である。これにより目的事象は「境界への到達」と「その後の独立な試行」に分離される。
$n\geqq 1$ とする。$n+2$ 回投げたとき $n,n+1,n+2$ 番目の玉がすべて黒であるという事象は,互いに排反な事象
$$
\lbrace S_k=n-1,\ X_{k+1}=X_{k+2}=X_{k+3}=1\rbrace\qquad(0\leqq k\leqq n-1)
$$
の和に等しい。したがって
$$
p_n=q^3u_{n-1}.
$$
$n+2$ 回投げると玉は $n+2$ 個以上並ぶから,$n,n+1,n+2$ 番目の玉は存在する。
($\supset$)$S_k=n-1$ かつ第 $k+1,k+2,k+3$ 回がすべて裏ならば,$n,n+1,n+2$ 番目の玉はこの 3 回で置かれる黒玉である。$k\leqq S_k=n-1$ より $k+3\leqq n+2$ であるから,これらの回は $n+2$ 回の中にある。
($\subset$)$n$ 番目の玉を置く回を第 $k+1$ 回とすると $S_k < n\leqq S_{k+1}$ である。$n$ 番目の玉が黒であるから $X_{k+1}=1$,よって $S_k=n-1$,$S_{k+1}=n$ である。このとき $n+1$ 番目の玉は第 $k+2$ 回で置かれ,それが黒であるから $X_{k+2}=1$。同様に $X_{k+3}=1$ である。
$(S_k)$ は狭義単調増加であるから $S_k=n-1$ となる $k$ は高々 $1$ つであり,各事象は互いに排反である。事象 $\lbrace S_k=n-1\rbrace$ は $X_1,\ldots,X_k$ で定まり,$X_{k+1},X_{k+2},X_{k+3}$ と独立であるから
$$
p_n=\sum_{k=0}^{n-1}\mathrm{P}(S_k=n-1)\,q^3=q^3u_{n-1}.
$$
位置 $n$ への依存はすべて $u_{n-1}$ に集約され,黒の連続個数は因子 $q^3$ にのみ現れる。連続個数を $k$ に変えれば因子が $q^k$ に変わるだけである( 5.5 節 )。
$m\geqq 1$ のとき,$K_m$ の余事象は互いに排反な事象 $\lbrace S_k=m-1,\ X_{k+1}=2\rbrace$($0\leqq k\leqq m-1$)の和に等しい。したがって
$$
u_m+ru_{m-1}=1\qquad(m\geqq 1).
$$
$m$ 番目の玉を置く回を第 $k+1$ 回とすると $S_k < m\leqq S_{k+1}$ である。$(S_j)$ の単調性より,$j\leqq k$ では $S_j < m$,$j\geqq k+2$ では $S_j > m$ であるから,$K_m$ が起こることと $S_{k+1}=m$ は同値である。$S_{k+1}\neq m$ となるのは $S_{k+1}\geqq m+1$ のときであり,$S_{k+1}\leqq S_k+2\leqq m+1$ より,これは $S_k=m-1$ かつ $X_{k+1}=2$ のときに限る。逆に $S_k=m-1$,$X_{k+1}=2$ ならば $S_k < m < S_{k+1}$ であり $K_m$ は起こらない。排反性と独立性は
補題2
の証明と同様であり
$$
1-u_m=\sum_{k=0}^{m-1}\mathrm{P}(S_k=m-1)\,r=ru_{m-1}.
$$
境界でない位置は「白タイルの 1 個目の直後」の 1 種類しかない。これは白タイルの長さが $2$ であることによる。各位置の状態は「境界」と「白タイルの内部」の 2 状態で,その遷移は次のとおりである。
| 位置 $m$ の状態 | 位置 $m+1$ が境界 | 位置 $m+1$ が内部 |
|---|---|---|
| 境界(確率 $u_m$) | $q$ | $r$ |
| 白タイルの内部(確率 $1-u_m$) | $1$ | $0$ |
次の玉が黒である条件付き確率は,前者で $q$,後者で $0$ であり($q > 0$),この 2 状態は未来の分布によって区別される。一方,2 状態の確率の和は $1$ であるから,未知量は $u_m$ の 1 個で足りる。 補題3 は,この 1 個の未知量が満たす一次の関係を与える。
最後のタイルで分けると $u_m=qu_{m-1}+ru_{m-2}$($m\geqq 2$)が成り立ち(
3.1 節
),(3) の漸化式も同じ係数をもつ。その特性多項式と,1 回の硬貨投げの母関数 $G(z)=\mathrm{E}[z^{X_1}]=qz+rz^2$ について
$$
\lambda^2-q\lambda-r=(\lambda-1)(\lambda+r),\qquad 1-G(z)=(1-z)(1+rz)
$$
が成り立つ。いずれも $q+r=1$,すなわち $G(1)=1$ による因数分解である。
以下は設問の配置と数値設定からの分析であり,出題者の意図については推定を含む。
| 着目する構造 | 数学的翻訳 | 導かれる解法 |
|---|---|---|
| 先頭のタイルを除くと同じ規則の列が残る | 第 1 回の結果による全確率の分解 | 本解 |
| 末尾のタイルを除く | 境界確率の二階漸化式 | 3.1 節 |
| $q+r=1$ | 階差の等比化,特性根 $1,-r$ | 3.2 節 |
| 境界でない位置は 1 種類 | 補題3 による一次漸化式 | 別解1 |
| 長さを固定した敷き詰め | 白タイル数ごとの二項係数,母関数 | 別解2 |
| 停止位置は $m$ と $m+1$ の 2 通り | 指数型保存量 $(-r)^{-S_k}$ | 参考解1 |
| $q=1+(-r)$ | 符号付き重みと対合による相殺 | 参考解2 |
| 裏で状態をリセット,表で反転 | 指示関数の交代和 | 3.7 節 |
1 番目の玉が黒であることは第 1 回が裏であることと同値である。このとき 2 番目の玉は第 2 回で置かれるから,2 番目の玉が黒であることは第 2 回が裏であることと同値であり,3 番目についても同様である。よって $p_1=q^3$ である。
第 1 回が表ならば 1,2 番目の玉は白であるから,2 番目の玉が黒であるには第 1 回が裏でなければならない。このとき 2,3,4 番目の玉は第 2,3,4 回で 1 個ずつ置かれるから,それらがすべて黒であることは第 2,3,4 回がすべて裏であることと同値である。よって $p_2=q^4$ である。
$$
p_1=(1-r)^3,\qquad p_2=(1-r)^4.
$$
$n\geqq 2$ とする。1 番目の玉が黒であることは $X_1=1$ と同値である。$X_1=1$ のとき,全体の $j$ 番目($j\geqq 2$)の玉は,第 2 回から第 $n+2$ 回までの $n+1$ 回で同じ規則により作られる列の $j-1$ 番目の玉である。よって求める事象は
「$X_1=1$」かつ「第 2 回以降の $n+1$ 回で作られる列の $n-1,n,n+1$ 番目がすべて黒」
である。$X_2,\ldots,X_{n+2}$ は $X_1$ と独立で,$X_1,\ldots,X_{n+1}$ と同じ分布をもつから,後者の確率は $p_{n-1}$ の定義($(n-1)+2=n+1$ 回)そのものである。したがって求める確率は
$$
(1-r)\,p_{n-1}.
$$
$n\geqq 3$ とし,第 1 回の結果で分ける。
$q=1-r$ より (3) は
$$
p_n+rp_{n-1}=p_{n-1}+rp_{n-2}\qquad(n\geqq 3)
$$
と書ける。よって $p_n+rp_{n-1}$ は $n\geqq 2$ で一定であり,(1) より
$$
p_n+rp_{n-1}=p_2+rp_1=q^4+rq^3=q^3(q+r)=q^3\qquad(n\geqq 2).
$$
すなわち $p_n=q^3-rp_{n-1}$($n\geqq 2$)である。これと $p_1=q^3$ から,$n$ に関する帰納法により
$$
p_n=q^3\sum_{j=0}^{n-1}(-r)^j\qquad(n\geqq 1)
$$
が成り立つ($n-1$ で成り立てば $p_n=q^3-rq^3\sum_{j=0}^{n-2}(-r)^j=q^3\sum_{j=0}^{n-1}(-r)^j$)。$-r\neq 1$ であるから
$$
\boxed{\,p_n=\frac{(1-r)^3}{1+r}\left\lbrace 1-(-r)^n\right\rbrace\quad(n\geqq 1)\,}
$$
補題2 で $p_n$ を境界確率 $u_{n-1}$ に帰着させたうえで,境界 $m$ に到達する最後のタイルが黒か白かで分ける。本解の「最初のタイル」による分解の鏡像である。
$m\geqq 2$ とする。$K_m$ は互いに排反な事象 $\lbrace S_k=m\rbrace$($1\leqq k\leqq m$)の和であり,各 $k\geqq 1$ について
$$
\lbrace S_k=m\rbrace=\lbrace S_{k-1}=m-1,\ X_k=1\rbrace\cup\lbrace S_{k-1}=m-2,\ X_k=2\rbrace
$$
(右辺は排反)が成り立つ。$\lbrace S_{k-1}=s\rbrace$ は $X_1,\ldots,X_{k-1}$ で定まり $X_k$ と独立であるから,$k$ について和をとって
$$
u_m=q\sum_{k=1}^{m}\mathrm{P}(S_{k-1}=m-1)+r\sum_{k=1}^{m}\mathrm{P}(S_{k-1}=m-2)=qu_{m-1}+ru_{m-2}\qquad(m\geqq 2).
$$
($\mathrm{P}(S_{m-1}=m-2)=0$ であるから第 2 の和は $u_{m-2}$ に等しい。)$n\geqq 3$ のとき $m=n-1\geqq 2$ として
補題2
を用いると
$$
p_n=q^3u_{n-1}=q\cdot q^3u_{n-2}+r\cdot q^3u_{n-3}=(1-r)p_{n-1}+rp_{n-2}.
$$
$\lambda^2=q\lambda+r$ の解は相異なる $1,-r$ である。任意の定数 $\alpha,\beta$ に対して数列 $\alpha+\beta(-r)^n$ は (3) を満たすから,$n=1,2$ で $p_n$ に一致するように $\alpha,\beta$ を定めれば,(3) により全項が一致する。
$$
\alpha-r\beta=q^3,\qquad \alpha+r^2\beta=q^4
$$
より $r(1+r)\beta=q^4-q^3=-rq^3$,すなわち $\beta=-\dfrac{q^3}{1+r}$,$\alpha=q^3+r\beta=\dfrac{q^3}{1+r}$ である。
補題3 により,二階漸化式を経由せず,確率の分割から一次漸化式 $u_m=1-ru_{m-1}$ が直接得られる。これと 補題2 を組み合わせて全設問を処理する。
$u_0=1$,$u_1=1-ru_0=q$ であるから, 補題2 より $p_1=q^3u_0=q^3$,$p_2=q^3u_1=q^4$ である。
本解と同じく,第 1 回が裏の場合に先頭の黒玉を除いて $(1-r)p_{n-1}$ を得る。
$n\geqq 2$ のとき,
補題2
と
補題3
より
$$
p_n+rp_{n-1}=q^3(u_{n-1}+ru_{n-2})=q^3.
$$
$n\geqq 3$ ならば,この式と $n$ を $n-1$ に置き換えた式の差をとり,$p_n-p_{n-1}+r(p_{n-1}-p_{n-2})=0$,すなわち $p_n=(1-r)p_{n-1}+rp_{n-2}$ である。
$c=\frac{1}{1+r}$ は $c=1-rc$ を満たすから,
補題3
との差をとって $u_m-c=-r(u_{m-1}-c)$($m\geqq 1$)。$u_0=1$ より
$$
u_m=c+(1-c)(-r)^m=\frac{1}{1+r}+\frac{r}{1+r}(-r)^m=\frac{1-(-r)^{m+1}}{1+r}\qquad(m\geqq 0).
$$
補題2
より
$$
p_n=q^3u_{n-1}=\frac{(1-r)^3}{1+r}\lbrace 1-(-r)^n\rbrace.
$$
長さ $m$ の区間をちょうど敷き詰めるタイル列を白タイルの個数で分類して数え,$u_m$ を有限和で表す。漸化式は Pascal 則から,閉じた形はタイル列全体の母関数から得る。
白タイル $j$ 個で長さ $m$ に達するタイル列は,黒タイル $m-2j$ 個と合わせて $m-j$ 個のタイルからなる。白タイルの位置の選び方は $\binom{m-j}{j}$ 通りであり,各タイル列が最初の $m-j$ 回に現れる確率は $r^jq^{m-2j}$ である。$K_m$ はこれらの排反な事象の和であるから
$$
u_m=\sum_{j=0}^{\lfloor m/2\rfloor}\binom{m-j}{j}r^jq^{m-2j},\qquad
p_n=q^3\sum_{j=0}^{\lfloor (n-1)/2\rfloor}\binom{n-1-j}{j}r^jq^{n-1-2j}.
$$
$u_0=1$,$u_1=q$ より $p_1=q^3$,$p_2=q^4$。(2) は先頭が黒タイルである列を分離して $(1-r)p_{n-1}$ を得る。
$m\geqq 2$ のとき,Pascal 則 $\binom{m-j}{j}=\binom{m-1-j}{j}+\binom{m-1-j}{j-1}$(範囲外の二項係数は $0$)を用いると
$$
u_m=q\sum_{j}\binom{m-1-j}{j}r^jq^{m-1-2j}+r\sum_{j}\binom{(m-2)-(j-1)}{j-1}r^{j-1}q^{(m-2)-2(j-1)}=qu_{m-1}+ru_{m-2}.
$$
Pascal 則の 2 項は,最後のタイルが黒である列と白である列に対応する(
3.1 節
)。
補題2
より $p_n=(1-r)p_{n-1}+rp_{n-2}$($n\geqq 3$)。
$U(z)=\sum_{m\geqq 0}u_mz^m$ を形式的べき級数とし,$G(z)=qz+rz^2$ とおく。$X_1,\ldots,X_k$ の独立性より $G(z)^k=\mathrm{E}[z^{S_k}]=\sum_{m}\mathrm{P}(S_k=m)z^m$ である。$G(z)$ の定数項は $0$ であるから $G(z)^k$ は $z^k$ 以上の項のみからなり,$\sum_{k\geqq 0}G(z)^k$ の各係数は有限和として定まる。よって
$$
U(z)=\sum_{m\geqq 0}\sum_{k=0}^{m}\mathrm{P}(S_k=m)z^m=\sum_{k\geqq 0}G(z)^k=\frac{1}{1-G(z)}=\frac{1}{(1-z)(1+rz)}.
$$
部分分数分解
$$
\frac{1}{(1-z)(1+rz)}=\frac{1}{1+r}\cdot\frac{1}{1-z}+\frac{r}{1+r}\cdot\frac{1}{1+rz}
$$
と $\frac{1}{1-z}=\sum_{m\geqq 0}z^m$,$\frac{1}{1+rz}=\sum_{m\geqq 0}(-r)^mz^m$ から
$$
u_m=\frac{1}{1+r}+\frac{r}{1+r}(-r)^m=\frac{1-(-r)^{m+1}}{1+r},\qquad
p_n=\frac{(1-r)^3}{1+r}\lbrace 1-(-r)^n\rbrace.
$$
なお $G(z)^k=z^k(q+rz)^k$ の $z^m$ の係数は $\binom{k}{m-k}r^{m-k}q^{2k-m}$ であり,$j=m-k$ とおけば有限和表示の第 $j$ 項に一致する。母関数は有限和の生成規則を一括して表したものである。
$S_k$ を,$1$ または $2$ ずつ進む歩行とみる。初めて $m$ 以上になったときの位置は $m$ か $m+1$ の 2 通りしかない。この 2 つに異なる値を与え,かつ 1 歩ごとに平均が変わらない関数 $F$ を作れば,$u_m$ は漸化式を経由せずに決まる。$F(s)=t^{-s}$ の形で平均不変の条件 $qF(s+1)+rF(s+2)=F(s)$ を課すと $t^2-qt-r=0$ となり,自明でない根 $t=-r$ を採る。(1)〜(3) は本解のとおりとし,(4) を示す。
$m\geqq 1$ を固定し,$T=\min\lbrace k\geqq 0 : S_k\geqq m\rbrace$ とする。$S_m\geqq m$ より $1\leqq T\leqq m$ であり,$S_{T-1}\leqq m-1$,$X_T\leqq 2$ より $S_T\in\lbrace m,m+1\rbrace$ である。$(S_k)$ の単調性より $K_m=\lbrace S_T=m\rbrace$,よって $u_m=\mathrm{P}(S_T=m)$ である。
$0\leqq s\leqq m+1$ に対し $F(s)=(-r)^{m+1-s}$ と定める。$0\leqq s\leqq m-1$ のとき
$$
qF(s+1)+rF(s+2)=(-r)^{m-1-s}\lbrace q(-r)+r\rbrace=(-r)^{m-1-s}\,r^2=F(s).
$$
$Y_k=S_{\min(k,T)}$($k\geqq 0$)とおく。事象 $\lbrace T\leqq k\rbrace$ は $X_1,\ldots,X_k$ で定まる。$X_1,\ldots,X_k$ の値を固定して $X_{k+1}$ についての平均をとると,
黒タイルの確率 $q$ を形式的に $1+(-r)$ と分け,黒タイルを重み $1$ のものと重み $-r$ のものの 2 種に分ける。すると長さ $2$ の部分として,白タイル(重み $r$)と「重み $1$ の黒,重み $-r$ の黒」の並び(重み $-r$)が逆符号で現れる。これらを対にして打ち消すと,別解2の二項係数の和が有限等比和に縮約される。配置を数えて加えるのではなく,打ち消す対応を構成する点で別解2と証明原理が異なる。(1)〜(3) は本解のとおりとし,(4) を示す。
長さ $1$ のタイル $\mathsf{A}$(重み $1$),$\mathsf{C}$(重み $-r$)と長さ $2$ のタイル $\mathsf{D}$(重み $r$)を考える。$\mathsf{A},\mathsf{C},\mathsf{D}$ を並べた有限列(語)について,長さをタイルの長さの和,重み $\mathrm{wt}$ を各タイルの重みの積で定め,長さ $m$ の語全体を $\mathcal{W}_m$ とする。負の重みは確率ではなく計数のための形式的な値である。
黒タイル $i$ 個,白タイル $j$ 個からなる長さ $m$ のタイル列の確率は $q^ir^j$ である。各黒タイルを $\mathsf{A}$ または $\mathsf{C}$ に,各白タイルを $\mathsf{D}$ に置き換えて得られる $2^i$ 個の語の重みの和は $(1-r)^ir^j=q^ir^j$ であり,$\mathcal{W}_m$ の各語はちょうど 1 つのタイル列から生じる。よって
$$
u_m=\sum_{\omega\in\mathcal{W}_m}\mathrm{wt}(\omega).
$$
$\omega\in\mathcal{W}_m$ を左から見て,最初に現れる「$\mathsf{D}$ または連続する $\mathsf{A}\mathsf{C}$」を $\mathsf{D}\leftrightarrow\mathsf{A}\mathsf{C}$ と置き換えた語を $\varphi(\omega)$ とする(いずれも現れなければ $\varphi(\omega)=\omega$)。このとき $\varphi$ は $\mathcal{W}_m$ 上の対合($\varphi\circ\varphi=\mathrm{id}$)であり,$\varphi(\omega)\neq\omega$ ならば $\mathrm{wt}(\varphi(\omega))=-\mathrm{wt}(\omega)$ である。不動点は $\mathsf{C}^j\mathsf{A}^{m-j}$($0\leqq j\leqq m$)に限る。
置き換えは長さ $2$ の部分どうしで行われるから長さを保ち,$\mathrm{wt}(\mathsf{D})=r$,$\mathrm{wt}(\mathsf{A}\mathsf{C})=-r$ より重みの符号だけを反転する。
$\varphi(\omega)\neq\omega$ のとき $\omega=\omega'\sigma\omega''$($\sigma$ は置き換える部分)と書く。$\sigma$ が最初の出現であるから,$\omega'$ は $\mathsf{D}$ も $\mathsf{A}\mathsf{C}$ も含まない。$\varphi(\omega)=\omega'\sigma'\omega''$ において $\sigma'$ の先頭の文字は $\mathsf{A}$ または $\mathsf{D}$ であって $\mathsf{C}$ ではないから,$\omega'$ の末尾と $\sigma'$ の先頭が新たに $\mathsf{A}\mathsf{C}$ をなすことはない。よって $\varphi(\omega)$ で最初に現れる対象部分は $\sigma'$ であり,$\varphi(\varphi(\omega))=\omega'\sigma\omega''=\omega$ である。
不動点は $\mathsf{D}$ も $\mathsf{A}\mathsf{C}$ も含まない語,すなわち $\mathsf{A},\mathsf{C}$ のみからなり $\mathsf{A}$ の直後に $\mathsf{C}$ が来ない語である。このような語ではすべての $\mathsf{C}$ がすべての $\mathsf{A}$ より左にあるから $\mathsf{C}^j\mathsf{A}^{m-j}$ の形であり,逆にこの形の語は不動点である。
補題4
により,不動点でない語は重みが逆符号の 2 つずつの組に分かれ,その重みの和は $0$ である。したがって
$$
u_m=\sum_{j=0}^{m}\mathrm{wt}(\mathsf{C}^j\mathsf{A}^{m-j})=\sum_{j=0}^{m}(-r)^j=\frac{1-(-r)^{m+1}}{1+r},
$$
補題2
より $p_n=\dfrac{(1-r)^3}{1+r}\lbrace 1-(-r)^n\rbrace$ である。
以下は上記のいずれかと発想の核を共有するため,独立の解法として扱わない。
独立な確率変数 $H_0,H_1,H_2,\ldots$($\mathrm{P}(H_i=1)=r$,$\mathrm{P}(H_i=0)=q$)を用いて $B_0=1$,$B_{i+1}=1-H_iB_i$ と定める。このとき $(B_0,B_1,\ldots)$ は境界の指示関数の列 $(\mathbf{1}_{K_0},\mathbf{1}_{K_1},\ldots)$ と同じ分布をもち,
$$
B_m=\sum_{k=0}^{m}(-1)^k\,\mathbf{1}_{\lbrace H_{m-1}=\cdots=H_{m-k}=1\rbrace},\qquad u_m=\mathrm{E}[B_m]=\sum_{k=0}^{m}(-r)^k.
$$
ただし $k=0$ の項の事象は全事象とする。
$H_i$ は「位置 $i$ が境界であるとき次に投げる硬貨」の結果(表を $1$)を表す。$B_i=1$ のとき,$H_i=0$ なら黒タイルが置かれて $B_{i+1}=1$,$H_i=1$ なら白タイルの内部に入って $B_{i+1}=0$ である。$B_i=0$ のとき位置 $i+1$ は白タイルの終わりであり $B_{i+1}=1$ で,$H_i$ は使われない。いずれも $B_{i+1}=1-H_iB_i$ に一致する。
実際に使われる変数は,境界の位置 $\tau_1=0 < \tau_2 < \cdots$ における $H_{\tau_1},H_{\tau_2},\ldots$ である。$\tau_l=\tau_{l-1}+1+H_{\tau_{l-1}}$ であるから,$H_{\tau_1},\ldots,H_{\tau_{l-1}}$ の値を固定すると $\tau_l$ は定数 $t$ に定まり,固定した事象は位置 $t$ より左の変数で記述される。$H_t$ はそれらと独立であるから,条件付きでも $H_{\tau_l}=1$ の確率は $r$ である。よって $H_{\tau_1},H_{\tau_2},\ldots$ は元の硬貨投げと同じ分布をもち,$(B_i)$ は境界の指示関数の列と同じ分布をもつ。
右端から続く $1$ の個数を $\ell=\max\lbrace k\leqq m : H_{m-1}=\cdots=H_{m-k}=1\rbrace$ とする。$\ell < m$ ならば $H_{m-\ell-1}=0$ より $B_{m-\ell}=1$,$\ell=m$ ならば $B_0=1$ である。その後の $\ell$ 回はいずれも $H=1$ で状態を反転する($B_{i+1}=1-B_i$)から,$B_m=1$ であることと $\ell$ が偶数であることは同値である。右辺の和は $\sum_{k=0}^{\ell}(-1)^k$ に等しく,$\ell$ が偶数なら $1$,奇数なら $0$ である。期待値をとれば,独立性より $\mathrm{P}(H_{m-1}=\cdots=H_{m-k}=1)=r^k$ であるから $u_m=\sum_{k=0}^{m}(-r)^k$ を得る。
状態の分割は別解1と同一であり, 補題5 は 補題3 を標本ごとの等式 $B_{i+1}=1-H_iB_i$ に精密化したものである。「裏は過去の情報を消去し,表は状態を反転する」という構造が交代和の各項に直接現れる( 5.2 節 )。
| 解法 | 分解・固定するもの | 中心となる式 | 利用する構造 | 論証上の要点 |
|---|---|---|---|---|
| 本解 | 第 1 回の結果 | $p_n=qp_{n-1}+rp_{n-2}$ | 先頭タイルの除去,$q+r=1$ | $n\geqq 3$,余分な 1 回 |
| 3.1 節 | 最後のタイル | $u_m=qu_{m-1}+ru_{m-2}$ | 末尾タイルの除去 | 補題2 との合成 |
| 3.2 節 | 階差・特性根 | $p_n-p_{n-1}=q^3(-r)^{n-1}$ | 根 $1,-r$ | 和の添字,$p_0$ の不在 |
| 別解1 | 位置 $m$ の状態 | $u_m+ru_{m-1}=1$ | 二状態,内部の位置が 1 つ | 排反かつ全事象 |
| 別解2 | 白タイルの個数 | $\sum_j\binom{m-j}{j}r^jq^{m-2j}$ | 敷き詰めの計数,母関数 | タイル数 $m-j$,閉じ方 |
| 参考解1 | 停止位置 | $\mathrm{E}[F(S_T)]=F(0)$ | 指数型保存量,$G(-1/r)=1$ | $T\leqq m$,保存の検証 |
| 参考解2 | 符号付きの語 | $\sum_{j=0}^{m}(-r)^j$ | 対合による相殺,$q=1+(-r)$ | 可逆性,不動点の決定 |
試験時間内に解く場合の目安を次に示す(方法の数学的価値の優劣を表すものではない)。
| 評価軸 | 本解 | 別解1 | 別解2 | 参考解1 | 参考解2 |
|---|---|---|---|---|---|
| 誘導との整合 | ◎ | ○ | ○ | △ | △ |
| 計算量 | 少 | 少 | 中 | 中 | 中 |
| 論証量 | 少 | 少 | 中 | 多 | 多 |
| 高校数学の範囲 | 内 | 内 | 有限和まで内 | 内 | 内 |
| 一般化への適用 | 広 | 広 | 広 | 広 | 限定的 |
本解は (2)(3) の誘導が指示する分解をそのまま実行し, 補題2 のような事象の分析を必要としない。この点で試験場での再現性が最も高い。別解1 は二階漸化式を経由せず,論理の長さが最短である。別解2 は配置の全体像を与え,参考解1・2 はそれぞれ停止位置の保存量と符号反転対合という,他の問題に移せる証明原理を示す。
本問から抽出される手順を,位置・長さが確率的に伸びる過程の問題一般に適用できる形で述べる。
(1) 試行の単位と観測の単位を分ける:1 回の試行で観測対象(位置・長さ・得点)がいくつ進むかを書き出し,「何回目の試行か」と「どの位置か」を区別する。本問では 1 回で $1$ または $2$ 進む。
(2) 再生点を探して目的事象を分解する:過程が過去と独立に新しく始まる点(再生点)を探し,目的事象を「再生点への到達」と「その後の独立な局所事象」の積に分ける。本問では黒玉の直前が必ず境界であることがこれを可能にする(
補題2
)。
(3) 未来を決める最小の状態を特定する:未来の分布を決めるのに必要な情報を状態として列挙し,状態の確率の和が $1$ であることを使って未知量を減らす。本問の状態は「境界」「白タイルの内部」の 2 つで,未知量は 1 個である。
(4) 自己相似な分解で漸化式を立てる:先頭または末尾の 1 操作を除いて同じ型の問題に帰着させる。設問がその分解を誘導していればそれに従う。
(5) 係数の和が $1$ なら保存量で階数を下げる:$x_n=\sum_{k=1}^{K}c_kx_{n-k}$,$\sum_kc_k=1$ のとき,$d_j=\sum_{k > j}c_k$ とおくと
$$
\sum_{j=0}^{K-1}d_j\,x_{n-j}\quad(d_0=1)
$$
は $n$ によらない(差をとれば漸化式そのものになる)。$c_k$ が歩幅の分布 $\mathrm{P}(X=k)$ ならば $d_j=\mathrm{P}(X > j)$ であり,この保存則は全確率の分解として直接立式できる(
5.1 節
)。本問では $p_n+rp_{n-1}$ である。
(6) 長さを固定した配置は部品の個数で分類して数える:二項係数の有限和を得たら,閉じた形が必要かを判断し,母関数・漸化式・相殺のいずれかで閉じる。
(7) 停止位置が少数なら保存量で直接決める:歩幅の確率母関数 $G$ について $G(z_0)=1$ を満たす $z_0$ をとれば,$z_0^{S_k}$ は 1 歩ごとに平均が変わらない。停止位置が $L$ 通りなら,自明な根 $z_0=1$ 以外に $L-1$ 個の根を用いる。
(8) 構造に基づいて検算する:初期値,パラメータの極限,偶奇の振る舞い,少数例の全数列挙,有限和と閉じた形の一致を確認する。
兆候と手法の対応を整理する。
| 兆候 | 試す手法 | 本問での実装 |
|---|---|---|
| 1 回の試行で進む量が一定でない | 位置と回数の分離,到達確率の導入 | $u_m$ |
| 目的のパターンが特定の状態から始まる | 再生点による分解 | 補題2 |
| 漸化式の係数の和が $1$ | 保存される一次結合 | $p_n+rp_{n-1}=q^3$ |
| 余事象の状態が 1 種類 | 一次漸化式の直接立式 | 補題3 |
| 部品の個数を固定すると数えやすい | 二項係数,母関数 | 別解2 |
| 停止位置が少数 | 指数型保存量 | 参考解1 |
| 重みが $1$ から引いた形 | 符号付き重みと対合 | 参考解2 |
各節で,高校数学の範囲で完結する内容と,それを超える一般論を区別して記す。
補題3
は,位置 $m$ の直前の最後の境界で分ける全確率の分解であり,排反な事象の確率の和として完結する。
発展 独立同分布な正の整数値の歩幅 $X_i$ の部分和 $S_k$ の値を再生点といい,$u_m=\mathrm{P}(\exists k:\ S_k=m)$ の列を再生列(renewal sequence)という。任意の $m\geqq 0$ に対して $S_k\leqq m < S_{k+1}$ となる $k$ はただ 1 つであるから,最後の再生点 $j=S_k$ で分けて
$$
\sum_{j=0}^{m}u_j\,\mathrm{P}(X_1 > m-j)=1
$$
が成り立つ。本問では $\mathrm{P}(X_1 > 0)=1$,$\mathrm{P}(X_1 > 1)=r$,$\mathrm{P}(X_1 > k)=0$($k\geqq 2$)であるから,これは
補題3
そのものである。裾確率の母関数 $\Phi(z)=\sum_{k\geqq 0}\mathrm{P}(X_1 > k)z^k$ は $\Phi(z)=\dfrac{1-G(z)}{1-z}$ を満たし,上式は
$$
U(z)\,\Phi(z)=\frac{1}{1-z},\qquad \Phi(z)=1+rz
$$
と書ける。$1-G(z)=(1-z)(1+rz)$ の因数 $1-z$ は規格化 $G(1)=1$ に,因数 $1+rz$ は裾確率に由来する。
4 節
(5) の係数 $d_j$ は裾確率 $\mathrm{P}(X > j)$ に等しく,二階漸化式の保存量(本解)と全確率の分解(別解1)が同じ式になる理由はここにある。
歩幅の分布の台の最大公約数が $1$ で平均 $\mu$ が有限ならば $u_m\to\frac{1}{\mu}$ である(Erdős–Feller–Pollard の再生定理)。本問では台 $\lbrace 1,2\rbrace$,$\mu=1+r$ で,$u_m\to\frac{1}{1+r}$ と整合する。再生定理は極限値だけを与え,有限の $m$ での補正 $\frac{r}{1+r}(-r)^m$ は $\Phi(z)$ の零点 $z=-1/r$ によって決まる。
一次漸化式 $u_m=1-ru_{m-1}$ を解けば十分である。
発展 位置 $m$ の状態(境界/白タイルの内部)の分布を列ベクトル $v_m=(u_m,\ 1-u_m)^{\top}$ で表すと
$$
v_{m+1}=Mv_m,\qquad M=\begin{pmatrix}q&1\\ r&0\end{pmatrix}
$$
である(各列の和が $1$)。
$$
\pi=\frac{1}{1+r}\begin{pmatrix}1\\ r\end{pmatrix},\qquad \Pi=\pi\,(1\ \ 1)=\frac{1}{1+r}\begin{pmatrix}1&1\\ r&r\end{pmatrix}
$$
とおくと $\Pi^2=\Pi$,$\Pi(I-\Pi)=(I-\Pi)\Pi=O$ であり
$$
M=\Pi-r(I-\Pi),\qquad M^m=\Pi+(-r)^m(I-\Pi).
$$
$\Pi$ と $I-\Pi$ は互いの積が零行列となる相補的な射影である(ユークリッド内積に関する直交射影ではない)。$v_0=(1,0)^{\top}$ に作用させれば $u_m=\frac{1}{1+r}+\frac{r}{1+r}(-r)^m$ を得る。$\pi$ は定常分布,$-r$ は第 2 固有値であり,定常分布からのずれの減衰を支配する。行ベクトルで分布を表す規約では遷移行列は $M^{\top}$ となる。
結合による固有値 $-r$ の意味
補題5
の表示 $B_{i+1}=1-H_iB_i$ で,初期状態だけが異なる 2 つの過程を同じ $(H_i)$ で動かすと,差 $\Delta_i$ は $\Delta_{i+1}=-H_i\Delta_i$ を満たし
$$
\Delta_m=(-1)^m\Delta_0\prod_{i=0}^{m-1}H_i.
$$
初期状態の差は,$m$ 回すべて $H_i=1$ のとき(確率 $r^m$)に限り,符号が $(-1)^m$ 倍されて残る。初期状態を確率 $\frac{1}{1+r}$ で境界,$\frac{r}{1+r}$ で内部とし $(H_i)$ と独立に選んだ過程 $B^{\star}$ は,$H_i$ が $B^{\star}_i$ と独立であることと $\frac{1}{1+r}=1-r\cdot\frac{1}{1+r}$ より,各位置で境界である確率が $\frac{1}{1+r}$ のまま変わらない。$B_0=1$ の過程との差の期待値をとって
$$
u_m-\frac{1}{1+r}=\mathrm{E}\left[(-1)^m(1-B^{\star}_0)\prod_{i=0}^{m-1}H_i\right]=\frac{r}{1+r}(-r)^m.
$$
すなわち $-r$ は「1 歩後に初期状態の差が残る符号付きの平均倍率」であり,符号は表による状態の反転を,大きさは反転が起こる確率を表す。
参考解1の論証は,有限回の条件付き平均の反復だけで完結する。
発展 歩幅の確率母関数 $G(z)=\mathrm{E}[z^{X_1}]$ について $G(z_0)=1$ となる $z_0$ をとると,$Z_k=z_0^{S_k}$ は $\mathrm{E}[Z_{k+1}\mid X_1,\ldots,X_k]=Z_k\,G(z_0)=Z_k$ を満たすマルチンゲールである。本問では $1-G(z)=(1-z)(1+rz)$ より $z_0=1$(自明)と $z_0=-1/r$ であり,参考解1の $F(S_k)=(-r)^{m+1}(-1/r)^{S_k}$ は後者の定数倍である。参考解1の核心は有界な停止時刻に対する任意抽出定理 $\mathrm{E}[Z_T]=\mathrm{E}[Z_0]$ であり,$T\leqq m$ であるため有限回の反復で証明できた。
別の見方として,位置 $s$ から出発したときに $m$ にちょうど到達する確率 $h(s)$ は,境界値 $h(m)=1$,$h(m+1)=0$ のもとで
$$
h(s)=q\,h(s+1)+r\,h(s+2)\qquad(0\leqq s\leqq m-1)
$$
を満たす(離散調和関数)。この方程式は $h(m),h(m+1)$ から $h$ を一意に定め,$1$ と $(-r)^{-s}$ がともに解であるから,解は $a+b(-r)^{-s}$ の形に限られる。境界値から
$$
h(s)=\frac{1-(-r)^{m+1-s}}{1+r},\qquad h(0)=u_m
$$
を得る。これは,上昇確率 $a$,下降確率 $b$ の $\pm 1$ 歩行に対する賭博者の破産問題で $(b/a)^{S_k}$ を用いる議論と同じ構造である($az+bz^{-1}=1$ の非自明な解が $z=b/a$)。
別解2の有限和と,Pascal 則による漸化式で十分である。
発展 $f_0=1$,$f_1=x$,$f_m=xf_{m-1}+yf_{m-2}$ で定まる多項式は,長さ $1$ のタイルに重み $x$,長さ $2$ のタイルに重み $y$ を与えた長さ $m$ の敷き詰めの重みの総和であり,$t^2-xt-y=0$ の相異なる 2 解を $\alpha,\beta$ とすると
$$
f_m=\sum_{j=0}^{\lfloor m/2\rfloor}\binom{m-j}{j}x^{m-2j}y^j=\frac{\alpha^{m+1}-\beta^{m+1}}{\alpha-\beta}
$$
が成り立つ(Binet 型公式)。
補題2
,
補題3
と同じ議論の繰り返しで示される。
発展 任意の色の並びの出現確率について,位置への依存は本問と同じ形に限られる。
色の有限列 $w=(w_1,\ldots,w_\ell)$ と $m\geqq 1$ に対し,$m,\ldots,m+\ell-1$ 番目の玉の色が順に $w_1,\ldots,w_\ell$ である事象を $\Gamma_m(w)$ とする(十分な回数だけ投げるものとする)。$\varepsilon_w$ を $w_1$ が白なら $1$,黒なら $0$ とし,
$$
a_w=\mathrm{P}(\Gamma_1(w)),\qquad b_w=\varepsilon_w\,\mathrm{P}(\Gamma_1(w_2,\ldots,w_\ell))
$$
とおく($\ell=1$ のときは $b_w=\varepsilon_w$)。このとき
$$
\mathrm{P}(\Gamma_m(w))=b_w+(a_w-b_w)\,u_{m-1}=b_w+\frac{a_w-b_w}{1+r}\lbrace 1-(-r)^m\rbrace.
$$
$m=1$ では $u_0=1$ より両辺は $a_w$ に等しい。$m\geqq 2$ とする。事象 $\lbrace S_k=m-1\rbrace$ のもとでは,$m$ 番目以降の玉は第 $k+1$ 回以降の硬貨で新たに作られ,その列は $\lbrace S_k=m-1\rbrace$ と独立で元の列と同じ分布をもつ。$k$ について和をとって $\mathrm{P}(\Gamma_m(w)\cap K_{m-1})=a_w\,u_{m-1}$。 補題3 より $K_{m-1}$ の余事象は排反な事象 $\lbrace S_k=m-2,\ X_{k+1}=2\rbrace$ の和であり,そのもとで $m$ 番目の玉は白タイルの 2 個目で白,$m+1$ 番目以降は第 $k+2$ 回以降の硬貨で新たに作られる。よって $\mathrm{P}(\Gamma_m(w)\cap K_{m-1}^{c})=b_w\,r\,u_{m-2}=b_w(1-u_{m-1})$。両者を加えればよい。
$$ \begin{array}{c} \text{硬貨 1 回}\ \longrightarrow\ \text{長さ }1\ (\text{確率 }q)\ \text{または長さ }2\ (\text{確率 }r)\ \text{のタイル}\\ \Downarrow\\ \text{黒 3 連}\iff\text{境界 }n-1\ \text{かつ続く 3 回が裏}:\quad p_n=q^3u_{n-1}\\ \Downarrow\\ \begin{array}{c|c|c} \text{先頭・末尾の 1 枚を除く} & \text{境界の補集合} & \text{全配置の計数}\\ \hline p_n=qp_{n-1}+rp_{n-2} & u_m+ru_{m-1}=1 & \sum_j\binom{m-j}{j}r^jq^{m-2j} \end{array}\\ \Downarrow\\ \begin{array}{c|c|c} q+r=1\ \text{による階数下げ} & \text{停止位置の保存量} & \text{母関数・符号反転対合} \end{array}\\ \Downarrow\\ u_m=\dfrac{1}{1+r}+\dfrac{r}{1+r}(-r)^m\quad(\text{定常値}+\text{交代減衰})\\ \Downarrow\\ p_n=\dfrac{(1-r)^3}{1+r}\left\lbrace 1-(-r)^n\right\rbrace \end{array} $$
| 設問 | 答 | 根拠 |
|---|---|---|
| (1) | $p_1=(1-r)^3,\ p_2=(1-r)^4$ | 最初の 3 回,4 回がすべて裏 |
| (2) | $(1-r)\,p_{n-1}$ | 先頭の黒玉の除去 |
| (3) | $p_n=(1-r)p_{n-1}+rp_{n-2}$ | 第 1 回の結果による分解 |
| (4) | $p_n=\dfrac{(1-r)^3}{1+r}\left\lbrace 1-(-r)^n\right\rbrace$ | 保存量 $p_n+rp_{n-1}=(1-r)^3$ |