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$ 以上となったときに試行を終了する。終了するまでに試行した回数の期待値を求めよ。
第 $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$ を考えてよい。終了の判定は各時点までの倍率だけで決まるので,実際に行われる試行の結果の分布はこの拡張によって変わらない。以下の記号を用いる。
倍率 $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) は第二段階まで用いる。
(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$ の有限問題となる。
(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$ の二種類だけになる。
$$
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$ 倍)が含まれれば,前者は保たれるが後者は失われる。
以上の構造から,作問の設計は次のように読める(数値設定からの分析であり,出題者の意図についての推定を含む)。
| $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}$ |
| 着目する構造 | 導かれる解法 |
|---|---|
| $2$ 進付値と二項分布 | 本解 (1) |
| 付値の打ち切り(3状態への圧縮) | 別解1 |
| 単調性による $T > k\iff S_k < 15$ と有限化 | 本解 (2),3.2 節 |
| 最小倍率による正規化 | 3.1 節 |
| 第一歩解析(状態からの再帰) | 別解2 |
| 状態の非再訪と素因数分解の一意性 | 別解3 |
| 有限個の格子点を分ける直線の取り替え | 参考解1 |
| 乗法過程の形式的冪級数表示 | 参考解2 |
各試行で持ち点を $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}.
$$
$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}$ |
3.1 節と 3.2 節は本解の特定の段階に対する別証・別の導出,3.3〜3.5 節は高校数学の範囲で完結する別解,3.6 節と 3.7 節は問題特化の変換または大学数学の道具を用いる参考解である。
補題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 節 の表と一致する。
$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)$ を経由しない分だけ短い。
$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$ はこの重複に由来する。
未来の経路を列挙する代わりに,現在の持ち点 $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}$ の元に限るので,大きい方から順に求める。
$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$ である。
試行回数を時間軸で数える代わりに,終了前に通過する $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 節 ),本解と同一の量を別の順序で足していることが確認できる。
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$ が継続側に移る)。この限定を明示したうえで用いる問題特化の圧縮である。
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 が同じ係数の異なる読み方であることを一つの代数的対象で示す。
以下は独立の解法とは数えず,既出の解法の表現違いまたは部分的な短縮として扱う。
| 解法 | 対象 | 主に利用する構造 | 範囲 | 長所 | 注意点 |
|---|---|---|---|---|---|
| 本解 | (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 は答案のための方法ではなく,解法どうしの関係を明らかにするための視点である。
本問から抽出される,「独立な試行で数を掛けていく過程(乗法過程)」と「停止時刻の期待値」に対する探索手順を述べる。
| 症状 | 検討する表現・道具 | 本問での例 |
|---|---|---|
| 「$m$ の倍数」という条件 | 素因数分解,$p$ 進付値 | 本解 (1) |
| 判定に必要な情報が粗い | 状態の打ち切り,同値類への圧縮 | 別解1 |
| 停止時刻のとり得る値が少数 | 尾確率の有限和 | 本解 (2) |
| 状態が単調に動き再訪されない | 状態占有の和 | 別解3 |
| 閾値が大きく状態が多い | 第一歩解析(後ろ向き再帰) | 別解2 |
| 固定時刻の積の大小比較 | 最小倍率による正規化,格子点と直線 | 3.1 節,参考解1 |
| 複数の設問が同じ過程から出る | 多変数母関数による周辺化 | 参考解2 |
閾値を一般化しても,状態占有の公式は有限和のまま使える。
整数 $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}.
$$
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$ が保証され,倍率の積を閾値に一致させれば不等号の読みが答に反映される。
| 事項 | 高校数学での扱い | 一般理論 |
|---|---|---|
| 倍数条件 | 素因数 $2$ の個数を数える | $p$ 進付値(乗法から加法への準同型) |
| 持ち点の表現 | $2^a3^b5^c$ と書いて場合分け | 自由可換モノイド,格子上のランダムウォーク |
| $E[T]=\sum_kP(T > k)$ | 指示関数の和と期待値の線形性 | 尾和公式(和の順序交換) |
| 状態ごとの漸化式 | 次の1回で場合分け | 第一歩解析,マルコフ性 |
| 状態の確率の和 | 到達確率を足す | 吸収マルコフ連鎖の基本行列,Green 関数 |
| 母関数 | 二項定理,多項定理 | 形式的冪級数環 |
| 停止時の関係式 | 扱わない | マルチンゲール,任意停止定理,Wald の等式 |
| 閾値が大きい場合 | 扱わない | 更新理論 |
本解,別解1〜3,3.1 節,3.2 節,参考解1 は左欄の範囲で完結する。右欄は,それらの計算が成り立つ理由と一般化を与える。
素数 $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$ に落としたものである。
$\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) の四つの解法は,この同じ量を異なる順序で計算している。
格子上のランダムウォークについて,出発点から各点への期待訪問回数を 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}$ と一致する。
$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 の等式は,本問では検算と構造理解のための道具である。
$\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$ を下回る。
$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個である。
素因数分解の一意性は 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 はその帰結である。