← 定理辞典📖 定理辞典

確率漸化式

確率漸化式

「いま各状態にいる確率 ×\times そこから移る確率」を全経路たし上げて、次の時刻の確率を作る漸化式。pn+1=ppn+qp_{n+1}=pp_n+q 型に整えれば、数列の漸化式と同じように一般項や収束先(定常確率)が求まる。

主張

毎回の試行で状態(部屋A・Bなど)を行き来する問題では、「nn 回目に状態Aにいる確率 pnp_n」を直接たどるのは大変だよね。そこで、11 回先の確率 pn+1p_{n+1} を、いまの確率 pnp_n から作る漸化式を立てる。次にAにいる経路は「いまAにいて(pnp_n)Aにとどまる」または「いまBにいて(1−pn1-p_n)Aへ移る」。この排反な経路の確率を、乗法で積・加法でたし合わせればいい。例えばAにとどまるのもBからAへ来るのも確率がそれぞれ 23,13\tfrac23,\tfrac13 なら、pn+1=23pn+13(1−pn)=13pn+13p_{n+1}=\tfrac23p_n+\tfrac13(1-p_n)=\tfrac13p_n+\tfrac13。こうして pn+1=ppn+qp_{n+1}=pp_n+q の形に整えれば、あとは数列の漸化式と同じ。特性方程式から一般項が求まり、n→∞n\to\infty の収束先(定常確率)も出るんだ。

pn+1=23pn+13(1−pn)=13pn+13pn=12+(p0−12)(13)n → n→∞  12\begin{gathered}p_{n+1}=\tfrac23p_n+\tfrac13(1-p_n)=\tfrac13p_n+\tfrac13\\[6pt]p_n=\tfrac12+\Bigl(p_0-\tfrac12\Bigr)\Bigl(\tfrac13\Bigr)^{n}\ \xrightarrow{\ n\to\infty\ }\ \tfrac12\end{gathered}
1/31/32/32/3部屋A1.00部屋B0.00
ノード=状態、矢印の数字=移る確率。いま各状態にいる確率に矢印の確率をかけてたし上げると、次の時刻の確率になるよ。

成り立つ条件

(i) どの時刻でも状態はちょうど 11 つ(A と B は排反で、pn+(Bにいる確率)=1p_n+(B\text{にいる確率})=1)。だから B にいる確率を 1−pn1-p_n と置きかえられる。(ii) 移る確率(遷移確率)が時刻によらず一定であること。この 22 つがそろうと、pn+1p_{n+1} を pnp_n だけの式で書ける。前提は数列の漸化式(an+1=pan+qa_{n+1}=pa_n+q 型の解き方)と、確率の加法・乗法だよ。

なぜそう決まる?

「次にAにいる」経路を、いまの状態ごとに分けて確率の加法・乗法で数え上げる。閉じた漸化式に整え、特性方程式で一般項と収束先を求める。

  1. 1

    次に A にいるのは、22 つの排反な経路のどちらか。「いま A にいて(pnp_n)A にとどまる(23\tfrac23)」か、「いま B にいて(1−pn1-p_n)A へ移る(13\tfrac13)」。同時には起きないので、別々に考えられるね。

    (次に A)=pn⋅23⏟A→A + (1−pn)⋅13⏟B→A(\text{次に }A)=\underbrace{p_n\cdot\tfrac23}_{A\to A}\ +\ \underbrace{(1-p_n)\cdot\tfrac13}_{B\to A}
  2. 2

    各経路の確率は「いまそこにいる確率 ×\times そこから移る確率」=乗法で積。排反な 22 経路だから加法でたし合わせて、pn+1p_{n+1} ができる。これを整理すると pnp_n だけの閉じた漸化式になるよ。

    pn+1=23pn+13(1−pn)=13pn+13p_{n+1}=\tfrac23p_n+\tfrac13(1-p_n)=\tfrac13p_n+\tfrac13
  3. 3

    これは an+1=pan+qa_{n+1}=pa_n+q 型。特性方程式 α=13α+13\alpha=\tfrac13\alpha+\tfrac13 を解くと α=12\alpha=\tfrac12(=動かなくなる確率=定常確率)。両辺から 12\tfrac12 を引くと、ずれ pn−12p_n-\tfrac12 が公比 13\tfrac13 の等比数列に化ける。

    pn+1−12=13(pn−12)p_{n+1}-\tfrac12=\tfrac13\Bigl(p_n-\tfrac12\Bigr)
  4. 4

    等比数列の一般項を当てれば pnp_n が求まる。公比 13\tfrac13 は 11 より小さいから、nn を大きくすると第 22 項は 00 へ。最初 A に偏って(p0=1p_0=1)いても、確率は半々 12\tfrac12 に収束する、というわけだね。

    pn=12+(p0−12)(13)n ⟶ 12p_n=\tfrac12+\Bigl(p_0-\tfrac12\Bigr)\Bigl(\tfrac13\Bigr)^{n}\ \longrightarrow\ \tfrac12

逆

立てた漸化式が pn+1=ppn+qp_{n+1}=pp_n+q 型なら、特性方程式 α=pα+q\alpha=p\alpha+q の解 α\alpha が「もう変わらない確率」=定常確率で、これがそのまま n→∞n\to\infty の収束先になる(∣p∣<1|p|<1 のとき)。上の例なら α=13α+13\alpha=\tfrac13\alpha+\tfrac13 から α=12\alpha=\tfrac12。逆に言えば、最初にAに偏っていても(p0=1p_0=1)、行き来をくり返すうちに差がならされて半々(12\tfrac12)へ近づく、と漸化式の形だけから読み取れるんだ。

補足・つまずきポイント

つまずきの定番は、B にいる確率を別の文字のまま残してしまうこと。状態が 22 つで排反なら必ず 1−pn1-p_n に置きかえて、pnp_n だけの式にする(そうしないと漸化式が閉じない)。もうひとつ、立式は「次にAにいる」を主語にして、そこへ来る全経路(とどまる+移ってくる)をもれなく・重複なく数えること。図(状態遷移図)の矢印を 11 本ずつ拾うと安全だよ。33 状態以上だと連立の漸化式になるが、考え方は同じ。最後に確率の和が 11 のままか、n=0n=0(11)で初期値に戻るかを検算しよう。

関連する定理

見て確かめる

言葉で読んだら、動くアニメと自分の手で確かめてみよう。

使いどころ

この定理が、実際の問題でどう効くのかを見てみよう。