期待値の漸化式と停止

同義語：停止までの回数の期待値expected hitting time

概要

前提知識: 確率漸化式と定常分布, 期待値の線形性と数え上げ, 反復試行の確率, 確率の定義と条件付き確率

高校での出発点：1 の目が出るまで何回振るか

さいころを、1 の目が出るまで振り続ける。1 の目が初めて出るのが何回目かを $T$ とする。$T$ は $1,2,3,\ldots$ のどの値もとりうるが、平均すると何回振ることになるだろうか。

分布を求めてから期待値を計算する

$T=n$ となるのは、1 回目から $n-1$ 回目まで 1 以外の目が出て、$n$ 回目に 1 の目が出るときである。各回は独立なので（反復試行の確率）
$$ P(T=n)=\left(\frac56\right)^{n-1}\cdot\frac16\qquad(n=1,2,3,\ldots) $$
である。$P(T=1)=\dfrac16$、$P(T=2)=\dfrac5{36}$、$P(T=3)=\dfrac{25}{216}$、$P(T=4)=\dfrac{125}{1296}$ と、少しずつ小さくなる。期待値は無限個の項の和
$$ E[T]=1\cdot\frac16+2\cdot\frac56\cdot\frac16+3\cdot\left(\frac56\right)^2\cdot\frac16+\cdots=\sum_{n=1}^{\infty}n\left(\frac56\right)^{n-1}\frac16 $$
で、この和は $6$ になる。ただし、$\sum nx^{n-1}$ の形の和を求めるには、等比数列の和の公式を少し工夫して使う必要がある（下の lem-evr-tail の後で別の方法で確かめる）。

1 の目が初めて出る回 T の分布。棒の高さは n とともに 5/6 倍ずつ小さくなり、期待値 6 の位置を破線で示す
図 1 のとおり、いちばん起こりやすいのは $T=1$ だが、$T$ が 10 や 20 になることもあり、その長い裾が期待値を $6$ まで押し上げている。
分布をすべて求めなくても、期待値だけなら次のように 1 行で求まる。

最初の 1 回で場合を分ける

求める期待値を $E$ とする。1 回目を振ると、次の 2 つの場合がある。

確率 $\dfrac16$ で 1 の目が出る。このとき振った回数は $1$ で終わりである。
確率 $\dfrac56$ で 1 以外の目が出る。このとき 1 回を使ったうえで、状況は最初と同じにもどる。ここから先に振る回数の期待値は、また $E$ である。
したがって
$$ E=\frac16\cdot1+\frac56\cdot(1+E)=1+\frac56E $$
となる。両辺から $\dfrac56E$ を引くと $\dfrac16E=1$ なので
$$ \boxed{E=6} $$
である。

ex-evr-die-first-step の計算は短いが、2 つのことを黙って使っている。1 つは「$E$ が有限の値である」ことで、もし $E$ が無限大なら $E=1+\dfrac56E$ から何も言えない。もう 1 つは「1 回目の後に状況が最初と同じにもどれば、そこから先の期待値もまた $E$ である」ことである。この記事では、この 2 つをきちんと確かめ、同じ方法を状態が 3 つ以上ある場合に広げる。答える問いは次の 3 つである。

止まるまでの回数の期待値は、いつ有限か。→ thm-evr-finite
「最初の 1 歩で分ける」式はいつ正しく、その解はただ 1 つか。→ thm-evr-first-step

硬貨を投げて「表表」が出るまでと「表裏」が出るまでの回数の期待値は、同じか。→ ex-evr-hh-ht

高校の計算	この記事の言葉	大学の言葉
「1 以外の目が出た」「表が 1 回出た」などの途中の様子	状態	Markov 連鎖の状態
1 の目が出たら終わり	目標の状態に着いたら止まる	吸収状態、停止時刻
$E=1+\frac56E$	最初の 1 歩で分けた連立 1 次方程式	$(I-Q)\boldsymbol t=\boldsymbol 1$
裏が続いても、いずれは表が出る	止まる確率は $1$	吸収の確率は $1$

状態と、止まるまでの回数

さいころの例では、途中の様子は「まだ 1 の目が出ていない」の 1 通りしかなかった。硬貨で「表表」を待つ場合は、「直前が表だったか」によって次に止まる確率が変わるので、途中の様子を 2 通りに分けて覚えておく必要がある。この「覚えておく途中の様子」を状態と呼ぶ。状態の間を確率的に移る仕組みは確率漸化式と定常分布の推移行列と同じである。

止まるまでの回数

有限個の状態の集合 $S$ と、各状態 $i,j$ について $i$ から $j$ へ移る確率 $p_{ij}$ が与えられているとする。$p_{ij}\ge0$ で、各 $i$ について $\sum_{j\in S}p_{ij}=1$ である（$(p_{ij})$ は確率行列）。$S$ の空でない部分集合 $Z$ を決め、$Z$ の状態を 目標の状態 と呼ぶ。
状態 $i$ から出発し、各回、今の状態だけで決まる確率で次の状態に移る。状態の列 $i=s_0,s_1,\ldots,s_n$ が起こる確率を
$$ p_{s_0s_1}\,p_{s_1s_2}\cdots p_{s_{n-1}s_n} $$
とする。初めて目標の状態に着いた回を $T$ とし、止まるまでの回数 という（$i\in Z$ なら $T=0$）。$i\notin Z$ のとき、

