0

2026年 九州大学 理系 第3問

1
0
$$$$
2026年 九州大学 理系 第3問

$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. 問題の構造

1.1 記法と確率モデル

  • $q=1-r$ とおく。$0 < q < 1$,$q+r=1$ である。
  • 第 $i$ 回の硬貨投げで置かれる玉の個数を $X_i$ とする。$X_i=1$ が裏(黒玉 $1$ 個),$X_i=2$ が表(白玉 $2$ 個)に対応し,$X_1,X_2,\ldots$ は独立で $\mathrm{P}(X_i=1)=q$,$\mathrm{P}(X_i=2)=r$ である。
  • $S_0=0$,$S_k=X_1+\cdots+X_k$ とおく。$S_k$ は $k$ 回投げた後の玉の個数であり,$k\leqq S_k\leqq 2k$,$S_{k+1}-S_k\in\lbrace 1,2\rbrace$ を満たす。とくに $(S_k)$ は狭義単調増加である。第 $k$ 回の硬貨投げは $S_{k-1}+1$ 番目から $S_k$ 番目までの玉を置く。
  • 1 回の硬貨投げで置かれる玉のまとまりをタイルと呼ぶ。黒タイルの長さは $1$,白タイルの長さは $2$ である。
  • 整数 $m\geqq 0$ が境界であるとは,ある $k\geqq 0$ について $S_k=m$ となること,すなわち $m$ 番目の玉の直後でタイルが切れることをいう($m=0$ は列の左端)。この事象を $K_m$ とし,$u_m=\mathrm{P}(K_m)$ とおく。$u_0=1$ である。
  • $(S_k)$ の単調性より $K_m$ は互いに排反な事象 $\lbrace S_k=m\rbrace$($0\leqq k\leqq m$)の和であり,$u_m=\sum_{k=0}^{m}\mathrm{P}(S_k=m)$ である。試行回数についての規約 最初の $N$ 回の結果で定まる事象の確率は,$N$ 回以上投げるどのモデルで計算しても同じである。$K_m$ は $X_1,\ldots,X_m$ で定まる($S_k=m$ ならば $k\leqq m$)。以下,考える事象が確定するのに十分な回数だけ投げるモデルで考え,問題文の有限回の設定との整合はその都度確認する。位置と回数の区別 問題文の例「裏,表,表」では $(S_1,S_2,S_3)=(1,3,5)$ で,境界は $0,1,3,5$ である。玉の番号と硬貨投げの回数は一致せず,$p_n$ は玉の番号(位置)について定義されている。

1.2 境界による分解

黒玉は 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 節 )。

1.3 二状態構造

境界の補集合

$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 個の未知量が満たす一次の関係を与える。

1.4 規格化条件と特性根

最後のタイルで分けると $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$ は規格化 $G(1)=1$ に対応し,$u_m$ の定数成分(極限値 $\frac{1}{1+r}$)を生む。
  • 根 $-r$ は 補題3 の係数に一致する。符号は「表で白タイルの内部に入り,次の位置で必ず境界に戻る」ことによる状態の反転を,大きさ $r$ は反転が起こる確率を表す( 5.2 節 )。
    したがって $u_m$ と $p_n$ は「定数 $+$ 定数 $\times(-r)^m$」の形をとる。また方程式 $G(z)=1$ は $z=1$ のほかに $z=-1/r$ を解にもち($G(-1/r)=-\frac{q}{r}+\frac{1}{r}=1$),これが参考解1の保存量 $(-r)^{-S_k}$ を与える( 3.5 節 )。本解で現れる保存量 $p_n+rp_{n-1}$ と 補題3 の左辺は同じ一次結合であり,前者は漸化式の代数的性質として,後者は全確率の分解として現れる( 5.1 節 )。

1.5 作問の設計と解法の導出

