0

2026年 北海道大学 理系 第5問

4
0
$$$$
2026年 北海道大学 理系 第5問

1個のさいころを投げる試行を繰り返す。最初の持ち点は $1$ とし、$3$ の目が出たときは持ち点を $3$ 倍、$5$ の目が出たときは持ち点を $5$ 倍、$3$ と $5$ 以外の目が出たときは持ち点を $2$ 倍する。たとえば $3$ 回試行して出た目が順番に $6$, $3$, $5$ のとき、持ち点は $1\times 2=2$, $2\times 3=6$, $6\times 5=30$ と変化し、最後の持ち点は $30$ である。次の問いに答えよ。
(1) $n\geqq 2$ とする。$n$ 回試行したとき、最後の持ち点が $4$ の倍数となる確率を求めよ。
(2) 持ち点がはじめて $15$ 以上となったときに試行を終了する。終了するまでに試行した回数の期待値を求めよ。


1. 問題の構造

1.1 記法と確率モデル

第 $i$ 回の試行で持ち点に掛けられる数を倍率 $X_i$ とよぶ。目 $1,2,4,6$ はいずれも倍率 $2$ を与え,目 $3,5$ はそれぞれ倍率 $3,5$ を与える(目 $4,6$ が倍率 $4,6$ を与えるのではない)。したがって $X_1,X_2,\ldots$ は独立同分布で
$$ P(X_i=2)=\frac23,\qquad P(X_i=3)=\frac16,\qquad P(X_i=5)=\frac16. $$
(2) では試行が途中で終了するが,終了後も仮想的に試行を続けた無限列 $X_1,X_2,\ldots$ を考えてよい。終了の判定は各時点までの倍率だけで決まるので,実際に行われる試行の結果の分布はこの拡張によって変わらない。以下の記号を用いる。

  • $S_0=1$,$S_k=X_1X_2\cdots X_k$($k\geqq1$)。$S_k$ は $k$ 回後の持ち点である。
  • $a_k,b_k,c_k$:第 $k$ 回までに倍率 $2,3,5$ が現れた回数。$a_k+b_k+c_k=k$ である。
  • $v_2(m)$:正の整数 $m$ を割り切る $2$ の冪の最大の指数($2$ 進付値)。
  • $T=\min\lbrace k\geqq1 : S_k\geqq15\rbrace$:(2) で終了するまでに試行した回数。
  • $\mathcal{R}=\lbrace 2^a3^b5^c : a,b,c\in\mathbb{Z}_{\geqq0},\ 2^a3^b5^c < 15\rbrace=\lbrace 1,2,3,4,5,6,8,9,10,12\rbrace$:$15$ 未満で到達し得る持ち点の全体。
  • $V_s$($s\in\mathcal{R}$):持ち点 $s$ を訪れる事象,すなわち「ある $k\geqq0$ について $S_k=s$」。
  • $\boldsymbol{1}_A$:事象 $A$ が起これば $1$,起こらなければ $0$ をとる確率変数。

1.2 乗法過程の加法化:素因数の指数

倍率 $2,3,5$ は相異なる素数であるから
$$ S_k=2^{a_k}3^{b_k}5^{c_k} $$
であり,素因数分解の一意性により,持ち点 $S_k$ と指数の組 $(a_k,b_k,c_k)$ は一方から他方が定まる。特に $k=a_k+b_k+c_k$ も $S_k$ から定まる。持ち点の推移は,格子 $\mathbb{Z}_{\geqq0}^3$ 上を各回に確率 $\frac23,\frac16,\frac16$ で $(1,0,0),(0,1,0),(0,0,1)$ だけ進むランダムウォークと同型である。積は可換であるから,固定した $k$ について $S_k$ は倍率の出現順序によらず,個数 $(a_k,b_k,c_k)$ だけで決まる。
二つの設問は,この過程から異なる情報を取り出す。
(1) は $4=2^2$ に関する条件である。$3^{b_n}5^{c_n}$ は奇数であるから
$$ v_2(S_n)=a_n,\qquad 4\mid S_n\iff a_n\geqq2. $$
倍率 $3$ と $5$ の区別は不要であり,各試行は「倍率 $2$(確率 $\frac23$)」か「奇数倍率(確率 $\frac13$)」かの二値試行に圧縮される。$a_n$ は二項分布 $\operatorname{Bin}\left(n,\frac23\right)$ に従い,(1) は $P(a_n\geqq2)$ を問うている。
(2) は持ち点の大小を問うので,$3$ と $5$ の区別が必要になる。各試行を「倍率 $2$ か奇数倍率か」($\frac23:\frac13$)と「奇数倍率ならば $3$ か $5$ か」($\frac12:\frac12$)の二段階に分ければ,(1) は第一段階だけで完結し,(2) は第二段階まで用いる。

1.3 (2) の有限化

停止時刻の有限化

(i) $S_0 < S_1 < S_2 < \cdots$ である。
(ii) すべての $k\geqq0$ について $T > k\iff S_k < 15$ である。
(iii) $T\in\lbrace 2,3,4\rbrace$ であり,$2,3,4$ のいずれの値も正の確率でとる。

(i) $X_{k+1}\geqq2$ より $S_{k+1}=X_{k+1}S_k\geqq2S_k > S_k$ である。
(ii) 定義より,$T > k$ は「$1\leqq j\leqq k$ のすべての $j$ について $S_j < 15$」と同値である。(i) よりこれは $S_k < 15$ と同値である($k=0$ では両辺とも真)。
(iii) $S_1\leqq5 < 15$ より $T > 1$,$S_4\geqq2^4=16$ より $T\leqq4$ である。倍率の列が $(5,5)$,$(2,2,5)$,$(2,2,2,2)$ で始まるとき,それぞれ $T=2,3,4$ となる。

(ii) が (2) の核心である。一般の確率過程では「時刻 $k$ まで一度も閾値に達していない」ことと「時刻 $k$ に閾値の下にいる」ことは異なるが,持ち点は後戻りしないので両者が一致する。これにより初到達時刻の問題は固定時刻 $k=2,3$ における $S_k$ の分布の問題に帰着し,(iii) によって深さ $4$ の有限問題となる。

1.4 閾値 15 の境界構造

境界の判定

(i) $S_2\geqq15\iff(X_1,X_2)\in\lbrace(3,5),(5,3),(5,5)\rbrace$ である。
(ii) $S_3 < 15\iff$「$c_3=0$ かつ $b_3\leqq1$」である。すなわち $S_3 < 15$ となるのは,$(X_1,X_2,X_3)$ が $(2,2,2)$ であるか $(3,2,2)$ の並べ替えであるときに限る。

(i) 2個の倍率の積は $2\cdot2=4$,$2\cdot3=6$,$3\cdot3=9$,$2\cdot5=10$,$3\cdot5=15$,$5\cdot5=25$ のいずれかであり,$15$ 以上となるのは $3\cdot5$ と $5\cdot5$ に限る。
(ii) $c_3\geqq1$ ならば,他の2個の倍率は $2$ 以上であるから $S_3\geqq5\cdot2\cdot2=20$ である。$b_3\geqq2$ ならば $S_3\geqq3\cdot3\cdot2=18$ である。逆に $c_3=0$ かつ $b_3\leqq1$ ならば $S_3\in\lbrace 2^3,\ 2^2\cdot3\rbrace=\lbrace 8,12\rbrace$ であり,いずれも $15$ 未満である。

各時刻における閾値の位置は次のとおりである。

時刻 $k$$S_k < 15$ となる $S_k$ の最大値$S_k\geqq15$ となる $S_k$ の最小値
$1$$5$なし
$2$$10=2\cdot5$$15=3\cdot5$
$3$$12=2^2\cdot3$$18=2\cdot3^2$
$4$なし$16=2^4$

注意すべき点は二つある。第一に,$k=2$ では $3\cdot5=15$ が閾値に一致する。条件の「以上」がこの場合を終了側に入れており,「$15$ より大きい」と読むと $P(T=2)$ は $\frac1{12}$ から $\frac1{36}$ に変わる( 1.6 節 )。第二に,$k=3$ では $12 < 15 < 18$ の隙間により,継続する倍率の組が $\lbrace2,2,2\rbrace$ と $\lbrace2,2,3\rbrace$ の二種類だけになる。

1.5 時間と状態の二重計数

時間と状態の二重計数