$P_i(T=n)$ は、$s_1,\ldots,s_{n-1}\notin Z$、$s_n\in Z$ となる長さ $n$ の列の確率の和、
$P_i(T>n)$ は、$s_1,\ldots,s_n$ がどれも $Z$ にない長さ $n$ の列の確率の和
とする（$P_i(T>0)=1$）。止まるまでの回数の期待値 を
$$ E_i=\sum_{n=1}^{\infty}n\,P_i(T=n) $$
で定める。右辺は $0$ 以上の数の和なので、部分和は増えていき、有限の値に近づくか、限りなく大きくなるかのどちらかである。後者のとき $E_i=\infty$ と書く。また、$P_i(T>n)$ が $n\to\infty$ で $0$ に近づかないとき（いつまでも止まらない確率が正のとき）も $E_i=\infty$ とする。$i\in Z$ なら $E_i=0$ とする。

列の確率の決め方は、確率漸化式と定常分布の Markov 連鎖の定義と同じである。「次の状態が今の状態だけで決まる」という仮定（Markov 性）のもとで、確率を掛けていく。

硬貨で「表表」と「表裏」を待つ

表と裏が $\dfrac12$ ずつの硬貨を投げ続ける。
(1) 「表表」（表が 2 回続けて出る）を待つ。状態を「始め」（直前が裏か、まだ投げていない）、「表」（直前が表で、まだ止まっていない）、「表表」（止まった）の 3 つにする。「始め」からは、表なら「表」へ、裏なら「始め」のままである。「表」からは、表なら「表表」へ、裏なら「始め」へもどる。目標は $Z=\{\text{表表}\}$ である。
(2) 「表裏」（表の直後に裏）を待つ。状態は「始め」「表」「表裏」の 3 つである。「始め」からの動きは (1) と同じである。「表」からは、裏なら「表裏」へ進み、表なら「表」のままである。直前が表であることは変わらないからである。
(1) で $T=3$ となる列は「裏表表」の 1 つだけで、状態は始め → 始め → 表 → 表表と動く。その確率は $\dfrac12\cdot\dfrac12\cdot\dfrac12=\dfrac18$ である。

「表表」を待つときの状態の移り方。表のあとの裏で「始め」にもどる

「表裏」を待つときの状態の移り方。表のあとの表では「表」にとどまる

図 2 と図 3 の違いは「表」の状態からの失敗の行き先だけである。「表表」では、表の後に裏が出ると振り出しの「始め」にもどる。「表裏」では、表の後に表が出ても「表」にとどまり、進んだ分を失わない。この違いが期待値の差になることを ex-evr-hh-ht で確かめる。
$P_i(T=n)$ と $P_i(T>n)$ の間には、次の関係がある。$s_1,\ldots,s_{n-1}\notin Z$ となる長さ $n-1$ の列に 1 歩を付け足すと、行き先が $Z$ に入るか入らないかのどちらかである。行き先の確率の和は $\sum_jp_{s_{n-1}j}=1$ なので
$$ P_i(T>n-1)=P_i(T=n)+P_i(T>n)\qquad(n\ge1) $$
が成り立つ。特に $P_i(T>n)$ は $n$ とともに増えない。

期待値を「まだ止まっていない確率」の和で書く

$i\notin Z$ とし、$a_n=P_i(T>n)$ とおく。和 $\sum_{n=0}^{\infty}a_n$ が有限の値 $A$ に近づくならば、$E_i$ も有限で
$$ E_i=\sum_{n=0}^{\infty}P_i(T>n)=A $$
である。

要点：$P_i(T=n)=a_{n-1}-a_n$ を使って部分和を並べかえると $\sum_{n=1}^{N}nP_i(T=n)=a_0+a_1+\cdots+a_{N-1}-Na_N$ となる。$a_n$ は増えないので $Na_{2N}\le a_N+\cdots+a_{2N-1}$ で、右辺は収束する和の先の部分だから $0$ に近づく。よって $Na_N\to0$ で、部分和は $A$ に近づく。

詳しい証明を開く

段 1（部分和の書きかえ）。上の関係から $P_i(T=n)=a_{n-1}-a_n$ である。これを使うと、$N\ge1$ について

$$\sum_{n=1}^{N}n(a_{n-1}-a_n)=(a_0-a_1)+2(a_1-a_2)+\cdots+N(a_{N-1}-a_N)=a_0+a_1+\cdots+a_{N-1}-Na_N$$

である（$a_k$ の係数は $(k+1)-k=1$ で、最後の $a_N$ だけ $-N$ が残る）。