以下は設問の配置と数値設定からの分析であり,出題者の意図については推定を含む。

  • 黒で始まるパターン:目的のパターンが黒で始まるため,その直前は必ず境界となり,位置への依存が $u_{n-1}$ の 1 量に集約される。白で始まるパターンでは境界と内部の両方の状態が寄与する( 定理6 )。
  • 試行回数 $n+2$:$n+2$ 番目の玉の存在を保証する最小の回数である(すべて裏のとき玉はちょうど $n+2$ 個)。標本空間が $2^{n+2}$ 通りの有限集合となる代わりに,(3) で「余分な 1 回」が生じ,事象がどの回までに確定するかの理解が問われる。
  • (1) の $p_2=q^4$:2 番目の玉が黒であるには第 1 回が裏でなければならない。$p_2\neq q^3$ であることが位置と回数の区別を検査し,同時に二階漸化式の初期値 2 つを与える。
  • (2) の誘導:(3) における「第 1 回が裏」の場合をそのまま切り出したものである。先頭のタイルを除くと同じ規則の列が残るという自己相似性を確認させ,(3) では「第 1 回が表」の場合(余分な 1 回を含む)を処理させる。条件 $n\geqq 2$,$n\geqq 3$ は $p_{n-1}$,$p_{n-2}$ が定義される範囲に対応する。
  • $q+r=1$ と答の形:特性根が $1,-r$ となり,答は有限等比級数で閉じる。偶数番目と奇数番目が上下から極限 $\frac{q^3}{1+r}$ に近づく振る舞いが設定から自然に生じる。
  • 黒の個数 $3$:個数そのものは本質的でない($q^3$ が $q^k$ に変わるだけ)。目的事象を複雑に見せつつ, 補題2 の分解に気づけば単純化される構成である。
    各構造から導かれる解法は次のとおりである。
    着目する構造数学的翻訳導かれる解法
    先頭のタイルを除くと同じ規則の列が残る第 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 節

2. 本解:先頭の硬貨による再帰

2.1 方針

  1. は直接求める。(2)(3) は第 1 回の結果で全確率を分解し,先頭のタイルを取り除いた残りの列が同じ規則に従うこと(自己相似性)を用いる。(4) は係数の和が $q+r=1$ であることから保存される一次結合 $p_n+rp_{n-1}$ を見出し,一階の漸化式に下げる。本解は 補題2 , 補題3 を用いずに完結する。

2.2 解答

(1)

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

(2)

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

(3)

$n\geqq 3$ とし,第 1 回の結果で分ける。

  • $X_1=1$ のとき:事象は (2) の事象と一致し,その確率は $qp_{n-1}$ である。
  • $X_1=2$ のとき:1,2 番目の玉は白であり,全体の $j$ 番目($j\geqq 3$)は第 2 回以降の列の $j-2$ 番目である。条件は「第 2 回以降の $n+1$ 回で作られる列の $n-2,n-1,n$ 番目がすべて黒」となる。$n$ 回投げれば玉は $n$ 個以上並び,以後の回は右側に玉を加えるだけであるから,この条件は第 2 回以降の最初の $n$ 回で確定し,最後の 1 回は影響しない。$n-2\geqq 1$ であるから,その確率は $p_{n-2}$($(n-2)+2=n$ 回の定義)であり,この場合の確率は $rp_{n-2}$ である。
    ゆえに
    $$ p_n=(1-r)\,p_{n-1}+r\,p_{n-2}\qquad(n\geqq 3). $$

(4)

$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.3 検証・検算

  • 初期値:$n=1$ で $\frac{q^3}{1+r}(1+r)=q^3$,$n=2$ で $\frac{q^3}{1+r}(1-r^2)=q^3(1-r)=q^4$。
  • 漸化式への代入:$(-r)^2=q(-r)+r$($-r$ は特性根)より,$qp_{n-1}+rp_{n-2}=\frac{q^3}{1+r}\left\lbrace q+r-(-r)^{n-2}(q(-r)+r)\right\rbrace=\frac{q^3}{1+r}\lbrace 1-(-r)^n\rbrace$。$n=3$ では $p_3=q^3(1-r+r^2)$。
  • 全数列挙:$r=\frac12$,$n=4$ のとき 6 回の結果 $2^6=64$ 通りは等確率である。 補題2 の分解に従えば,境界 $3$ に到達する仕方は「裏裏裏」(3 回),「裏表」「表裏」(各 2 回,残り 1 回は任意で各 2 通り)であり,続く 3 回が裏となる結果は $1+2+2=5$ 通りである。公式は $\frac{1}{8}\cdot\frac{1-1/16}{3/2}=\frac{5}{64}$ を与え,一致する。
  • パラメータの極限:$r\to+0$ ではほぼすべて裏となり $p_n\to 1$,$r\to 1-0$ では $p_n\to 0$。いずれも公式と整合する。
  • 偶奇と大小:$p_{2k}=\frac{q^3}{1+r}(1-r^{2k})$,$p_{2k-1}=\frac{q^3}{1+r}(1+r^{2k-1})$($k\geqq 1$)より,偶数番目は増加,奇数番目は減少し,ともに $\frac{q^3}{1+r}$ に収束する。$p_n\leqq q^3$ は 補題2 の $u_{n-1}\leqq 1$ と整合する。
    $$ p_2 < p_4 < p_6 < \cdots < \frac{q^3}{1+r} < \cdots < p_5 < p_3 < p_1=q^3. $$