$$ T=\sum_{k=0}^{3}\boldsymbol{1}_{\lbrace S_k < 15\rbrace}=\sum_{s\in\mathcal{R}}\boldsymbol{1}_{V_s}. $$
したがって
$$ E[T]=\sum_{k=0}^{3}P(S_k < 15)=\sum_{s\in\mathcal{R}}P(V_s). $$

第1の等号:$T=\sum_{k\geqq0}\boldsymbol{1}_{\lbrace T > k\rbrace}$(右辺では $k=0,1,\ldots,T-1$ の $T$ 個の項だけが $1$)に 補題1 (ii)(iii) を用いればよい。
第2の等号: 補題1 (i) より $S_0,S_1,\ldots,S_{T-1}$ は相異なり,いずれも $15$ 未満かつ $2^a3^b5^c$ の形であるから $\mathcal{R}$ に属する。また $k\geqq T$ ならば $S_k\geqq S_T\geqq15$ である。よって $V_s$ が起こる $s\in\mathcal{R}$ の全体は $\lbrace S_0,\ldots,S_{T-1}\rbrace$ に一致し,その個数は $T$ である。
期待値の等式は有限和の線形性による。

到達確率

$s=2^a3^b5^c\in\mathcal{R}$,$k=a+b+c$ とする。このとき $V_s=\lbrace S_k=s\rbrace=\lbrace (a_k,b_k,c_k)=(a,b,c)\rbrace$ であり,
$$ P(V_s)=\frac{k!}{a!\,b!\,c!}\left(\frac23\right)^a\left(\frac16\right)^{b+c}. $$

$S_j=s$ ならば,素因数分解の一意性より $(a_j,b_j,c_j)=(a,b,c)$ であり,$j=a+b+c=k$ となる。よって $V_s=\lbrace S_k=s\rbrace$ であり,これは $(a_k,b_k,c_k)=(a,b,c)$ と同値である。倍率 $2,3,5$ をそれぞれ $a,b,c$ 個含む長さ $k$ の列は $\frac{k!}{a!\,b!\,c!}$ 個あり,各列の確率は $\left(\frac23\right)^a\left(\frac16\right)^b\left(\frac16\right)^c$ である。

$\mathcal{R}$ の各状態について 補題4 を適用すると次の表を得る。

$s$$(a,b,c)$$k=a+b+c$$P(V_s)$
$1$$(0,0,0)$$0$$1$
$2$$(1,0,0)$$1$$\frac23$
$3$$(0,1,0)$$1$$\frac16$
$5$$(0,0,1)$$1$$\frac16$
$4$$(2,0,0)$$2$$\frac49$
$6$$(1,1,0)$$2$$\frac29$
$9$$(0,2,0)$$2$$\frac1{36}$
$10$$(1,0,1)$$2$$\frac29$
$8$$(3,0,0)$$3$$\frac8{27}$
$12$$(2,1,0)$$3$$\frac29$

$k$ ごとに足すと $1,\ 1,\ \frac{11}{12},\ \frac{14}{27}$ となり,これは $P(S_k < 15)$ に等しい。実際,事象 $\lbrace S_k < 15\rbrace$ は,$s\in\mathcal{R}$ かつ $a+b+c=k$ を満たす $s$ にわたる $\lbrace S_k=s\rbrace$ の互いに排反な和である。全体を足すと $\frac{371}{108}$ となる。すなわち 補題3 の二つの和は,同じ有限の表を時刻ごとに足すか状態ごとに足すかの違いである。
この構造には二つの事実が関わっている。単調性( 補題1 (i))により各状態は高々1回しか訪れられず,$P(V_s)=\sum_{k}P(S_k=s)$ が成り立つ。倍率が素数であること(素因数分解の一意性)により,この和は $k=a+b+c$ の1項だけとなり,多項係数で閉じた形に書ける。倍率に合成数(例えば $4$ 倍)が含まれれば,前者は保たれるが後者は失われる。

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

以上の構造から,作問の設計は次のように読める(数値設定からの分析であり,出題者の意図についての推定を含む)。

  • さいころの $6$ 個の目を倍率 $2,3,5$ の3種類に集約し,確率を $\frac23,\frac16,\frac16$ とする。目 $4,6$ も倍率 $2$ を与えるので,「目が $2$ である確率」$\frac16$ と「倍率が $2$ である確率」$\frac23$ の区別が試される。
  • 倍率を相異なる素数とする。素因数分解の一意性により状態は指数の組で記述され,順序を捨てて数えることができる( 1.2 節 )。
    1. の条件を $4=2^2$ とし,素数 $3,5$ を判定から外す。答 $1-\frac{2n+1}{3^n}$ は $n=0,1$ でも正しい値 $0$ を与えるので,条件 $n\geqq2$ は自明な場合を除くためのものと解釈できる。
    1. の閾値 $15$ は,最小倍率について $2^3 < 15\leqq2^4$,最大倍率について $5 < 15\leqq5^2$ を満たし,$T\in\lbrace2,3,4\rbrace$ を保証する( 補題1 )。さらに $15=3\cdot5$ は2回後の境界を閾値に一致させ,不等号の読み(以上か,より大きいか)を答に反映させる。
      閾値を一般の整数 $N$ に変えたとき,$T_N=\min\lbrace k : S_k\geqq N\rbrace$ の期待値は次のようになる( 命題5 による)。
      $N$$6$$7,8$$9$$10$$11,12$$13,14,15$$16$
      $E[T_N]$$\frac{22}{9}$$\frac83$$\frac{80}{27}$$\frac{323}{108}$$\frac{347}{108}$$\frac{371}{108}$$\frac{377}{108}$
      $E[T_{N+1}]-E[T_N]$ は,$N$ が $2^a3^b5^c$ の形ならば持ち点 $N$ の到達確率( 補題4 の式)に等しく,そうでなければ $0$ である。$13\leqq N\leqq15$ では一定であり,「$15$ より大きい」と読むことは $N=16$ に当たる。その差 $\frac{6}{108}=\frac1{18}$ は持ち点 $15$ の到達確率 $2\cdot\frac16\cdot\frac16$ である。
      各構造がどの解法を導くかを整理する。
      着目する構造導かれる解法
      $2$ 進付値と二項分布本解 (1)
      付値の打ち切り(3状態への圧縮)別解1
      単調性による $T > k\iff S_k < 15$ と有限化本解 (2),3.2 節
      最小倍率による正規化3.1 節
      第一歩解析(状態からの再帰)別解2
      状態の非再訪と素因数分解の一意性別解3
      有限個の格子点を分ける直線の取り替え参考解1
      乗法過程の形式的冪級数表示参考解2

2. 本解

2.1 方針

  1. は $4=2^2$ に注目して倍率 $2$ の出現回数 $a_n$ に帰着させ,余事象 $a_n\leqq1$ を数える。(2) は持ち点の単調増加から $T\in\lbrace2,3,4\rbrace$ と $T > k\iff S_k < 15$ を導き,
    $$ T=2+\boldsymbol{1}_{\lbrace T > 2\rbrace}+\boldsymbol{1}_{\lbrace T > 3\rbrace} $$
    の期待値をとる。必要な確率は $P(S_2 < 15)$ と $P(S_3 < 15)$ だけであり,境界の積 $3\cdot5=15$,$2^2\cdot3=12$,$2\cdot3^2=18$,$2^2\cdot5=20$ を用いて数える。

2.2 解答

(1)

各試行で持ち点を $2$ 倍する目は $1,2,4,6$ であるから,倍率 $2$ が現れる確率は $\frac46=\frac23$,奇数倍率($3$ 倍または $5$ 倍)が現れる確率は $\frac13$ である。$n$ 回のうち倍率 $2$ が現れた回数を $a_n$ とすると,最後の持ち点は $2^{a_n}m$($m$ は奇数)の形であるから
$$ 4\mid S_n\iff a_n\geqq2. $$
各試行は独立であるから
$$ P(a_n=0)=\left(\frac13\right)^n=\frac1{3^n},\qquad P(a_n=1)=\binom{n}{1}\frac23\left(\frac13\right)^{n-1}=\frac{2n}{3^n}. $$
よって求める確率は
$$ P(a_n\geqq2)=1-\frac1{3^n}-\frac{2n}{3^n}=1-\frac{2n+1}{3^n}. $$

(2)