段 2（$Na_N$ が $0$ に近づく）。$a_n$ は増えないので、$N\le n\le2N-1$ の $N$ 個の項はどれも $a_{2N}$ 以上である。よって

$$0\le N\,a_{2N}\le a_N+a_{N+1}+\cdots+a_{2N-1}$$

である。右辺は収束する和 $\sum a_n$ の $N$ 番目から先の一部なので、$N\to\infty$ で $0$ に近づく。したがって $2N\,a_{2N}\to0$ である。奇数番目も $0\le(2N+1)a_{2N+1}\le(2N+1)a_{2N}=2N\,a_{2N}+a_{2N}\to0$ となる。

段 3（結論）。段 1 の式で $N\to\infty$ とすると、右辺は $A-0=A$ に近づく。左辺は $E_i$ の部分和なので、$E_i=A$ である。$\square$

さいころの期待値をもう一度

ex-evr-die-series では $P(T>n)$ は「$n$ 回続けて 1 以外の目が出る確率」で、$\left(\dfrac56\right)^n$ である。公比 $\dfrac56$ の無限等比級数なので
$$ \sum_{n=0}^{\infty}\left(\frac56\right)^n=\frac1{1-\frac56}=6 $$
で、lem-evr-tail により $E[T]=6$ である。ex-evr-die-first-step の答えと一致する。

「表表」と「表裏」のまだ止まっていない確率

ex-evr-states で「始め」から出発すると、$P(T>n)$ は次のとおりである。

$n$	$0$	$1$	$2$	$3$	$4$	$5$	$6$
「表表」	$1$	$1$	$\frac34$	$\frac58$	$\frac12$	$\frac{13}{32}$	$\frac{21}{64}$
「表裏」	$1$	$1$	$\frac34$	$\frac12$	$\frac5{16}$	$\frac3{16}$	$\frac7{64}$

「始め」から出発して $T>n$ となるのは、最初の $n$ 回の表裏の列が、待っている並びを含まないときである。「表裏」の方が早く $0$ に近づく。

数え方と一般の $n$ での式を開く

「表表」の $n=3$ では、長さ 3 の表裏の列 8 通りのうち、表表を含まないものは裏裏裏・裏裏表・裏表裏・表裏裏・表裏表の 5 通りなので $\dfrac58$ である。「表裏」の $n=3$ では、表裏を含まないのは「裏が続いた後に表が続く」形の裏裏裏・裏裏表・裏表表・表表表の 4 通りなので $\dfrac48=\dfrac12$ である。

「表裏」を含まない長さ $n$ の列は、裏が $k$ 個続いた後に表が $n-k$ 個続く形（$k=0,1,\ldots,n$）の $n+1$ 通りなので、$P(T>n)=\dfrac{n+1}{2^n}$ である。「表表」を含まない長さ $n$ の列の個数を $c_n$ とすると、最後が裏なら残りの長さ $n-1$ の部分が条件を満たせばよく、最後が表ならその前は裏で、残りの長さ $n-2$ の部分が条件を満たせばよいので $c_n=c_{n-1}+c_{n-2}$（$c_0=1$、$c_1=2$）である。$c_n$ は Fibonacci 数 $1,1,2,3,5,8,\ldots$ の $n+2$ 番目で、$P(T>n)=\dfrac{c_n}{2^n}$ である。

主定理 1：止まる確率は $1$ で、期待値は有限

ex-evr-die-first-step で黙って使った「$E$ が有限」を確かめる。さいころでは、どの回にも確率 $\dfrac16$ で止まるので、$n$ 回続けて止まらない確率は $\left(\dfrac56\right)^n$ で、急速に小さくなる。「表表」を待つ場合は、1 回ごとに止まる確率が一定ではない（「始め」からは 1 回では止まれない）。そこで何回かをひとまとめにして考える。

止まることと期待値が有限であること

def-evr-stop の設定で、ある正の整数 $k$ と正の数 $\delta$ があって、目標でないどの状態 $i$ から出発しても
$$ P_i(T\le k)\ge\delta\qquad\text{つまり}\qquad P_i(T>k)\le1-\delta $$
が成り立つとする。このとき、目標でないどの状態 $i$ と、どの $m=0,1,2,\ldots$ についても
$$ P_i(T>mk)\le(1-\delta)^m $$
であり、$E_i$ は有限で
$$ E_i\le\frac k\delta $$
である。特に $P_i(T>n)\to0$（$n\to\infty$）で、止まる確率は $1$ である。