3. 別解と参考解

3.1 (3) の別証:末尾のタイルによる分解

着想・方針

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

検証・検算

  • $u_0=1$,$u_1=q$ から $u_2=q^2+r$ となり,長さ $2$ に到達する配置「黒黒」「白」の確率の和に一致する。
  • 各タイル列の確率は黒タイルの個数と白タイルの個数だけで決まり,列を左右反転しても変わらない。このため「最初のタイル」と「最後のタイル」による分解は同じ係数の漸化式を与える。

3.2 (4) の他の導出:階差数列と特性方程式

着想・方針

  1. の二階漸化式を標準的な方法で解く。係数の和が $1$ であるから,階差が公比 $-r$ の等比数列になる。

解答

階差数列
  1. より $n\geqq 3$ で $p_n-p_{n-1}=-r(p_{n-1}-p_{n-2})$ であり,$p_2-p_1=q^4-q^3=-rq^3$ であるから
    $$ p_n-p_{n-1}=q^3(-r)^{n-1}\qquad(n\geqq 2). $$
    よって $n\geqq 1$ で($n=1$ では和は空)
    $$ p_n=p_1+\sum_{k=2}^{n}(p_k-p_{k-1})=q^3+q^3\sum_{k=2}^{n}(-r)^{k-1}=q^3\sum_{j=0}^{n-1}(-r)^j=\frac{q^3}{1+r}\lbrace 1-(-r)^n\rbrace. $$
特性方程式

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

検証・検算

  • 階差の和は $k=2$ から始まり,初項 $p_1$ を重複して数えない。$n=2$ で $q^3-rq^3=q^4$ となる。
  • 特性方程式による方法は 2 根が相異なること($1\neq -r$)を用いる。$p_0$ は定義されないので,定数は $p_1,p_2$ から定める。

3.3 別解1:境界の補集合による一次漸化式

着想・方針

補題3 により,二階漸化式を経由せず,確率の分割から一次漸化式 $u_m=1-ru_{m-1}$ が直接得られる。これと 補題2 を組み合わせて全設問を処理する。

解答

(1)

$u_0=1$,$u_1=1-ru_0=q$ であるから, 補題2 より $p_1=q^3u_0=q^3$,$p_2=q^3u_1=q^4$ である。

(2)

本解と同じく,第 1 回が裏の場合に先頭の黒玉を除いて $(1-r)p_{n-1}$ を得る。

(3)

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

(4)

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

検証・検算

  • $u_2=1-rq=q^2+r$ は配置「黒黒」「白」の確率の和に一致する。
  • $u_m-\frac{1}{1+r}$ は符号を交代しながら絶対値が $r$ 倍ずつ縮む。よって $u_0 > u_2 > \cdots > \frac{1}{1+r} > \cdots > u_3 > u_1=q$。
    1. で得た $p_n+rp_{n-1}=q^3$ は本解 (4) の保存量と同じ式である。本解では二階漸化式の代数的性質として,ここでは「位置 $n-1$ は境界か白タイルの内部のいずれか一方」という全確率の分割として現れる。

3.4 別解2:タイル配置の直接計数と母関数

着想・方針

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

(1)(2)

$u_0=1$,$u_1=q$ より $p_1=q^3$,$p_2=q^4$。(2) は先頭が黒タイルである列を分離して $(1-r)p_{n-1}$ を得る。

(3)

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

(4)

$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$ 項に一致する。母関数は有限和の生成規則を一括して表したものである。

検証・検算

  • $m=3$ では $j=0,1$ の 2 項で $u_3=q^3+2qr$。$q=1-r$ を代入すると $1-r+r^2-r^3$ となり,閉じた形に一致する。
  • 二項係数の上側は玉の数 $m$ ではなくタイルの数 $m-j$ である。$m=n-1$ に到達するまでの $n-1-j$ 回と続く 3 回で計 $n+2-j$ 回を使い,残り $j$ 回の結果は任意(確率の和 $1$)であるから,有限回の設定と矛盾しない。
  • 有限和のままでは (4) の閉じた形にならない。閉じ方は,母関数(本解法),Pascal 則による漸化式(本解・別解1 に合流),相殺(参考解2)の 3 通りがある。有限和までは高校数学の範囲で完結するが,形式的べき級数は範囲外である。