$k$ 回後の持ち点を $S_k$($S_0=1$),終了するまでに試行した回数を $T$ とする。
どの倍率も $2$ 以上であるから $S_{k+1}\geqq2S_k > S_k$ であり,持ち点は狭義単調増加する。ゆえに「$k$ 回後までに終了していない」こと,すなわち $T > k$ は,$S_k < 15$ と同値である($S_k < 15$ ならばそれ以前の持ち点もすべて $15$ 未満である)。また $S_1\leqq5 < 15$,$S_4\geqq2^4=16$ であるから $T\in\lbrace 2,3,4\rbrace$ である。したがって
$$ T=2+\boldsymbol{1}_{\lbrace T > 2\rbrace}+\boldsymbol{1}_{\lbrace T > 3\rbrace},\qquad E[T]=2+P(S_2 < 15)+P(S_3 < 15). $$
2回後の持ち点は $4,6,9,10,15,25$ のいずれかであり,$15$ 以上となるのは倍率の列が $(3,5),(5,3),(5,5)$ のときに限る。よって
$$ P(S_2 < 15)=1-3\left(\frac16\right)^2=\frac{11}{12}. $$
3回後について,倍率 $5$ が1回でも現れれば $S_3\geqq5\cdot2\cdot2=20$,倍率 $3$ が2回以上現れれば $S_3\geqq3\cdot3\cdot2=18$ である。逆に倍率の列が $(2,2,2)$ または $(3,2,2)$ の並べ替え(3通り)ならば,$S_3$ は $8$ または $12$ である。よって
$$ P(S_3 < 15)=\left(\frac23\right)^3+3\cdot\frac16\left(\frac23\right)^2=\frac{8}{27}+\frac{6}{27}=\frac{14}{27}. $$
以上より
$$ E[T]=2+\frac{11}{12}+\frac{14}{27}=\frac{216+99+56}{108}=\frac{371}{108}. $$

解答のまとめ

設問答
(1)$1-\dfrac{2n+1}{3^n}$
(2)$\dfrac{371}{108}$

2.3 検証・検算

    1. の特殊値:$n=2$ では2回とも倍率 $2$ でなければならず,確率は $\left(\frac23\right)^2=\frac49$ である。公式は $1-\frac59=\frac49$ を与える。$n=3$ では $P(a_3=2)+P(a_3=3)=\frac{12}{27}+\frac8{27}=\frac{20}{27}$ であり,公式の値 $1-\frac7{27}$ と一致する。
    1. の増分:$\left(1-\frac{2n+3}{3^{n+1}}\right)-\left(1-\frac{2n+1}{3^n}\right)=\frac{4n}{3^{n+1}}$ は,「$a_n=1$ の状態から次に倍率 $2$ が出る確率」$\frac{2n}{3^n}\cdot\frac23$ に一致する。また $n\to\infty$ で確率は $1$ に収束する。
    1. の範囲:$T\in\lbrace2,3,4\rbrace$ より $2 < E[T] < 4$ でなければならず,$\frac{371}{108}\approx3.435$ はこれを満たす。$P(T=4)=P(S_3 < 15)=\frac{14}{27}\approx0.52$ が大きいことも,$E[T]$ が $3$ を上回ることと整合する。
    1. の一様な数え直し:さいころの目の列で数えると $P(S_2 < 15)=\frac{36-3}{36}$,$P(S_3 < 15)=\frac{4^3+3\cdot4^2}{6^3}=\frac{112}{216}$ であり,上の値と一致する。
    1. の別経路:状態ごとの和( 1.5 節 の表,別解3)も $\frac{371}{108}$ を与える。停止時の分布に関する恒等式による検算は 5.5 節 で行う。

3. 別解と参考解

3.1 節と 3.2 節は本解の特定の段階に対する別証・別の導出,3.3〜3.5 節は高校数学の範囲で完結する別解,3.6 節と 3.7 節は問題特化の変換または大学数学の道具を用いる参考解である。

3.1 補題2 の別証:最小倍率による正規化

着想・方針

補題2 を,倍率 $2$ の個数を消去した表示から導く。どの試行でも持ち点は少なくとも $2$ 倍される。倍率 $3,5$ を「$2$ 倍に上乗せ $\frac32$ 倍,$\frac52$ 倍が加わったもの」とみれば,固定した時刻 $k$ では閾値の判定が上乗せ分の大小比較になる。

解答

$a_k=k-b_k-c_k$ より
$$ S_k=2^k\varphi(b_k,c_k),\qquad \varphi(b,c)=\left(\frac32\right)^b\left(\frac52\right)^c. $$
$\varphi$ は $b,c$ のそれぞれについて狭義単調増加である。
$k=2$ のとき,$S_2\geqq15\iff\varphi(b_2,c_2)\geqq\frac{15}{4}$ である。$b+c\leqq2$ の範囲で
$$ \varphi(0,0)=1,\quad \varphi(1,0)=\frac32,\quad \varphi(0,1)=\frac52,\quad \varphi(2,0)=\frac94,\quad \varphi(1,1)=\frac{15}{4},\quad \varphi(0,2)=\frac{25}{4} $$
であるから,$S_2\geqq15\iff(b_2,c_2)\in\lbrace(1,1),(0,2)\rbrace$。これは倍率の列 $(3,5),(5,3),(5,5)$ に当たる。
$k=3$ のとき,$S_3 < 15\iff\varphi(b_3,c_3) < \frac{15}{8}$ である。
$$ \varphi(1,0)=\frac32 < \frac{15}{8} < \frac94=\varphi(2,0) < \frac52=\varphi(0,1) $$
と単調性より,$c_3\geqq1$ ならば $\varphi\geqq\frac52$,$b_3\geqq2$ ならば $\varphi\geqq\frac94$ である。よって $S_3 < 15\iff(b_3,c_3)\in\lbrace(0,0),(1,0)\rbrace$ となる。

検証・検算

$k=2$ の境界 $\varphi(1,1)=\frac{15}{4}$ はちょうど等号であり,「以上」の読みが判定を左右することがここでも確認される。$(b,c)$ 平面で見ると,継続する点の集合は直線 $b\log\frac32+c\log\frac52=\log\frac{15}{2^k}$ の下側にある格子点の全体であり,各座標について下に閉じている。その極大元は $k=2$ で $(2,0),(0,1)$(持ち点 $9,10$),$k=3$ で $(1,0)$(持ち点 $12$)であり, 1.4 節 の表と一致する。

3.2 $E[T]$ の他の導出:停止時刻の分布

着想・方針

$T$ のとり得る値は $2,3,4$ だけであるから( 補題1 ),分布そのものを求めて定義 $E[T]=\sum_kkP(T=k)$ を用いる。必要な数え上げは本解と同じであり,期待値の組み立て方だけが異なる。

解答

補題1 (ii) より $P(T > k)=P(S_k < 15)$ であるから,
$$ P(T=2)=1-P(S_2 < 15)=\frac1{12},\qquad P(T=4)=P(S_3 < 15)=\frac{14}{27}, $$
$$ P(T=3)=P(S_2 < 15)-P(S_3 < 15)=\frac{11}{12}-\frac{14}{27}=\frac{43}{108}. $$
よって
$$ E[T]=2\cdot\frac1{12}+3\cdot\frac{43}{108}+4\cdot\frac{14}{27}=\frac{18+129+224}{108}=\frac{371}{108}. $$

検証・検算

$\frac1{12}+\frac{43}{108}+\frac{14}{27}=\frac{9+43+56}{108}=1$ である。本解との関係は,$T\in\lbrace2,3,4\rbrace$ に対する恒等式
$$ \sum_{k}kP(T=k)=\sum_{k\geqq0}P(T > k) $$
である。終了した時刻を数えるか,継続している時刻を数えるかの違いであり,本問では本解の方が $P(T=3)$ を経由しない分だけ短い。

3.3 別解1:因数 $2$ の個数を有限状態で追う

着想・方針

  1. の判定に必要なのは $a_n$ そのものではなく,$a_n$ が $0,1,2$ 以上のいずれであるかだけである。打ち切った量 $\min(a_n,2)$ は,次の試行の結果とあわせて次の値が決まるので,3状態の推移として追える。

解答