方針：$k$ 回ずつに区切り、「$k$ 回の区切りの中で止まらない確率は $1-\delta$ 以下」を $m$ 回くり返して使う。
段 1（$m$ についての帰納法）。$m=0$ では $P_i(T>0)=1=(1-\delta)^0$ である。$P_i(T>mk)\le(1-\delta)^m$ がすべての $i\notin Z$ で成り立つとする。$P_i(T>(m+1)k)$ は、$s_1,\ldots,s_{(m+1)k}$ がどれも $Z$ にない列の確率の和である。この列を、前半の $s_0,\ldots,s_{mk}$ と、$s_{mk}$ から始まる後半の $k$ 歩に分ける。前半の列を 1 つ固定して、後半の $k$ 歩について先に確率を足すと、後半の和は「状態 $s_{mk}$ から出発して $k$ 回のうちに止まらない確率」$P_{s_{mk}}(T>k)$ になる。$s_{mk}\notin Z$ なので、仮定からこれは $1-\delta$ 以下である。よって
$$ P_i(T>(m+1)k)=\sum_{\text{前半の列}}(\text{前半の列の確率})\times P_{s_{mk}}(T>k)\le(1-\delta)\sum_{\text{前半の列}}(\text{前半の列の確率})=(1-\delta)P_i(T>mk) $$
である。帰納法の仮定から右辺は $(1-\delta)^{m+1}$ 以下である。
段 2（和を上から押さえる）。$a_n=P_i(T>n)$ は $n$ とともに増えないので、$mk\le n\le mk+k-1$ の $k$ 個の $n$ では $a_n\le a_{mk}\le(1-\delta)^m$ である。したがって、$M\ge1$ について
$$ \sum_{n=0}^{Mk-1}a_n\le k\sum_{m=0}^{M-1}(1-\delta)^m=k\cdot\frac{1-(1-\delta)^M}{\delta}\le\frac k\delta $$
である。$a_n\ge0$ なので部分和 $\sum_{n=0}^{N}a_n$ は $N$ とともに増え、しかも $\dfrac k\delta$ を超えない（どの $N$ も、ある $Mk-1$ 以下である）。上に有界な増加数列は収束するので、$\sum_{n=0}^{\infty}a_n$ は $\dfrac k\delta$ 以下の有限の値 $A$ に近づく。
段 3（結論）。lem-evr-tail により $E_i=A\le\dfrac k\delta$ である。また $0\le a_{mk}\le(1-\delta)^m\to0$ で、$a_n$ は増えないので $a_n\to0$ である。$n$ 回のうちに止まる確率は $1-a_n$ なので、$1$ に近づく。$\square$

主定理 1 を当てはめる

さいころでは $k=1$、$\delta=\dfrac16$ とできる。上界は $E\le\dfrac{1}{1/6}=6$ で、実際の値 $6$ と等しい。
「表表」を待つ場合、「始め」からは 2 回のうちに止まるのは「表表」の $\dfrac14$、「表」からは 2 回のうちに止まるのは 1 回目に表が出る場合だけで $\dfrac12$ である（1 回目に裏が出ると「始め」にもどり、2 回目には止まれない）。どちらも $\dfrac14$ 以上なので $k=2$、$\delta=\dfrac14$ とでき、$P(T>2m)\le\left(\dfrac34\right)^m$、$E\le\dfrac2{1/4}=8$ である。実際の値は $6$（ex-evr-hh-ht）で、上界は正しいが等号ではない。

「表表」を待つときの P(T > n)（青）と、主定理 1 の上界（赤の破線）。n が 2 増えるごとに上界は 3/4 倍になり、青の点は上界を超えない
主定理 1 の仮定は、状態が有限個なら「どの状態からも目標にたどり着ける道がある」ことと同じである。

目標にたどり着ける道があれば仮定が成り立つ

状態の個数を $r$ とする。目標でないどの状態 $i$ からも、確率が正の列 $i=s_0,s_1,\ldots,s_\ell$ で $s_\ell\in Z$ となるものがあるとする。このとき thm-evr-finite の仮定が $k=r$ で成り立つ。

要点：各状態から目標に着く最も短い列を選ぶと、同じ状態を 2 度通らないので長さは $r$ より小さい。その列の確率の最小値を $\delta$ とすればよい。

詳しい証明を開く

状態 $i\notin Z$ ごとに、$Z$ に着く確率が正の列のうち長さ $\ell$ が最も短いものを 1 つ選ぶ。この列は、最後の $s_\ell$ より前に $Z$ に入らない（入れば、そこで切った列がもっと短い）。また同じ状態を 2 度通らない（2 度通れば、その間を取り除いた列がもっと短く、確率も正のままである）。よって列の状態は互いに異なり、$\ell+1\le r$、つまり $\ell\le r-1< r$ である。この列が起こる確率を $\delta_i>0$ とすると、$P_i(T\le r)\ge P_i(T=\ell)\ge\delta_i$ である。$\delta$ を $\delta_i$（$i\notin Z$）の最小値とすれば、$\delta>0$ で、どの $i\notin Z$ でも $P_i(T\le r)\ge\delta$ である。$\square$

主定理 2：最初の 1 歩で分ける

ex-evr-die-first-step の式 $E=1+\dfrac56E$ を、状態がいくつあっても使える形にする。

最初の 1 歩で分ける式

