確率漸化式 | 場合の数と確率統計

1 状態と遷移

定義 1.1 (状態確率と遷移確率). $n$ 回目に状態 $i$ にある確率を $p_n(i)$ とします。状態 $i$ から次に状態 $j$ へ移る条件付き確率を、状態 $i$ から $j$ への遷移確率といいます。

各状態から着目する状態へ入る場合を排反に分けると、次の回の状態確率を求めることができます。

2 完結した二状態の例

ある機械は、毎日の終わりに正常または故障のいずれかの状態にあります。正常ならば翌日も正常である確率を $0.7$ 、故障ならば修理によって翌日に正常である確率を $0.2$ とします。初日は正常であるとします。

例 2.1. $n$ 日目に正常である確率を $p_n$ とすると、故障である確率は $1-p_n$ です。翌日に正常である場合を、前日に正常であった場合と故障であった場合に分けると、

p_{n+1}=0.7p_n+0.2(1-p_n)=0.5p_n+0.2,\qquad p_1=1

を得ます。

定理 2.2. 上の二状態モデルでは、

p_n=0.4+0.6\left(\frac12\right)^{n-1}

が成り立ちます。

証明. 不動点 $\alpha$ は $\alpha=0.5\alpha+0.2$ を満たすので $\alpha=0.4$ です。したがって

p_{n+1}-0.4=0.5(p_n-0.4)

です。 $p_1-0.4=0.6$ なので、等比数列の一般項から結論を得ます。▨

注意 2.3 (確率としての検算). $0.4\le p_n\le1$ なので、一般項は確率の範囲にあります。また $n$ を大きくすると $p_n$ は0.4へ近づき、漸化式の不動点と一致します。

上の例で状態を一つの確率だけで表すことができるのは、状態が正常と故障の二つだけなので、故障である確率が $1-p_n$ と決まるためです。三状態以上では、通常は複数の状態確率を同時に追います。

例 2.4. 状態を晴れ、曇り、雨の三つに分ける場合、 $n$ 日目の確率を $s_n,c_n,r_n$ とし、 $s_n+c_n+r_n=1$ を保ちながら、各遷移確率を係数とする連立漸化式を立てます。一つの確率だけを追うと、前日の残り二状態を区別することができません。

3 例題

レベル3 — 確率漸化式

はじめの状態を p_0 $=$ 1 として、n 回の操作の後に指定した状態にある確率 p_n を n の式で表せ。

解法の型1回の操作で場合分けして p_(n+1) $=$ a p_n + b を立て、不動点 $\alpha$ $=$ b/(1−a) を引いて (p_n − $\alpha)$ を公比 a の等比数列にする

例 3.1. 表の出る確率が 1/3 である硬貨を繰り返し投げる。n 回投げたとき、表の出た回数が偶数（0 回も含む）である確率を p_n とする。p_n を求めよ。

p_0 = 1,\quad p_{n+1} = \dfrac{2}{3}\,p_n + \dfrac{1}{3}\,(1 - p_n)

答 $p_n = \dfrac{1}{2} + \dfrac{1}{2}\left(\dfrac{1}{3}\right)^{n}$

注意 n+1 回目に「偶数回」なのは、「n 回目まで偶数回で、次が裏（確率 2/3）」か「n 回目まで奇数回で、次が表（確率 1/3）」。整理すると p_(n+1) $=$ (1 − 2·1/3) p_n + 1/3 $=$ 1/3·p_n + 1/3。不動点は $\alpha =$ 1/2（回数を重ねると偶数・奇数が半々に近づく）。検算: n $=$ 1 では p_1 $=$ 1/2 + (1/2)(1 − 2·1/3) $=$ 2/3 で、裏が出る確率に一致する。

例 3.2. 点 P は部屋 A、部屋 B のいずれかにいる。1回の操作でサイコロを1個投げ、P が A にいるときは出た目が 2 以下なら B へ移り（それ以外は A に留まる）、P が B にいるときは出た目が 1 以下なら A へ移る（それ以外は B に留まる）。はじめ P は A にいる。n 回の操作の後に P が A にいる確率 p_n を求めよ。

p_0 = 1,\quad p_{n+1} = \dfrac{2}{3}\,p_n + \dfrac{1}{6}\,(1 - p_n)

答 $p_n = \dfrac{1}{3} + \dfrac{2}{3}\left(\dfrac{1}{2}\right)^{n}$

注意 n+1 回目に A にいるのは「n 回目に A にいて留まる（確率 4/6 $=$ 2/3）」か「n 回目に B にいて A へ移る（確率 1/6）」。整理して p_(n+1) $=$ 1/2·p_n + 1/6。不動点は $\alpha =$ (1/6)/(1 − 1/2) $=$ 1/3（長い目で見て A にいる割合）。p_n − $\alpha$ は公比 1/2 の等比数列で初項 1 − $\alpha =$ 2/3。

4 演習

問題 4.1.例 2.1の機械が初日に故障している場合に、 $n$ 日目に正常である確率 $p_n$ を求めよ。

解答.

初日に故障しているので $p_1=0$ であり、漸化式は例 2.1と同じ $p_{n+1}=0.5p_n+0.2$ である。不動点 $0.4$ を用いると $p_{n+1}-0.4=0.5(p_n-0.4)$ であり、数列 $(p_n-0.4)$ は初項 $p_1-0.4=-0.4$ 、公比 $1/2$ の等比数列である。したがって、

p_n=0.4-0.4\left(\frac12\right)^{n-1}

である。▨

問題 4.2. 二状態の機械について、正常から翌日も正常である確率を $a$ 、故障から翌日に正常である確率を $b$ とする（ $0\le a\le1$ 、 $0\le b\le1$ ）。 $n$ 日目に正常である確率 $p_n$ が満たす漸化式と、その漸化式の不動点を求めよ。