$A_n=P(a_n=0)$,$B_n=P(a_n=1)$,$C_n=P(a_n\geqq2)$ とおく。$\delta=\boldsymbol{1}_{\lbrace X_{n+1}=2\rbrace}$ とすると $a_{n+1}=a_n+\delta$ であり,
$$ \min(a_{n+1},2)=\min\bigl(\min(a_n,2)+\delta,\ 2\bigr) $$
が成り立つ。$X_{n+1}$ は $X_1,\ldots,X_n$ と独立で $P(\delta=1)=\frac23$ であるから
$$ A_{n+1}=\frac13A_n,\qquad B_{n+1}=\frac23A_n+\frac13B_n,\qquad C_{n+1}=\frac23B_n+C_n, $$
$(A_0,B_0,C_0)=(1,0,0)$ である。第1式より $A_n=3^{-n}$ である。第2式の両辺に $3^{n+1}$ を掛けると
$$ 3^{n+1}B_{n+1}=2\cdot3^nA_n+3^nB_n=2+3^nB_n $$
となり,$3^nB_n$ は公差 $2$,初項 $3^0B_0=0$ の等差数列であるから $B_n=\frac{2n}{3^n}$ である。よって
$$ C_n=1-A_n-B_n=1-\frac{2n+1}{3^n}. $$

検証・検算

第3式 $C_{n+1}-C_n=\frac23B_n=\frac{4n}{3^{n+1}}$ は,得られた $C_n$ の差分と一致する( 2.3 節 )。推移を行列で書くと
$$ \begin{pmatrix}A_{n+1}\\ B_{n+1}\\ C_{n+1}\end{pmatrix} =\begin{pmatrix}\frac13&0&0\\ \frac23&\frac13&0\\ 0&\frac23&1\end{pmatrix} \begin{pmatrix}A_n\\ B_n\\ C_n\end{pmatrix} $$
であり,固有値 $\frac13$ は重複度 $2$ をもつが固有空間は1次元である(2次の Jordan 細胞をなす)。$B_n$ に現れる因子 $n$ はこの重複に由来する。

3.4 別解2:残り期待回数の後ろ向き再帰

着想・方針

未来の経路を列挙する代わりに,現在の持ち点 $s$ から終了までの残り回数の期待値 $E_s$ を状態ごとに定め,次の1回の結果で場合分けする(第一歩解析)。持ち点は増加する一方なので,閾値に近い状態から順に値が確定する。

解答

正の整数 $s$ に対し $T^{(s)}=\min\lbrace k\geqq0 : sX_1\cdots X_k\geqq15\rbrace$,$E_s=E[T^{(s)}]$ とおく。$T=T^{(1)}$ であり,$T^{(s)}\leqq4$ より $E_s$ は有限である。$s\geqq15$ ならば $E_s=0$ である。$s < 15$ ならば $T^{(s)}\geqq1$ であり,$X_2,X_3,\ldots$ に対して同様に定めた量を用いると $T^{(s)}=1+T'^{(sX_1)}$ と書ける。$(X_2,X_3,\ldots)$ は $X_1$ と独立で $(X_1,X_2,\ldots)$ と同じ分布をもつから
$$ E_s=1+\frac23E_{2s}+\frac16E_{3s}+\frac16E_{5s}\qquad(s < 15) $$
が成り立つ。ただし添字が $15$ 以上の項は $0$ である。$1$ から到達し得る $15$ 未満の状態は $\mathcal{R}$ の元に限るので,大きい方から順に求める。

  • $s\in\lbrace8,9,10,12\rbrace$:$2s\geqq16$ であるから $E_s=1$。
  • $s\in\lbrace5,6\rbrace$:$2s\in\lbrace10,12\rbrace$,$3s,5s\geqq15$ であるから $E_s=1+\frac23\cdot1=\frac53$。
  • $s=4$:$E_4=1+\frac23E_8+\frac16E_{12}=1+\frac23+\frac16=\frac{11}{6}$。
  • $s=3$:$E_3=1+\frac23E_6+\frac16E_9=1+\frac{10}{9}+\frac16=\frac{41}{18}$。
  • $s=2$:$E_2=1+\frac23E_4+\frac16E_6+\frac16E_{10}=1+\frac{11}{9}+\frac5{18}+\frac16=\frac83$。
    したがって
    $$ E[T]=E_1=1+\frac23E_2+\frac16E_3+\frac16E_5=1+\frac{16}{9}+\frac{41}{108}+\frac{5}{18}=\frac{108+192+41+30}{108}=\frac{371}{108}. $$

検証・検算

$5$ と $6$ は異なる持ち点であるが,「倍率 $2$ なら次の1回で必ず終了する状態へ,奇数倍率なら即終了」という同じ未来をもつので $E_5=E_6$ となる。同様に $8,9,10,12$ は次の1回で必ず終了する。値の妥当性は,状態 $s$ から出発した状態占有の和(別解3)でも確かめられる。例えば $s=2$ から訪れ得る $15$ 未満の状態は $2,4,6,10,8,12$ で,その到達確率の和は $1+\frac23+\frac16+\frac16+\frac49+\frac29=\frac83=E_2$ である。

3.5 別解3:訪れる状態の確率の和

着想・方針

試行回数を時間軸で数える代わりに,終了前に通過する $15$ 未満の状態の個数として数える。持ち点は同じ値に戻らないので,各状態は高々1回しか訪れられず,期待値は各状態への到達確率の和になる。到達確率は素因数分解の一意性から多項分布で直接書ける。

解答

持ち点は狭義単調増加するから,$S_0,\ldots,S_{T-1}$ は相異なる $15$ 未満の値であり,すべて $\mathcal{R}$ に属する。また終了後の持ち点は $15$ 以上である。よって $T$ は「訪れた $\mathcal{R}$ の元の個数」に等しく,
$$ T=\sum_{s\in\mathcal{R}}\boldsymbol{1}_{V_s},\qquad E[T]=\sum_{s\in\mathcal{R}}P(V_s). $$
$s=2^a3^b5^c$ を訪れるのは,$k=a+b+c$ 回目に倍率 $2,3,5$ の個数がちょうど $(a,b,c)$ になるときに限るから
$$ P(V_s)=\frac{(a+b+c)!}{a!\,b!\,c!}\left(\frac23\right)^a\left(\frac16\right)^{b+c} $$
である( 補題3 , 補題4 )。$s=1,2,3,4,5,6,8,9,10,12$ に対する値は順に
$$ 1,\ \frac23,\ \frac16,\ \frac49,\ \frac16,\ \frac29,\ \frac8{27},\ \frac1{36},\ \frac29,\ \frac29 $$
であるから
$$ E[T]=\frac{108+72+18+48+18+24+32+3+24+24}{108}=\frac{371}{108}. $$

検証・検算

$7,11,13,14$ は $2,3,5$ だけの積では表せないので $\mathcal{R}$ に含まれない。状態 $12=2^2\cdot3$ への経路は倍率の並び $(2,2,3),(2,3,2),(3,2,2)$ の3通りあり,$3\left(\frac23\right)^2\frac16=\frac29$ となる。状態を $k=a+b+c$ ごとにまとめると $P(S_k < 15)$ が再現され( 1.5 節 ),本解と同一の量を別の順序で足していることが確認できる。

3.6 参考解1:閾値判定の加法化

着想・方針

2回後と3回後の判定だけが必要であることに着目し,各試行に小さな整数 $d_i$(倍率 $2,3,5$ にそれぞれ $0,1,2$)を対応させる。和 $D_k=d_1+\cdots+d_k=b_k+2c_k$ は積を保存しないが, 3.1 節 の $(b,c)$ 平面で,有限個の格子点に対する真の境界直線を,同じ点を同じ側に分ける直線 $b+2c=\text{一定}$ に取り替えたものになっている。

解答

$D_k=b_k+2c_k$ とおく。$b+c\leqq2$ を満たす格子点のうち $b+2c\geqq3$ となるのは $(1,1),(0,2)$ だけであり,$b+c\leqq3$ を満たす格子点のうち $b+2c\leqq1$ となるのは $(0,0),(1,0)$ だけである。よって 補題2 (または 3.1 節 )より
$$ T=2\iff S_2\geqq15\iff D_2\geqq3,\qquad T=4\iff S_3 < 15\iff D_3\leqq1. $$
さいころの目で数えると,$d_i$ の値 $0,1,2$ に対応する目はそれぞれ $4,1,1$ 個である。多項式 $(4+u+u^2)^k$ の $u^j$ の係数が $D_k=j$ となる目の列の個数を与えるから
$$ P(T=2)=\frac{2\cdot1\cdot1+1^2}{6^2}=\frac{3}{36}=\frac1{12},\qquad P(T=4)=\frac{4^3+3\cdot4^2}{6^3}=\frac{112}{216}=\frac{14}{27}. $$
ここで $u^3$ の係数 $2$ は $u\cdot u^2$ の並びの数,$u^4$ の係数 $1$ は $u^2\cdot u^2$ に当たる。$T\in\lbrace2,3,4\rbrace$ より $T=3-\boldsymbol{1}_{\lbrace T=2\rbrace}+\boldsymbol{1}_{\lbrace T=4\rbrace}$ であるから
$$ E[T]=3-\frac1{12}+\frac{14}{27}=\frac{324-9+56}{108}=\frac{371}{108}. $$