thm-evr-finite の仮定のもとで、止まるまでの回数の期待値 $E_i$（$i\in S$）は
$$ E_z=0\quad(z\in Z),\qquad E_i=1+\sum_{j\in S}p_{ij}E_j\quad(i\notin Z) $$
を満たす。さらに、状態ごとの未知数 $x_i$（$i\in S$）についての連立 1 次方程式
$$ x_z=0\quad(z\in Z),\qquad x_i=1+\sum_{j\in S}p_{ij}x_j\quad(i\notin Z) $$
の解はただ 1 組で、それは $x_i=E_i$ である。

式の意味は ex-evr-die-first-step と同じである。1 歩目に確率 $p_{ij}$ で状態 $j$ に移り、1 回を使ったうえで、そこから先は「状態 $j$ から出発した場合」と同じになる。証明では、この言葉どおりの計算を、列の確率の和として書く。

段 1（1 歩目で列を分ける）。$i\notin Z$ とする。$T=1$ となるのは $s_1\in Z$ のときなので $P_i(T=1)=\sum_{j\in Z}p_{ij}$ である。$n\ge2$ のとき、$T=n$ となる列 $i,s_1,\ldots,s_n$ では $s_1=j\notin Z$ で、残りの $j=s_1,s_2,\ldots,s_n$ は「$j$ から出発して $n-1$ 回目に初めて $Z$ に着く列」である。列の確率は $p_{ij}\times(\text{残りの列の確率})$ なので、$j$ ごとにまとめて
$$ P_i(T=n)=\sum_{j\notin Z}p_{ij}\,P_j(T=n-1)\qquad(n\ge2) $$
である。
段 2（止まる確率は $1$）。$j\notin Z$ について、def-evr-stop の後の関係 $P_j(T>m-1)=P_j(T=m)+P_j(T>m)$ を $m=1,\ldots,M$ で足すと $\sum_{m=1}^{M}P_j(T=m)=1-P_j(T>M)$ である。thm-evr-finite により $P_j(T>M)\to0$ なので
$$ \sum_{m=1}^{\infty}P_j(T=m)=1 $$
である。
段 3（期待値の式）。thm-evr-finite により $E_j$ はどれも有限である。段 1 を使い、$n=m+1$ とおきかえると
$$ E_i=1\cdot P_i(T=1)+\sum_{n=2}^{\infty}n\sum_{j\notin Z}p_{ij}P_j(T=n-1)=\sum_{j\in Z}p_{ij}+\sum_{j\notin Z}p_{ij}\sum_{m=1}^{\infty}(m+1)P_j(T=m) $$
である（$j$ についての和は有限個なので、無限和と順番を入れかえてよい）。段 2 と $E_j$ の定義から
$$ \sum_{m=1}^{\infty}(m+1)P_j(T=m)=\sum_{m=1}^{\infty}mP_j(T=m)+\sum_{m=1}^{\infty}P_j(T=m)=E_j+1 $$
なので
$$ E_i=\sum_{j\in Z}p_{ij}+\sum_{j\notin Z}p_{ij}(E_j+1)=\underbrace{\sum_{j\in S}p_{ij}}_{=1}+\sum_{j\notin Z}p_{ij}E_j=1+\sum_{j\in S}p_{ij}E_j $$
である。最後の等号では $E_z=0$（$z\in Z$）を使って、和を $S$ 全体に広げた。
段 4（解はただ 1 組）。$(x_i)$ と $(y_i)$ がどちらも連立 1 次方程式の解だとし、差を $d_i=x_i-y_i$ とおく。方程式を引き算すると、定数 $1$ が消えて
$$ d_z=0\quad(z\in Z),\qquad d_i=\sum_{j\in S}p_{ij}d_j\quad(i\notin Z) $$
である。thm-evr-finite の仮定から、目標でないどの状態 $i$ でも $P_i(T\le k)\ge\delta>0$ なので、$i$ から確率が正の列で $Z$ にたどり着ける。よって下の lem-evr-max が使えて、$d_i$ はすべて $0$ で、$x_i=y_i$ である。段 3 により $(E_i)$ は解の 1 つなので、ただ 1 つの解は $(E_i)$ である。$\square$

最大値の原理

cor-evr-reach のように、目標でないどの状態からも、確率が正の列で $Z$ にたどり着けるとする。数 $d_i$（$i\in S$）が
$$ d_z=0\quad(z\in Z),\qquad d_i=\sum_{j\in S}p_{ij}d_j\quad(i\notin Z) $$
を満たすならば、すべての $i$ で $d_i=0$ である。

要点：$d_i$ は $d_j$ たちの重み付きの平均なので、$d$ が最大値をとる目標でない状態では、そこから確率が正で移れる状態もすべて最大値をとる（平均が最大値に等しければ、平均される値はすべて最大値）。目標にたどり着く列に沿って最大値が伝わり、目標では値が $0$ なので、最大値は $0$ 以下である。$-d_i$ に同じ議論を使うと最小値は $0$ 以上である。

詳しい証明を開く

段 1（重み付きの平均）。$p_{ij}\ge0$、$\sum_jp_{ij}=1$ なので、$i\notin Z$ での式は「$d_i$ は $d_j$ たちの重み付きの平均」という意味である。$d_j$ の最大値を $M$ とし、$d_i=M$ となる $i\notin Z$ があるとすると