3.5 参考解1:停止位置と指数型保存量

着想・方針

$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) を示す。

解答((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}$ についての平均をとると,

  • $T\leqq k$ となる値に対しては $Y_{k+1}=Y_k$ であり,$F(Y_{k+1})$ の平均は $F(Y_k)$。
  • $T > k$ となる値に対しては $Y_k=S_k\leqq m-1$,$Y_{k+1}=S_k+X_{k+1}$ であり,$X_{k+1}$ は $X_1,\ldots,X_k$ と独立であるから,$F(Y_{k+1})$ の平均は $qF(S_k+1)+rF(S_k+2)=F(Y_k)$。
    これを $X_1,\ldots,X_k$ について平均して $\mathrm{E}[F(Y_{k+1})]=\mathrm{E}[F(Y_k)]$ を得る。$T\leqq m$ より $Y_m=S_T$ であるから
    $$ \mathrm{E}[F(S_T)]=\mathrm{E}[F(Y_m)]=\mathrm{E}[F(Y_0)]=F(0)=(-r)^{m+1}. $$
    一方 $F(m)=-r$,$F(m+1)=1$ より
    $$ \mathrm{E}[F(S_T)]=-r\,u_m+(1-u_m)=1-(1+r)u_m. $$
    ゆえに $u_m=\dfrac{1-(-r)^{m+1}}{1+r}$($m\geqq 1$)であり,$u_0=1$ もこの式を満たす。 補題2 より $p_n=\dfrac{(1-r)^3}{1+r}\lbrace 1-(-r)^n\rbrace$ である。

検証・検算

  • $m=1$ では $T=1$,$S_T=X_1$ で,$\mathrm{E}[F(X_1)]=qF(1)+rF(2)=-qr+r=r^2=F(0)$ が直接確かめられ,$u_1=q$ を得る。
  • 停止位置が 2 通りであるのは歩幅が $1$ 以上 $2$ 以下だからである。歩幅の最大値が $L$ ならば停止位置は $L$ 通りとなり,非自明な指数解が $L-1$ 個必要になる( 5.5 節 )。
  • $T\leqq m$ と有界であるから,期待値の保存は有限回の反復で示される。符号 $F(m)=-r$,$F(m+1)=1$ の対応を取り違えないこと。

3.6 参考解2:符号反転対合による相殺

着想・方針

黒タイルの確率 $q$ を形式的に $1+(-r)$ と分け,黒タイルを重み $1$ のものと重み $-r$ のものの 2 種に分ける。すると長さ $2$ の部分として,白タイル(重み $r$)と「重み $1$ の黒,重み $-r$ の黒」の並び(重み $-r$)が逆符号で現れる。これらを対にして打ち消すと,別解2の二項係数の和が有限等比和に縮約される。配置を数えて加えるのではなく,打ち消す対応を構成する点で別解2と証明原理が異なる。(1)〜(3) は本解のとおりとし,(4) を示す。

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

検証・検算

  • $m=2$ では $\mathcal{W}_2=\lbrace\mathsf{AA},\mathsf{AC},\mathsf{CA},\mathsf{CC},\mathsf{D}\rbrace$。$\varphi$ は $\mathsf{D}$ と $\mathsf{AC}$ を入れ替え,不動点 $\mathsf{AA},\mathsf{CA},\mathsf{CC}$ の重みの和 $1-r+r^2$ は $u_2=q^2+r$ に一致する。
  • 不動点は $\mathsf{C}$ が先の $\mathsf{C}^j\mathsf{A}^{m-j}$ であり,$\mathsf{A}^j\mathsf{C}^{m-j}$ ではない。
    別解2と合わせると,恒等式
    $$ \sum_{j=0}^{\lfloor m/2\rfloor}\binom{m-j}{j}r^j(1-r)^{m-2j}=\sum_{i=0}^{m}(-r)^i $$
    の組合せ論的証明が得られる。

3.7 同じ系列に属する変形

以下は上記のいずれかと発想の核を共有するため,独立の解法として扱わない。

本解の系列

  • 偶奇分解:$p_n=q^3-rp_{n-1}$ を 2 回用いると $p_{n+2}=q^4+r^2p_n$($n\geqq 1$)。偶数番目と奇数番目がそれぞれ係数正の一次漸化式に従い,$p_{n+2}-p_n=r^2(p_n-p_{n-2})$($n\geqq 3$)から偶奇別の単調性が読める。計算は本解より長い。
  • 行列表示:$(p_n,p_{n-1})^{\top}=N(p_{n-1},p_{n-2})^{\top}$($N$ の第 1 行は $(q,\ r)$,第 2 行は $(1,\ 0)$)。$N$ の固有値 $1,-r$ による対角化は特性方程式と同値である。固有値 $1$ の左固有ベクトルは $(1,\ r)$ であり($(1,\ r)N=(q+r,\ r)$),これとの内積が保存量 $p_n+rp_{n-1}$ である。
  • 帰納法:小さい $n$ の値から答の形を予想し,(3) で帰納的に確かめる。発見の手段としての価値に限られる。
  • 末尾のタイル: 3.1 節 。先頭分解の鏡像である。

別解1 の系列

  • 反復代入:$u_m=1-r(1-ru_{m-2})=\cdots=1-r+r^2-\cdots+(-r)^mu_0$。
  • $p_n$ のままの一次漸化式: 補題2 と 補題3 を合成した $p_n=q^3-rp_{n-1}$($n\geqq 2$)を出発点とする。補助数列を表に出さない最短の記述である。
  • 一次関数の反復:$f(x)=1-rx$ について $f(x)-\frac{1}{1+r}=-r\left(x-\frac{1}{1+r}\right)$。$f$ は不動点のまわりで距離を $r$ 倍に縮め,左右を反転する。$u_m=f^m(1)$ の挙動はクモの巣図で視覚化される。
  • 右端からの偶奇判定:漸化式を立てずに交代和を直接得る表示である。
右端からの偶奇判定

独立な確率変数 $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 節 )。