検証・検算

$D_2=2$ の場合は持ち点 $9$(倍率 $3,3$)と $10$(倍率 $2,5$)があり,いずれも $15$ 未満である。$D_3=2$ の場合は持ち点 $18$($2,3,3$)と $20$($2,2,5$)であり,いずれも $15$ 以上である。境界が $D_2\geqq3$,$D_3\leqq1$ に置かれることがこの具体例から逆に確かめられる。対応 $2,3,5\mapsto0,1,2$ は準同型ではなく,閾値や時刻を変えれば判定を保存しない(例えば閾値 $16$ の2回後では $D_2=3$ の持ち点 $15$ が継続側に移る)。この限定を明示したうえで用いる問題特化の圧縮である。

3.7 参考解2:多変数母関数による (1)(2) の統一

着想・方針

1回の試行を多項式 $f(x,y,z)=\frac23x+\frac16y+\frac16z$ で表し,指数 $(a,b,c)$ を単項式 $x^ay^bz^c$ で記録する。$n$ 回後の状態の分布は $f^n$ の係数,全時刻にわたる到達確率は $\sum_nf^n$ の係数として一括して得られる。(1) は変数 $y,z$ を消去する周辺化,(2) は $15$ 未満の領域の係数和として読める。

解答

多項定理より
$$ f(x,y,z)^n=\sum_{a+b+c=n}\frac{n!}{a!\,b!\,c!}\left(\frac23\right)^a\left(\frac16\right)^{b+c}x^ay^bz^c $$
であり,$x^ay^bz^c$ の係数は $P\bigl((a_n,b_n,c_n)=(a,b,c)\bigr)$ に等しい。
(1):多項式 $f^n$ に $y=z=1$ を代入すると,$x^a$ の係数は $\sum_{b,c}P\bigl((a_n,b_n,c_n)=(a,b,c)\bigr)=P(a_n=a)$ となる。$f(x,1,1)=\frac13+\frac23x$ であるから
$$ P(4\mid S_n)=1-[x^0]\left(\frac13+\frac23x\right)^n-[x^1]\left(\frac13+\frac23x\right)^n=1-\frac1{3^n}-\frac{2n}{3^n}=1-\frac{2n+1}{3^n}. $$
ここで $[x^j]g$ は $g$ の $x^j$ の係数を表す。
(2):$f$ は定数項をもたないので,形式的冪級数環 $\mathbb{Q}[[x,y,z]]$ において
$$ G(x,y,z)=\sum_{n\geqq0}f^n=\frac{1}{1-\left(\frac23x+\frac16y+\frac16z\right)} $$
が定まる。$f^n$ は $n$ 次の斉次多項式であるから,$x^ay^bz^c$ の係数には $n=a+b+c$ の項だけが寄与し,その値は 補題4 の $P(V_s)$($s=2^a3^b5^c$)に等しい。よって 補題3 より
$$ E[T]=\sum_{\substack{a,b,c\geqq0\\ 2^a3^b5^c < 15}}[x^ay^bz^c]\,G(x,y,z)=\frac{371}{108}. $$
時刻を記録する変数 $w$ を加え,$G_w=\sum_{n\geqq0}w^nf^n=(1-wf)^{-1}$ とする。上と同じ係数和をとると
$$ H(w)=\sum_{\substack{a,b,c\geqq0\\ 2^a3^b5^c < 15}}[x^ay^bz^c]\,G_w=\sum_{k\geqq0}P(S_k < 15)\,w^k=1+w+\frac{11}{12}w^2+\frac{14}{27}w^3 $$
となる。$H(1)=E[T]$ は本解であり,$w$ の次数でまとめる前の係数の和は別解3である。

検証・検算

$f(1,1,1)=1$ より,$f^n$ の係数の総和は各 $n$ で $1$ である。また $T\geqq1$ に対して
$$ (1-w)\sum_{k\geqq0}P(T > k)\,w^k=1-\sum_{k\geqq1}P(T=k)\,w^k $$
が成り立つから,$E[w^T]=1-(1-w)H(w)$ である。右辺を展開すると
$$ E[w^T]=\frac1{12}w^2+\frac{43}{108}w^3+\frac{14}{27}w^4 $$
となり,3.2 節の分布が再現される。母関数は高校数学の答案としては過剰であるが,本解・3.2 節・別解3 が同じ係数の異なる読み方であることを一つの代数的対象で示す。

3.8 同じ系列に属する変形

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

  • 一様な目の列による直接計数((1)):倍率 $2$ となる目は $4$ 個,奇数倍率となる目は $2$ 個であるから,余事象の列の個数は $2^n+n\cdot4\cdot2^{n-1}$ であり,$1-\frac{(2n+1)2^n}{6^n}=1-\frac{2n+1}{3^n}$ を得る。二項分布の名称を用いない本解である。
  • 1変数の確率母関数((1)):$g(t)=\left(\frac13+\frac23t\right)^n$ として $1-g(0)-g'(0)$ を計算する。本解の係数抽出であり,参考解2 の $y=z=1$ の場合に当たる。
  • 2回目の倍率 $2$ までの待ち時間((1)):その時刻を $\tau$ とすると $\lbrace\tau\leqq n\rbrace=\lbrace a_n\geqq2\rbrace$ であり,$P(\tau=k)=(k-1)\left(\frac23\right)^2\left(\frac13\right)^{k-2}$ の和として同じ値を得る。事象の等式が示すとおり本解と同じ核をもつ。
  • $\bmod 4$ の状態推移((1)):倍率は $\bmod 4$ で $5\equiv1$,$3\equiv-1$ として作用し,倍率 $2$ は奇数を $2$ へ,$2$ を $0$ へ移す($2$ と $0$ は奇数倍で変わらない)。状態 $1,3$ は倍率 $3,5$ の下で入れ替わるだけなので「奇数」にまとめられ,別解1 の3状態の推移になる。
  • 固定長の標本空間への埋め込み((2)):終了後も3回目まで仮想的に投げた $6^3=216$ 本の目の列を考える。各列で実際に行われる回数の総和は,2回目までの $2\cdot216$,3回目を行う列 $33\cdot6=198$,4回目を行う列 $112$ の和 $742$ であり,$E[T]=\frac{742}{216}=\frac{371}{108}$ を得る。本解の $T=2+\boldsymbol{1}_{\lbrace T > 2\rbrace}+\boldsymbol{1}_{\lbrace T > 3\rbrace}$ を一様な標本空間上で数えたものである。
  • 最大値 $4$ を基準とする式((2)):$E[T]=4-P(T\leqq2)-P(T\leqq3)=4-\frac1{12}-\frac{13}{27}=\frac{371}{108}$。本解の補集合による言い換えである。
  • 吸収マルコフ連鎖の基本行列((2)):別解2 の連立方程式,および本解と別解3 の和を行列で表したものである( 5.3 節 )。
  • 順序集合・境界の見方((2)):継続する倍率の組の集合が下に閉じていることを用い,極大な継続パターンと極小な終了パターンだけを調べる。 補題2 の発見法である( 5.7 節 )。
    次のものは,独立の解法として採用しない。
  • 独立性から得られる $E[S_n]=\left(\frac83\right)^n$ の利用:持ち点の平均の成長率は得られるが,$E[T]$ は定まらない。
  • マルチンゲールの任意停止定理と Wald の等式:成り立つ恒等式は終了時の分布を必要とし,$E[T]$ を直接は与えない( 5.5 節 )。
  • 対数をとった加法的ランダムウォーク:閾値が大きい場合の漸近挙動を与えるが,本問の正確な値は有限個の状態の計算に帰着する( 5.6 節 )。
  • 複素数(1 の冪根による係数抽出),三角関数,初等幾何,凸性(Jensen の不等式):本問の構造に対応する周期・角度・図形がなく,凸性からは評価しか得られない。