$$0=M-d_i=\sum_{j\in S}p_{ij}M-\sum_{j\in S}p_{ij}d_j=\sum_{j\in S}p_{ij}(M-d_j)$$

である。右辺の各項は $0$ 以上なので、どの項も $0$ である。つまり $p_{ij}>0$ となるどの $j$ でも $d_j=M$ である。平均が最大値に等しければ、平均される値（重みが正のもの）はすべて最大値である。

段 2（最大値は $0$ 以下）。$M>0$ と仮定する。$d_z=0< M$ なので、$d_i=M$ となる $i$ は $Z$ にない。この $i$ から $Z$ にたどり着く確率が正の列 $i=s_0,s_1,\ldots,s_\ell$ で、$Z$ に初めて入るのが $s_\ell$ であるものをとる。段 1 を $s_0$ に使うと $p_{s_0s_1}>0$ なので $d_{s_1}=M$ である。$s_1\notin Z$ なら同じく $d_{s_2}=M$ で、これを続けると $d_{s_\ell}=M$ になる。ところが $s_\ell\in Z$ なので $d_{s_\ell}=0< M$ で、矛盾である。よって $M\le0$ である。

段 3（最小値は $0$ 以上）。$-d_i$ も同じ式を満たすので、段 2 から $-d_i$ の最大値も $0$ 以下である。つまり $d_i$ の最小値は $0$ 以上である。段 2 と合わせて、すべての $d_i$ は $0$ である。$\square$

主定理 2 により、期待値を求める問題は「状態を決める → 最初の 1 歩で分けた式を立てる → 連立 1 次方程式を解く」という手順になる。未知数が 1 つなら ex-evr-die-first-step のように 1 行で済む。

例：表表と表裏、おまけ集め、正方形の上の歩き

「表表」は 6 回、「表裏」は 4 回

ex-evr-states の状態で、「始め」と「表」から出発したときの期待値を $E_0$、$E_1$ とする。目標での値は $0$ である。どちらの場合も、状態が有限個で、どの状態からも目標にたどり着けるので、cor-evr-reach と thm-evr-first-step が使える。
(1) 「表表」を待つ。「始め」からは確率 $\dfrac12$ ずつで「表」と「始め」に、「表」からは確率 $\dfrac12$ ずつで「表表」と「始め」に移るので
$$ E_0=1+\frac12E_1+\frac12E_0,\qquad E_1=1+\frac12\cdot0+\frac12E_0 $$
である。2 つ目の式を 1 つ目に代入すると
$$ E_0=1+\frac12\left(1+\frac12E_0\right)+\frac12E_0=\frac32+\frac34E_0 $$
で、$\dfrac14E_0=\dfrac32$ より $E_0=6$、$E_1=1+3=4$ である。
(2) 「表裏」を待つ。「表」からは確率 $\dfrac12$ ずつで「表裏」と「表」に移るので
$$ E_0=1+\frac12E_1+\frac12E_0,\qquad E_1=1+\frac12\cdot0+\frac12E_1 $$
である。2 つ目の式から $\dfrac12E_1=1$、$E_1=2$ で、1 つ目の式から $\dfrac12E_0=1+\dfrac12\cdot2=2$、$E_0=4$ である。
どちらの並びも、2 回続けて投げたときに出る確率は $\dfrac14$ で同じである。それでも待つ回数の期待値は $6$ と $4$ で違う。違いは、図 2・図 3 で見た「表」の状態からの失敗の行き先にある。(1) の $E_1=1+\dfrac12E_0$ では失敗すると $E_0=6$ の「始め」にもどるが、(2) の $E_1=1+\dfrac12E_1$ では失敗しても $E_1=2$ の「表」にとどまる。

同じ手順で解ける例をもう 2 つ見る。どちらも状態が有限個で、どの状態からも目標にたどり着けるので、主定理 2 が使える。

3 種類のおまけを全部集める

お菓子を 1 個買うごとに、3 種類のおまけのどれかが $\dfrac13$ ずつの確率で、ほかの回とは独立に 1 つ付いてくる。全種類がそろうまでに買う個数の期待値を求める。
状態を「もっている種類の数」$0,1,2,3$ とし、目標を $3$ とする。$c$ 種類もっているとき、次の 1 個が新しい種類である確率は $\dfrac{3-c}3$ である。$c$ 種類から出発したときの期待値を $E_c$ とすると、$E_3=0$ と
$$ E_2=1+\frac23E_2+\frac13\cdot0,\qquad E_1=1+\frac13E_1+\frac23E_2,\qquad E_0=1+E_1 $$
である。1 つ目から $\dfrac13E_2=1$、$E_2=3$ である。2 つ目から $\dfrac23E_1=1+2=3$、$E_1=\dfrac92$ である。3 つ目から
$$ \boxed{E_0=\frac{11}2} $$
である。これは $1+\dfrac32+3$ とも書ける。$c$ 種類から $c+1$ 種類に進むまでの期待値 $\dfrac3{3-c}$（$c=0,1,2$）の和である。