別解2 の系列

  • 試行回数による表示:$k$ 回で $m$ に達するとき表は $m-k$ 回であり,$u_m=\sum_{k=\lceil m/2\rceil}^{m}\binom{k}{m-k}r^{m-k}q^{2k-m}$。$j=m-k$ とおけば別解2の和に一致する。
  • 格子路:裏を $(1,0)$,表を $(0,1)$ の 1 歩とする格子路で,$x+2y=m$ を満たす点 $(x,y)$ に至る経路を数える。数える対象は同じタイル列である。
  • 状態遷移グラフの経路和:境界から境界に戻る閉路は重み $qz$(黒)と $rz^2$(白,内部を経由)の 2 種類で,その任意個の連結の重みの総和は $1/(1-qz-rz^2)$,すなわち母関数 $U(z)$ である。
  • 有限和の閉じ方:母関数(別解2),Pascal 則による漸化式(本解・別解1 へ合流),相殺(参考解2)。

発見法(証明ではない)

  • 平均歩幅:1 回の平均歩幅 $\mathrm{E}[X_1]=q+2r=1+r$ から,十分先での境界の密度は $\frac{1}{1+r}$ と予想され,$\lim_{n\to\infty}p_n=\frac{q^3}{1+r}$ の見当がつく。有限の $n$ における補正項 $(-r)^n$ はこの考察からは決まらない( 5.1 節 )。
  • 特殊値:$u_0,u_1,u_2=1,\ 1-r,\ 1-r+r^2$ から交代和 $\sum(-r)^j$ を予想できる。

3.8 解法の比較

解法分解・固定するもの中心となる式利用する構造論証上の要点
本解第 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 はそれぞれ停止位置の保存量と符号反転対合という,他の問題に移せる証明原理を示す。

4. 汎用的な探索手順

本問から抽出される手順を,位置・長さが確率的に伸びる過程の問題一般に適用できる形で述べる。
(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

5. 発展事項

各節で,高校数学の範囲で完結する内容と,それを超える一般論を区別して記す。

5.1 再生列と最後の再生点による分解

高校数学の範囲

  補題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$ によって決まる。

5.2 二状態マルコフ連鎖:スペクトル分解と結合

高校数学の範囲

 一次漸化式 $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 歩後に初期状態の差が残る符号付きの平均倍率」であり,符号は表による状態の反転を,大きさは反転が起こる確率を表す。

5.3 指数型マルチンゲールと離散調和関数

高校数学の範囲

 参考解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$)。

5.4 Fibonacci 多項式とドミノ敷き詰め