3.9 解法の比較

解法対象主に利用する構造範囲長所注意点
本解(1)$2$ 進付値,二項分布高校最短,再現性が高い「目が $2$」と「倍率 $2$」の区別
本解(2)単調性,有限化,尾確率高校$P(T=3)$ も不要で最短$T > k\iff S_k < 15$ の根拠を述べる
3.1 節(2) の判定最小倍率による正規化高校境界が一目で分かる単調性の確認
3.2 節(2)停止時刻の分布高校期待値の定義に忠実計算が一段多い
別解1(1)付値の打ち切り,状態推移高校複雑な倍数条件へ拡張できる打ち切りと推移の整合
別解2(2)第一歩解析高校閾値が大きくても機械的に使える状態数が多い,先頭の $1$
別解3(2)非再訪,素因数分解の一意性高校連立も漸化式も不要和で期待値が得られる理由の説明
参考解1(2)格子点の線形分離高校計算が最も短い判定の保存を先に示す
参考解2(1)(2)形式的冪級数大学両設問と各解法を統一する答案には過剰

試験場での第一選択は本解である。(1) は条件 $4=2^2$ から倍率 $2$ の個数へ直接落ち,(2) は単調性と $2^4=16$ により二つの確率だけで期待値が組み上がる。別解2 は閾値が大きい類題でも機械的に適用でき,別解3 は本問の素数倍率という構造を最も強く用いる。参考解1 は最短であるが,閾値 $15$ と時刻 $2,3$ に依存する。参考解2 は答案のための方法ではなく,解法どうしの関係を明らかにするための視点である。


4. 汎用的な探索手順

本問から抽出される,「独立な試行で数を掛けていく過程(乗法過程)」と「停止時刻の期待値」に対する探索手順を述べる。

4.1 意思決定の流れ

  1. 判定条件を分解する。倍数条件は素因数分解して各素数の付値の条件へ,閾値条件は大小(対数)の条件へ翻訳する。本問では $4\mid S_n\iff v_2(S_n)\geqq2$ である。
  2. 1回の試行を,状態への作用によって同値類にまとめる。同じ作用をもつ結果(目 $1,2,4,6$)を一つにし,判定に関係しない区別((1) における $3$ と $5$)も消す。
  3. 停止時刻が現れたら,計算の前に上下界を求める。最も遅く増える列と最も速く増える列から $T_{\min}\leqq T\leqq T_{\max}$ を得る。本問では $2\leqq T\leqq4$ である。
  4. 単調性を確かめる。過程が後戻りしなければ「時刻 $k$ までに到達していない」は「時刻 $k$ に未到達」と一致し,初到達の問題が固定時刻の分布の問題に変わる。
  5. 境界のパターンを探す。継続する集合が下に閉じていれば,極大な継続パターンと極小な終了パターンだけを調べればよい。本問では $k=3$ で $12$ と $18,20$ がこれに当たる。
  6. 積が可換ならば順序を捨て,個数の組で分類してから並べ方の数を掛ける。
  7. 期待値の入口を選ぶ。停止時刻の値が少数なら尾確率の和,状態が再訪されないなら状態占有の和,状態数が多く閾値が大きいなら後ろ向き再帰,分布そのものも必要なら停止時刻の分布を用いる。これらは同じ有限和の異なる足し方である( 5.3 節 )。
  8. 検算する。期待値が上下界の間にあるか,分布の総和が $1$ か,時刻ごとと状態ごとの二通りの和が一致するか,特殊値($n=2$ など)で正しいかを確かめる。

4.2 症状と有効な表現

症状検討する表現・道具本問での例
「$m$ の倍数」という条件素因数分解,$p$ 進付値本解 (1)
判定に必要な情報が粗い状態の打ち切り,同値類への圧縮別解1
停止時刻のとり得る値が少数尾確率の有限和本解 (2)
状態が単調に動き再訪されない状態占有の和別解3
閾値が大きく状態が多い第一歩解析(後ろ向き再帰)別解2
固定時刻の積の大小比較最小倍率による正規化,格子点と直線3.1 節,参考解1
複数の設問が同じ過程から出る多変数母関数による周辺化参考解2

4.3 類題への適用

閾値を一般化しても,状態占有の公式は有限和のまま使える。

一般の閾値に対する期待値

整数 $N\geqq2$ に対し $T_N=\min\lbrace k\geqq0 : S_k\geqq N\rbrace$,$\mathcal{R}_N=\lbrace 2^a3^b5^c : a,b,c\in\mathbb{Z}_{\geqq0},\ 2^a3^b5^c < N\rbrace$ とする。
(i) $\min\lbrace k : 5^k\geqq N\rbrace\leqq T_N\leqq\min\lbrace k : 2^k\geqq N\rbrace$ であり,両端の値は正の確率でとられる。
(ii) 次が成り立つ。
$$ E[T_N]=\sum_{k\geqq0}P(S_k < N)=\sum_{\substack{a,b,c\geqq0\\ 2^a3^b5^c < N}}\frac{(a+b+c)!}{a!\,b!\,c!}\left(\frac23\right)^a\left(\frac16\right)^{b+c}. $$

(i) $2^k\leqq S_k\leqq5^k$ による。倍率がすべて $5$ の列とすべて $2$ の列で,それぞれ左端と右端の値をとる。
(ii) 補題1 , 補題3 , 補題4 の証明で用いたのは,$X_i\geqq2$ による単調性と素因数分解の一意性だけである。閾値 $15$ を $N$ に,$\mathcal{R}$ を $\mathcal{R}_N$ に置き換えれば同じ証明が成り立つ。和は (i) により有限である。

1.6 節 の表はこの公式による。閾値が大きくなると $T_N$ の値の範囲が広がり,尾確率の各項 $P(S_k < N)$ の計算は重くなるが,(ii) の右辺は $\mathcal{R}_N$ の元を列挙するだけで計算できる。$\mathcal{R}_N$ の元の個数は $(\log N)^3$ の程度で増える。
倍数条件についても同じ考え方が適用できる。$2^m\mid S_n$ は $a_n\geqq m$ と同値であるから
$$ P(2^m\mid S_n)=1-\sum_{j=0}^{m-1}\binom{n}{j}\frac{2^j}{3^n} $$
となる。法が二つ以上の素数を含む場合,例えば $12=2^2\cdot3$ では $12\mid S_n\iff$「$a_n\geqq2$ かつ $b_n\geqq1$」であり,包除原理より
$$ P(12\mid S_n)=1-P(a_n\leqq1)-P(b_n=0)+P(a_n\leqq1,\ b_n=0)=1-\frac{2n+1}{3^n}-\left(\frac56\right)^n+\frac{4n+1}{6^n} $$
を得る。ここで $P(a_n\leqq1,\ b_n=0)$ は倍率が $2$ と $5$ だけで $2$ が高々1回の確率 $\left(\frac16\right)^n+n\cdot\frac23\left(\frac16\right)^{n-1}$ である。別解1 の方法では状態を $(\min(a_n,2),\min(b_n,1))$ の6個にとればよい。$n=3$ では $\frac29$ となり,倍率の組 $\lbrace2,2,3\rbrace$ の確率 $3\cdot\left(\frac23\right)^2\cdot\frac16=\frac29$ と一致する。
作問の視点からは,(1) で法に素数を一つだけ含ませれば二項分布になり,二つ以上含ませれば包除または多状態の推移が必要になる。(2) で閾値を $2^{k-1} < N\leqq2^k$ に置けば $T\leqq k$ が保証され,倍率の積を閾値に一致させれば不等号の読みが答に反映される。


5. 発展事項

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

事項高校数学での扱い一般理論
倍数条件素因数 $2$ の個数を数える$p$ 進付値(乗法から加法への準同型)
持ち点の表現$2^a3^b5^c$ と書いて場合分け自由可換モノイド,格子上のランダムウォーク
$E[T]=\sum_kP(T > k)$指示関数の和と期待値の線形性尾和公式(和の順序交換)
状態ごとの漸化式次の1回で場合分け第一歩解析,マルコフ性
状態の確率の和到達確率を足す吸収マルコフ連鎖の基本行列,Green 関数
母関数二項定理,多項定理形式的冪級数環
停止時の関係式扱わないマルチンゲール,任意停止定理,Wald の等式
閾値が大きい場合扱わない更新理論