ex-evr-coupon の答えを「種類が 1 つ増えるまでの回数の期待値の和」として求める方法は、期待値の期待値の線形性による計算と同じである。ここでは、状態を「もっている種類の数」にとって最初の 1 歩で分けた。

正方形の頂点を歩く

正方形の頂点の上を、1 回ごとに隣の 2 頂点のどちらかへ $\dfrac12$ ずつの確率で移る点がある。ある頂点から出発して、向かい合う頂点に初めて着くまでの回数の期待値は $4$ である。状態を「目標の頂点までの辺の数」$0,1,2$ にとると、未知数 2 つの連立 1 次方程式 $E_2=1+E_1$、$E_1=1+\dfrac12E_2$ になる。

式の立て方と解き方を開く

出発点は距離 $2$ で、隣の頂点はどちらも距離 $1$ なので、$2$ からは必ず $1$ に移る。$1$ からは、確率 $\dfrac12$ で目標 $0$ に、確率 $\dfrac12$ で $2$ に移る。よって $E_2=1+E_1$、$E_1=1+\dfrac12\cdot0+\dfrac12E_2$ である。1 つ目を 2 つ目に代入すると $E_1=1+\dfrac12(1+E_1)$、$\dfrac12E_1=\dfrac32$ で、$E_1=3$、$E_2=4$ である。4 つの頂点を状態にとる代わりに、目標までの距離でまとめたので、未知数が 2 つで済んだ。

ここまでの例をまとめる。

例	目標でない状態	最初の 1 歩で分けた式	出発点の期待値
さいころで 1 の目	1 つ	$E=1+\frac56E$	$6$
硬貨で「表表」	始め、表	$E_0=1+\frac12E_1+\frac12E_0$、$E_1=1+\frac12E_0$	$6$
硬貨で「表裏」	始め、表	$E_0=1+\frac12E_1+\frac12E_0$、$E_1=1+\frac12E_1$	$4$
3 種類のおまけ	$0,1,2$ 種類	$E_c=1+\frac c3E_c+\frac{3-c}3E_{c+1}$	$\frac{11}2$
正方形の向かいの頂点	距離 $1,2$	$E_2=1+E_1$、$E_1=1+\frac12E_2$	$4$

立方体の頂点を歩く

立方体の頂点の上を、1 回ごとに隣の 3 頂点のどれかへ $\dfrac13$ ずつの確率で移る点がある。ある頂点から出発して、中心について反対側の頂点に初めて着くまでの回数の期待値を求めよ。

解答を開く

状態を目標までの辺の数 $0,1,2,3$ とする。距離 $3$ の頂点の隣はどれも距離 $2$、距離 $2$ の頂点の隣は距離 $1$ が 2 つと距離 $3$ が 1 つ、距離 $1$ の頂点の隣は距離 $0$ が 1 つと距離 $2$ が 2 つである。よって $E_0=0$ と

$$E_3=1+E_2,\qquad E_2=1+\frac23E_1+\frac13E_3,\qquad E_1=1+\frac13\cdot0+\frac23E_2$$

である。1 つ目を 2 つ目に代入すると $E_2=\dfrac43+\dfrac23E_1+\dfrac13E_2$、つまり $E_2=2+E_1$ である。これを 3 つ目に代入すると $E_1=1+\dfrac23(2+E_1)$ で、$\dfrac13E_1=\dfrac73$、$E_1=7$ である。よって $E_2=9$、$E_3=10$ で、答えは $10$ 回である。8 つの頂点を別々の状態にとって 7 個の未知数の連立 1 次方程式を解いても、同じ $10$ になる。

反例：仮定を外すと何が起こるか

主定理 1・2 の仮定や、方程式の一部を外した例を並べる。

外す条件	反例	成り立たなくなること
どの状態からも目標にたどり着ける	目標 $0$ のほかに、出られない状態 $2$ がある	止まる確率が $1$、期待値が有限、方程式が解をもつ
状態が有限個	$0,1,2,\ldots$ の上を $\frac12$ ずつ左右に動き、$0$ で止まる	方程式が $0$ 以上の有限の解をもつ
目標の状態で $x_z=0$ とおく	さいころで、止まった状態の値を決めない	方程式の解がただ 1 組

反例：出られない状態がある

状態を $0,1,2$、目標を $Z=\{0\}$ とする。状態 $1$ からは確率 $\dfrac12$ ずつで $0$ と $2$ に移り、状態 $2$ からは必ず $2$ にとどまる。
状態 $2$ から出発すると、いつまでも止まらない。状態 $1$ から出発すると、1 回目に $2$ へ移れば止まらないので、どの $n\ge1$ でも $P_1(T>n)=\dfrac12$ である。$P_1(T>n)$ が $0$ に近づかないので、def-evr-stop により $E_1=E_2=\infty$ である。thm-evr-finite の仮定は、状態 $2$ で $P_2(T\le k)=0$ となって成り立たない。
最初の 1 歩で分けた式を立てると、状態 $2$ の式は $x_2=1+x_2$ で、両辺から $x_2$ を引くと $0=1$ になる。方程式は解をもたない。