高校数学の範囲

 別解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 型公式)。

  • $x=y=1$ では $f_m$ は Fibonacci 数 $F_{m+1}$ であり,$1\times m$ の盤をモノミノとドミノで敷き詰める方法の数に等しい。
  • $x=2\cos\theta$,$y=-1$($\sin\theta\neq 0$)では $\alpha,\beta=e^{\pm i\theta}$ より $f_m=\dfrac{\sin(m+1)\theta}{\sin\theta}$(第 2 種 Chebyshev 多項式 $U_m(\cos\theta)$)となる。
  • 本問は $x=q$,$y=r$ の場合で,$x+y=1$ により一方の解が $\alpha=1$,他方が $\beta=-r$ となり,$u_m=f_m=\dfrac{1-(-r)^{m+1}}{1+r}$ が有限等比和になる。
    参考解2の符号反転対合は,$x=1+(-r)$ と分けたうえで和の大部分を打ち消す。符号反転対合による恒等式の証明は組合せ論の標準的な手法であり,Euler の五角数定理に対する Franklin の証明(1881 年)が古典的な例である。

5.5 一般化:局所パターンと白玉の個数

高校数学の範囲

  補題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})$。両者を加えればよい。

  • 黒 $k$ 個の並びでは $a_w=q^k$,$b_w=0$ より $q^ku_{m-1}$。本問は $k=3$ の場合である。
  • $m$ 番目の玉が黒である確率は $qu_{m-1}$,白である確率は $1-qu_{m-1}$($a_w=r$,$b_w=1$)であり,和は $1$ となる。
    どのような有限パターンについても,位置への依存は「定数 $+$ 定数 $\times(-r)^m$」の形に限られる。過去の情報が 2 状態に圧縮され,そのうち非定常な成分が 1 次元であることの帰結である。
    表で白玉を $L$ 個($L\geqq 2$)置く場合,境界でない位置は白タイルの内部の $L-1$ 種類となり, 補題3 と同じ議論で
    $$ u^{(L)}_m=1-r\sum_{j=1}^{L-1}u^{(L)}_{m-j}\quad\left(u^{(L)}_0=1,\ \text{負の添字の項は }0\right),\qquad \sum_{m\geqq 0}u^{(L)}_mz^m=\frac{1}{(1-z)(1+rz+\cdots+rz^{L-1})} $$
    を得る。定常値は $\dfrac{1}{1+(L-1)r}$(平均歩幅の逆数)であり,非定常成分は $1+rz+\cdots+rz^{L-1}=0$ の $L-1$ 個の根に対応する。$L=3$ では 2 根は互いに共役な虚数で絶対値 $1/\sqrt{r}$ をもち,補正項は振動しながら $O(r^{m/2})$ で減衰する。$L=2$ に限り非定常成分が 1 次元となり,答が単一の等比数列 $(-r)^m$ で表される。

6. 最終整理

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

6.2 解答一覧

設問答根拠
(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$

6.3 数学的教訓

  • 試行の回数と観測される位置は別物である。1 回で進む量が一定でない過程では,位置への到達確率 $u_m$ を主役にする。
  • 目的のパターンが再生点から始まるとき,確率は「再生点への到達確率」と「局所パターンの確率」の積に分解される。黒の連続個数は因子 $q^k$ にしか効かない。
  • 有限回の試行で定義された確率を再帰的に扱うときは,各事象が最初の何回で確定するかを明示する。(3) の余分な 1 回はその典型である。
  • 係数の和が $1$ の線形漸化式には保存される一次結合があり,それは裾確率を係数とする全確率の分解と一致する。
  • 状態の補集合が 1 種類しかなければ,二階の関係を経ずに一次の関係が直接立つ。白タイルの長さ $2$ がこの単純さの源泉である。
  • 答に現れる $(-r)^n$ は,裏による過去の情報の消去と表による状態の反転を表す。定常値 $\frac{1}{1+r}$ は平均歩幅の逆数である。
  • 同じ値 $u_m$ が,漸化式,配置の計数,停止位置の保存量,符号反転対合という独立な証明原理から得られる。方法の選択は,設問の誘導,状態の最小性,配置の全体像のいずれを重視するかで決まる。
投稿日:1日前
数学の力で現場を変える アルゴリズムエンジニア募集 - Mathlog served by OptHub

この記事を高評価した人

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

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

バッジはありません。

投稿者

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

コメント

他の人のコメント

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