本解,別解1〜3,3.1 節,3.2 節,参考解1 は左欄の範囲で完結する。右欄は,それらの計算が成り立つ理由と一般化を与える。

5.2 付値と乗法過程の加法化

素数 $p$ の付値 $v_p$ は $v_p(mm')=v_p(m)+v_p(m')$ を満たし,乗法を加法に移す。素因数分解の一意性により,写像 $(a,b,c)\mapsto2^a3^b5^c$ は加法モノイド $\mathbb{Z}_{\geqq0}^3$ から $2,3,5$ が生成する乗法モノイドへの同型であり,後者は自由可換モノイドである。持ち点の過程はこのモノイド上のランダムウォークであり,二つの設問はそれぞれ次の加法的な写像による像に対する閾値の問題である。
$$ \text{(1)}\ \ (a,b,c)\mapsto a\geqq2,\qquad \text{(2)}\ \ (a,b,c)\mapsto a\log2+b\log3+c\log5\geqq\log15. $$
$\log2,\log3,\log5$ は有理数体上一次独立である。実際,整数 $p,q,r$ について $p\log2+q\log3+r\log5=0$ ならば $2^p3^q5^r=1$ となり,素因数分解の一意性から $p=q=r=0$ である。したがって (2) の写像は $\mathbb{Z}^3$ 上で単射であり,持ち点の大きさが状態を決めるという 1.2 節 の事実と整合する。 3.1 節 の正規化は,固定時刻で $a$ を消去して $(b,c)\mapsto b\log\frac32+c\log\frac52$ に落としたものである。

5.3 吸収マルコフ連鎖と基本行列