反例：状態が無限にある

状態を $0,1,2,\ldots$ の無限個とし、目標を $0$ とする。$i\ge1$ からは確率 $\dfrac12$ ずつで $i+1$ と $i-1$ に移る。最初の 1 歩で分けた式は
$$ x_0=0,\qquad x_i=1+\frac12x_{i+1}+\frac12x_{i-1}\quad(i\ge1) $$
である。両辺を 2 倍して整理すると $x_{i+1}-x_i=(x_i-x_{i-1})-2$ で、隣どうしの差は 1 つ進むごとに $2$ ずつ減る。$x_1=d$ とおくと、差は $d,\ d-2,\ d-4,\ldots$ なので
$$ x_n=d+(d-2)+\cdots+(d-2(n-1))=nd-n(n-1)=n(d-n+1) $$
である。$d$ がどんな数でも、$n>d+1$ となる $n$ では $x_n<0$ になる。期待値は $0$ 以上なので、この方程式には、期待値としてありうる「すべて $0$ 以上の有限の値」の解がない。
実際、この歩き方では $E_1=\infty$ である。一方で、止まる確率は $1$ である。どちらもギャンブラーの破産で、右にも止まる所を置いた有限個の状態の問題と比べて示す。

反例：目標での値を決めない

さいころの例で、状態を「まだ」と「止まった」の 2 つにとり、「まだ」の式 $x_{\text{まだ}}=1+\dfrac56x_{\text{まだ}}+\dfrac16x_{\text{止まった}}$ だけを立て、$x_{\text{止まった}}=0$ を書き忘れたとする。このとき、どんな数 $c$ についても
$$ x_{\text{止まった}}=c,\qquad x_{\text{まだ}}=6+c $$
が式を満たす（$1+\dfrac56(6+c)+\dfrac16c=6+c$）。解は無数にあり、ただ 1 組には決まらない。lem-evr-max は、目標で値が $0$ であることを使って最大値を押さえていた。

大学数学で見る：吸収的 Markov 連鎖

大学の確率論では、目標の状態を「一度入ったら出ない状態」（吸収状態）とみなし、この記事の設定を 吸収的 Markov 連鎖 として扱う。目標でない状態の間で移る確率を並べた正方行列を $Q$ とすると、thm-evr-first-step の連立 1 次方程式は、期待値を並べた列ベクトル $\boldsymbol t$ と成分がすべて $1$ の列ベクトル $\boldsymbol c$ を使って
$$ \boldsymbol t=\boldsymbol c+Q\boldsymbol t,\qquad\text{つまり}\qquad(I-Q)\boldsymbol t=\boldsymbol c $$
と書ける。GS06 §11.2 は、吸収的 Markov 連鎖では吸収される確率が $1$ であること（Theorem 11.3、p.417）と、行列 $N=(I-Q)^{-1}$（基本行列）を使うと $\boldsymbol t=N\boldsymbol c$ となること（Theorem 11.5、p.419）を示している。thm-evr-finite と thm-evr-first-step は、この 2 つの定理を、行列の逆行列を使わずに述べたものにあたる。

停止時刻と調和関数を開く

「初めて目標に着いた回」のように、その回までの結果だけで「今止まるかどうか」が決まる確率変数を、大学では停止時刻という。「最後に表が出た回」は、その後の結果を見ないと決まらないので停止時刻ではない。

lem-evr-max の式 $d_i=\sum_jp_{ij}d_j$ を満たす関数を、推移確率に関する調和関数という。「各点の値が周りの値の重み付きの平均」という性質は、平面の調和関数（ラプラス方程式の解）が円の上の値の平均になることの離散版で、「最大値は境界でとる」という最大値の原理も同じ形で成り立つ。

ex-evr-hh-ht のように、並びが出るまでの回数の期待値は並びによって違う。表と裏の並びが 3 文字以上になると、どちらの並びが先に出やすいかを比べる問題も、同じく状態を決めて最初の 1 歩で分ける方法で解ける。

さらに先へ

両側に止まる所がある歩き方で、どちらで止まるかの確率を求めるのがギャンブラーの破産である。そこでは最初の 1 歩で分けた式が三項間漸化式になり、三項間漸化式の特性方程式で解ける。ex-evr-cx-infinite の $E_1=\infty$ もそこで示す。
期待値ではなく「$n$ 回後にどの状態にいるか」の分布を追うのが確率漸化式と定常分布である。
1 回ごとに確率 $p$（$0< p\le1$）で成功する独立な試行（反復試行の確率）で、初めて成功するまでの回数の期待値は、ex-evr-die-first-step と同じ式 $E=1+(1-p)E$ から $\dfrac1p$ である。主定理 1 の仮定は $k=1$、$\delta=p$ で成り立つ。