解答.

$n$ 日目に故障である確率は $1-p_n$ である。翌日に正常である場合を、前日に正常であった場合と故障であった場合に分けると、二つの場合は排反なので

p_{n+1}=ap_n+b(1-p_n)=(a-b)p_n+b

を得る。不動点 $\alpha$ は $\alpha=(a-b)\alpha+b$ 、すなわち $(1-a+b)\alpha=b$ を満たす。 $a-b\ne1$ ならば、不動点はただ一つ存在し、 $\alpha=b/(1-a+b)$ である。 $a-b=1$ となるのは、 $0\le a\le1$ 、 $0\le b\le1$ のもとでは $a=1$ 、 $b=0$ の場合に限る。この場合の漸化式は $p_{n+1}=p_n$ であり、すべての実数が不動点である。▨

問題 4.3.問題 4.1で求めた一般項が0以上1以下にあり、漸化式 $p_{n+1}=0.5p_n+0.2$ と初期条件 $p_1=0$ を満たすことを、代入して確かめよ。

解答.

一般項 $p_n=0.4-0.4/2^{n-1}$ に $n=1$ を代入すると $p_1=0.4-0.4=0$ であり、初期条件を満たす。一般項を漸化式の右辺に代入すると、

0.5\left(0.4-\frac{0.4}{2^{n-1}}\right)+0.2=0.4-\frac{0.4}{2^n}

であり、右辺は一般項の $n+1$ のときの値 $p_{n+1}$ に等しい。したがって、一般項は漸化式を満たす。さらに、すべての正の整数 $n$ について $0<0.4/2^{n-1}\le0.4$ なので $0\le p_n<0.4$ であり、 $p_n$ は0以上1以下にある。▨

レベル3 — 確率漸化式

はじめの状態を p_0 $=$ 1 として、n 回の操作の後に指定した状態にある確率 p_n を n の式で表せ。

解法の型1回の操作で場合分けして p_(n+1) $=$ a p_n + b を立て、不動点 $\alpha$ $=$ b/(1−a) を引いて (p_n − $\alpha)$ を公比 a の等比数列にする

問題 4.4. 5 個の地点 A, B, C, D, E の上を点 P が動く。1回の操作で、P は今いる地点以外の 4 個の地点のいずれかへ等確率で移る。はじめ P は地点 A にある。n 回の操作の後に P が地点 A にある確率 p_n を求めよ。

p_0 = 1,\quad p_{n+1} = \dfrac{1 - p_n}{4}

解答.

答 $p_n = \dfrac{1}{5} + \dfrac{4}{5}\left(-\dfrac{1}{4}\right)^{n}$

注意 n+1 回目に A にいるのは「n 回目に A 以外にいて（確率 1 − p_n）、そこから A へ移る（確率 1/4）」場合だけなので p_(n+1) $=$ (1 − p_n)/4。不動点は $\alpha =$ 1/5（長い目で見ると 5 個の地点に均等に散らばる）。p_n − 1/5 は公比 −1/4 の等比数列で、初項 p_0 − 1/5 $=$ 4/5。検算: n $=$ 1 のとき p_1 $=$ 1/5 − (1/5) $=$ 0（1回で A には戻れない）。▨

問題 4.5. 表の出る確率が 2/5 である硬貨を繰り返し投げる。n 回投げたとき、表の出た回数が偶数（0 回も含む）である確率を p_n とする。p_n を求めよ。

p_0 = 1,\quad p_{n+1} = \dfrac{3}{5}\,p_n + \dfrac{2}{5}\,(1 - p_n)

解答.

答 $p_n = \dfrac{1}{2} + \dfrac{1}{2}\left(\dfrac{1}{5}\right)^{n}$

注意 n+1 回目に「偶数回」なのは、「n 回目まで偶数回で、次が裏（確率 3/5）」か「n 回目まで奇数回で、次が表（確率 2/5）」。整理すると p_(n+1) $=$ (1 − 2·2/5) p_n + 2/5 $=$ 1/5·p_n + 2/5。不動点は $\alpha =$ 1/2（回数を重ねると偶数・奇数が半々に近づく）。検算: n $=$ 1 では p_1 $=$ 1/2 + (1/2)(1 − 2·2/5) $=$ 3/5 で、裏が出る確率に一致する。▨

問題 4.6. 点 P は部屋 A、部屋 B のいずれかにいる。1回の操作でサイコロを1個投げ、P が A にいるときは出た目が 2 以下なら B へ移り（それ以外は A に留まる）、P が B にいるときは出た目が 2 以下なら A へ移る（それ以外は B に留まる）。はじめ P は A にいる。n 回の操作の後に P が A にいる確率 p_n を求めよ。

p_0 = 1,\quad p_{n+1} = \dfrac{2}{3}\,p_n + \dfrac{1}{3}\,(1 - p_n)

解答.

答 $p_n = \dfrac{1}{2} + \dfrac{1}{2}\left(\dfrac{1}{3}\right)^{n}$

注意 n+1 回目に A にいるのは「n 回目に A にいて留まる（確率 4/6 $=$ 2/3）」か「n 回目に B にいて A へ移る（確率 2/6 $=$ 1/3）」。整理して p_(n+1) $=$ 1/3·p_n + 1/3。不動点は $\alpha =$ (1/3)/(1 − 1/3) $=$ 1/2（長い目で見て A にいる割合）。p_n − $\alpha$ は公比 1/3 の等比数列で初項 1 − $\alpha =$ 1/2。▨

§B4.10確率漸化式

1 状態と遷移

2 完結した二状態の例

3 例題

4 演習

前提記事