$\mathcal{R}$ の10個の状態を添字とする行列 $Q$ を,$s'/s\in\lbrace2,3,5\rbrace$ のとき $Q_{s,s'}=P(X_1=s'/s)$,それ以外のとき $Q_{s,s'}=0$ で定める。$(Q^k)_{s,s'}$ は持ち点 $s$ から出発して $k$ 回後に $s'$ にいる確率である(途中の値は $s'$ より小さいので自動的に $\mathcal{R}$ に属する)。状態を小さい順に並べると $Q$ は狭義上三角行列であり,どの状態からも4回後には $16$ 以上となるので $Q^4=O$ である。よって基本行列は有限和
$$ \Gamma=(I-Q)^{-1}=I+Q+Q^2+Q^3 $$
で与えられ,$\Gamma_{s,s'}$ は $s$ から出発したときの $s'$ への期待訪問回数,すなわち到達確率である。状態 $1$ に対応する単位ベクトルを $\boldsymbol{e}$,すべての成分が $1$ のベクトルを $\boldsymbol{j}$ とすると
$$ E[T]=\boldsymbol{e}^{\top}\Gamma\boldsymbol{j}=\sum_{k=0}^{3}\sum_{s\in\mathcal{R}}(Q^k)_{1,s}. $$
(2) の四つの解法は,この同じ量を異なる順序で計算している。

  • 先に $s$ について足す:$\sum_s(Q^k)_{1,s}=P(S_k < 15)=P(T > k)$ となり,本解である。
  • 先に $k$ について足す:$\sum_k(Q^k)_{1,s}=\Gamma_{1,s}=P(V_s)$ となり,別解3 である。
  • $\boldsymbol{t}=\Gamma\boldsymbol{j}$ を連立方程式 $(I-Q)\boldsymbol{t}=\boldsymbol{j}$,すなわち $t_s=1+\sum_{s'}Q_{s,s'}t_{s'}$ の解として求める:$t_s=E_s$ であり,別解2 である。$Q$ が上三角であることが,大きい状態から順に解ける理由である。
  • 脱出確率のベクトル $\boldsymbol{r}=(I-Q)\boldsymbol{j}$ を用いて $P(T=k)=\boldsymbol{e}^{\top}Q^{k-1}\boldsymbol{r}$ とする:3.2 節である。
    一般の吸収マルコフ連鎖では状態の間に閉路があり,$\Gamma$ を得るには逆行列の計算が必要になる。本問では倍率がすべて $1$ より大きいため推移のグラフが閉路をもたず($Q$ が冪零),$\Gamma$ が有限和で書けることが,各解法を初等的にしている。

5.4 形式的冪級数と Green 関数

格子上のランダムウォークについて,出発点から各点への期待訪問回数を Green 関数とよぶ。参考解2 の $G(x,y,z)=\sum_nf^n$ は,原点から出発する本問の歩みの Green 関数の母関数である。各歩みで $a+b+c$ がちょうど $1$ 増えるため,各点の訪問は高々1回であり,Green 関数は到達確率に一致する。
時刻を記録した $H(w)=\sum_kP(T > k)w^k$ からは,期待値だけでなく高次の量も読める。$\sum_{k\geqq0}kP(T > k)=E\left[\frac{T(T-1)}{2}\right]$ であるから $E[T(T-1)]=2H'(1)$ であり,
$$ H'(1)=1+\frac{11}{6}+\frac{14}{9}=\frac{79}{18},\qquad E[T^2]=\frac{79}{9}+\frac{371}{108}=\frac{1319}{108},\qquad V[T]=\frac{1319}{108}-\left(\frac{371}{108}\right)^2=\frac{4811}{11664}. $$
これは 3.2 節の分布から直接計算した $E[T^2]=4\cdot\frac1{12}+9\cdot\frac{43}{108}+16\cdot\frac{14}{27}=\frac{1319}{108}$ と一致する。

5.5 マルチンゲールと Wald の等式

$E[X_1]=2\cdot\frac23+3\cdot\frac16+5\cdot\frac16=\frac83$ であるから,$M_k=S_k\left(\frac38\right)^k$ は
$$ E[M_{k+1}\mid X_1,\ldots,X_k]=M_k\cdot\frac38E[X_{k+1}]=M_k $$
を満たすマルチンゲールである。$T$ は有界な停止時刻であるから,任意停止定理により $E\left[S_T\left(\frac38\right)^T\right]=1$ が成り立つ。
また,$c_T=\sum_{i\geqq1}\boldsymbol{1}_{\lbrace X_i=5\rbrace}\boldsymbol{1}_{\lbrace T\geqq i\rbrace}$ において事象 $\lbrace T\geqq i\rbrace=\lbrace T > i-1\rbrace$ は $X_1,\ldots,X_{i-1}$ だけで決まり $X_i$ と独立であるから,
$$ E[c_T]=\sum_{i\geqq1}\frac16P(T\geqq i)=\frac16E[T] $$
が成り立つ(Wald の等式)。同様に $E[a_T]=\frac23E[T]$,$E[b_T]=\frac16E[T]$ である。証明は本解と同じ尾和の考え方による。
終了時の $(T,S_T)$ の分布は次のとおりである。

$T$$S_T$ の値(確率)
$2$$15\ \left(\frac1{18}\right)$,$25\ \left(\frac1{36}\right)$
$3$$18\ \left(\frac1{18}\right)$,$20\ \left(\frac29\right)$,$27\ \left(\frac1{216}\right)$,$30\ \left(\frac2{27}\right)$,$45\ \left(\frac1{216}\right)$,$50\ \left(\frac1{27}\right)$
$4$$16\ \left(\frac{16}{81}\right)$,$24\ \left(\frac{16}{81}\right)$,$36\ \left(\frac1{27}\right)$,$40\ \left(\frac4{81}\right)$,$60\ \left(\frac1{27}\right)$

この表から $E\left[S_T\left(\frac38\right)^T\right]=1$,$E[a_T]=\frac{371}{162}$,$E[b_T]=E[c_T]=\frac{371}{648}$ が確かめられ,いずれも上の恒等式と $E[T]=\frac{371}{108}$ に整合する。
ただし,これらの恒等式から $E[T]$ を直接求めることはできない。停止時の値 $S_T$ は $15$ から $60$ までばらつき(閾値の越え過ぎ),その分布を知るには結局 $\mathcal{R}$ 上の計算が必要になる。仮に越え過ぎがなく $S_T=15$ であったとしても,得られるのは $E\left[\left(\frac38\right)^T\right]$ であり,$T$ が定数でない限り $E\left[\left(\frac38\right)^T\right]\neq\left(\frac38\right)^{E[T]}$ である(指数関数の狭義凸性)。マルチンゲールと Wald の等式は,本問では検算と構造理解のための道具である。

5.6 更新理論:閾値が大きい場合

$\ell_i=\log X_i$,$L_k=\log S_k=\ell_1+\cdots+\ell_k$ とおくと,$T_N$ は正の増分をもつランダムウォーク $L_k$ が水準 $\log N$ に初めて達する時刻である。閾値を大きくしたときの挙動は更新理論で記述される。

更新理論からの漸近式(引用)

$\ell_1,\ell_2,\ldots$ を独立同分布な正の確率変数とし,その分布は非算術的(ある $h > 0$ について $\ell_1\in h\mathbb{Z}$ が確率 $1$ で成り立つことがない)とする。$\mu=E[\ell_1]$,$\mu_2=E[\ell_1^2] < \infty$,$L_k=\ell_1+\cdots+\ell_k$,$\tau_t=\min\lbrace k : L_k > t\rbrace$ とおく。このとき $t\to\infty$ で
$$ E[\tau_t]=\frac{t}{\mu}+\frac{\mu_2}{2\mu^2}+o(1). $$

本問では $\ell_1\in\lbrace\log2,\log3,\log5\rbrace$ であり, 5.2 節 の一次独立性から,これらの値が共通の $h\mathbb{Z}$ に含まれることはない(含まれれば $\log3/\log2$ が有理数となる)。よって分布は非算術的である。$T_N$ は $L_k\geqq\log N$ で定義されるが,$\tau_t$ との差は $L_k=t$ となる $k$ の個数($0$ または $1$)であり,その期待値は $t\to\infty$ で $0$ に収束する(Blackwell の更新定理より,任意の $h > 0$ について区間 $(t-h,t]$ に入る $L_k$ の個数の期待値は $\frac{h}{\mu}$ に収束する)。したがって
$$ \mu=\frac23\log2+\frac16\log3+\frac16\log5\approx0.91344,\qquad \mu_2\approx0.95318,\qquad \frac{\mu_2}{2\mu^2}\approx0.57119 $$
を用いて $E[T_N]=\dfrac{\log N}{\mu}+0.57119\cdots+o(1)$ が成り立つ。 命題5 による正確な値(小数第4位まで)と比べる。

$N$$E[T_N]$$\frac{\log N}{\mu}+\frac{\mu_2}{2\mu^2}$差
$15$$3.4352$$3.5359$$-0.1007$
$10^3$$8.1540$$8.1335$$+0.0204$
$10^6$$15.7014$$15.6959$$+0.0055$
$10^{12}$$30.8282$$30.8206$$+0.0076$
$10^{24}$$61.0672$$61.0700$$-0.0028$
$10^{40}$$101.4033$$101.4026$$+0.0008$

差は符号を変えながら $0$ に近づく。$N=15$ では誤差が $0.1$ 程度あり,正確な値は有限個の境界の構造で決まる。
増加の速さを表すのは $e^{\mu}=2^{2/3}\cdot15^{1/6}\approx2.493$ であり,平均の倍率 $E[X_1]=\frac83\approx2.667$ より小さい(重み付きの相加・相乗平均の関係)。持ち点の平均 $E[S_k]=\left(\frac83\right)^k$ は倍率 $5$ を多く含むまれな経路によって引き上げられており,典型的な経路の成長は $e^{\mu k}$ の程度である。$\left(\frac83\right)^k=15$ から $T$ を見積もると $k\approx2.76$ となり,実際の $E[T]\approx3.44$ を下回る。

5.7 順序構造と境界

$2^a3^b5^c$ の形の数全体に整除関係で順序を入れると,これは $\mathbb{Z}_{\geqq0}^3$ の成分ごとの順序と同型である。$\mathcal{R}$ はこの順序で下に閉じている($s\mid s'$ かつ $s' < 15$ ならば $s\leqq s' < 15$)。持ち点の列 $S_0\mid S_1\mid S_2\mid\cdots$ は各段で素数倍される飽和鎖であり,$T$ はこのランダムな鎖が $\mathcal{R}$ 内にもつ元の個数,$E[T]$ は各元が鎖に含まれる確率の和である(別解3)。
停止時の値は $\mathcal{R}$ の外側の境界
$$ \partial\mathcal{R}=\lbrace sx : s\in\mathcal{R},\ x\in\lbrace2,3,5\rbrace,\ sx\geqq15\rbrace=\lbrace15,16,18,20,24,25,27,30,36,40,45,50,60\rbrace $$
に属し,これは 5.5 節 の表の値の全体と一致する。固定時刻 $k$ では,継続する $(b,c)$ の集合は下に閉じた集合であり,その極大元(反鎖)だけで決まる。終了する集合は上に閉じ,その極小元で決まる。 補題2 の証明が「$5\cdot2\cdot2$」と「$3\cdot3\cdot2$」の2つの比較で済むのは,この極小元が2個しかないためである。(1) の条件 $a\geqq2$ も上に閉じた集合で,極小元は $a=2$ の1個である。

5.8 歴史的背景

素因数分解の一意性は Euclid『原論』の整数論の命題に起源をもち,Gauss『整数論研究』(1801)で明示的に定式化された。尾和公式と第一歩解析はマルコフ連鎖の基本的手法であり,吸収マルコフ連鎖の基本行列 $(I-Q)^{-1}$ は Kemeny と Snell の『Finite Markov Chains』(1960)で体系化された。停止時刻に関する Wald の等式は Wald(1944)が逐次解析の文脈で与え,マルチンゲールの任意停止定理は Doob の『Stochastic Processes』(1953)で整備された。更新理論は Feller(1941)による更新方程式の研究,Blackwell の更新定理(1948),Smith の鍵更新定理(1950年代)を経て確立され, 定理6 はその帰結である。


6. 最終整理

6.1 全体の構造マップ

  • 倍率への圧縮:目 $1,2,4,6\to2$ 倍,$3\to3$ 倍,$5\to5$ 倍,$S_k=2^{a_k}3^{b_k}5^{c_k}$
      1. $4\mid S_n$
        • $v_2(S_n)=a_n\geqq2$ → 本解(二項分布の余事象)
        • $\min(a_n,2)$ の3状態 → 別解1(漸化式)
        • 結論 $1-\frac{2n+1}{3^n}$
      1. はじめて $15$ 以上
        • 単調性 → $T > k\iff S_k < 15$,$2^4=16$ → $T\in\lbrace2,3,4\rbrace$
        • 境界 $3\cdot5=15$,$12 < 15 < 18,20$ → 継続は $\lbrace2,2,2\rbrace,\lbrace2,2,3\rbrace$ のみ(別証:3.1 節の正規化)
        • 有限の表 $P(S_k=s)$ の足し方
          • 時刻ごと → 本解(尾確率),3.2 節(停止時刻の分布)
          • 状態ごと → 別解3(状態占有)
          • 大きい状態から → 別解2(後ろ向き再帰)
          • 境界直線の取り替え → 参考解1(問題特化)
        • 統一:参考解2(多変数母関数),5.3 節(基本行列)
        • 結論 $\frac{371}{108}$

6.2 数学的教訓

  • 倍数条件は素因数の付値の条件に翻訳する。付値は乗法を加法に変え,判定に無関係な素因数を捨てさせる。
  • 状態は判定に必要な情報まで圧縮する。打ち切り $\min(a_n,2)$ のように,圧縮が推移と両立することを確かめれば漸化式が立つ。
  • 停止時刻は計算の前に上下界を求める。最も遅い列と最も速い列が有限性を与える。
  • 単調な過程では初到達の事象が固定時刻の事象と一致する。これが停止時刻の問題を固定時刻の分布の問題に変える。
  • 閾値問題では,全列挙の前に境界の積(継続する最大と終了する最小)を探す。等号が成り立つ場合は不等号の読みを試している。
  • 期待値の計算は,同じ有限和の足し方の選択である。時刻ごと,状態ごと,後ろから,終了時刻ごとのどれを選ぶかで,計算量と一般性が変わる。
  • 問題特化の短縮は,保存する判定を明示したうえで用いる。閾値を一般化するときは,状態占有の公式と後ろ向き再帰が有効である。
投稿日:12日前
数学の力で現場を変える アルゴリズムエンジニア募集 - Mathlog served by OptHub

この記事を高評価した人

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

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

バッジはありません。

投稿者

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

コメント

他の人のコメント

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