1

確率漸化式と遷移行列

472
1
$$\newcommand{A}[0]{\mathbb{A}} \newcommand{abs}[1]{\lvert#1\rvert} \newcommand{Algs}[0]{{\rm Algs}} \newcommand{Art}[0]{{\rm Art}} \newcommand{Aut}[0]{Aut} \newcommand{B}[0]{\mathbb{B}} \newcommand{bB}[0]{\mathbf{B}} \newcommand{bH}[0]{\mathbf{H}} \newcommand{Br}[0]{\mathrm{Br}} \newcommand{C}[0]{\mathbb{C}} \newcommand{cF}[0]{\mathcal{F}} \newcommand{cG}[0]{\mathcal{G}} \newcommand{cH}[0]{\mathcal{H}} \newcommand{cI}[0]{\mathcal{I}} \newcommand{cJ}[0]{\mathcal{J}} \newcommand{colim}[0]{colim} \newcommand{Cone}[0]{{\rm Cone}} \newcommand{Conj}[0]{{\rm Conj}} \newcommand{dimtot}[0]{{\rm dimtot}} \newcommand{End}[0]{End} \newcommand{Ext}[0]{{\rm Ext}} \newcommand{F}[0]{\mathbb{F}} \newcommand{fa}[0]{\mathfrak{a}} \newcommand{fb}[0]{\mathfrak{b}} \newcommand{fg}[0]{\mathfrak{g}} \newcommand{fh}[0]{\mathfrak{h}} \newcommand{Frob}[0]{\mathrm{Frob}} \newcommand{Fun}[0]{Fun} \newcommand{fZ}[0]{\mathfrak{Z}} \newcommand{G}[0]{\mathbb{G}} \newcommand{Gal}[0]{{\rm Gal}} \newcommand{GL}[0]{GL} \newcommand{Gm}[0]{\mathbb{G}m} \newcommand{grad}[0]{grad} \newcommand{Hom}[0]{Hom} \newcommand{id}[0]{\mathrm{id}} \newcommand{im}[0]{im} \newcommand{Ind}[0]{Ind} \newcommand{inpr}[1]{\langle #1 \rangle} \newcommand{inv}[0]{\mathrm{inv}} \newcommand{leng}[0]{{\rm leng}} \newcommand{li}[0]{{\rm li}} \newcommand{Monoids}[0]{{\rm Monoids}} \newcommand{N}[0]{\mathbb{N}} \newcommand{norm}[1]{\lvert\lvert#1\rvert\rvert} \newcommand{Ob}[0]{{\rm Ob}} \newcommand{ord}[0]{{\rm ord}} \newcommand{p}[0]{\mathfrak{p}} \newcommand{Posets}[0]{{\rm Posets}} \newcommand{pr}[0]{{\rm pr}} \newcommand{Prim}[0]{{\rm Prim}} \newcommand{Proj}[0]{\mathbb{P}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{quat}[3]{\left(\frac{#1,#2}{#3}\right)} \newcommand{R}[0]{\mathbb{R}} \newcommand{rank}[0]{\mathrm{rank}} \newcommand{rec}[0]{\mathrm{rec}} \newcommand{Res}[0]{Res} \newcommand{res}[0]{\mathrm{res}} \newcommand{sB}[0]{\mathscr{B}} \newcommand{Sch}[0]{Sch} \newcommand{Set}[0]{{\rm Set}} \newcommand{Sets}[0]{{\rm Set}} \newcommand{SL}[0]{SL} \newcommand{SO}[0]{SO} \newcommand{spa}[1]{{\rm Spa}(#1)} \newcommand{Spec}[0]{\mathrm{Spec}} \newcommand{spf}[1]{{\rm Spf}(#1)} \newcommand{Sw}[0]{{\rm Sw}} \newcommand{Tr}[0]{Tr} \newcommand{tr}[0]{\mathrm{tr}} \newcommand{trace}[0]{trace} \newcommand{vect}[1]{\overrightarrow{#1}} \newcommand{Vect}[0]{{\rm Vect}} \newcommand{Vir}[0]{Vir} \newcommand{vol}[0]{\mathrm{vol}} \newcommand{Xb}[0]{\overline{X}} \newcommand{Z}[0]{\mathbb{Z}} $$

問題

例えば次のような問題を考える。

手元にカードが$1$枚あり、片面は黒でもう片面が白くなっているとする。サイコロを振って$1$の目がでたらカードを裏返すという操作を繰り返し行う。最初カードは黒い面を向いており、この操作を$3$回行った後に白い面を向いている確率を求めよ。

$1$回目終わった後に白か黒か、$2$回目終わった後に白か黒かそれぞれで場合わけ、言い換えるとカードの色の遷移を黒白白白、黒白黒白、黒黒白白、黒黒黒白のそれぞれで場合わけして確率を計算すると
$$\begin{eqnarray} \frac{1}{6}\times\frac{5}{6}\times\frac{5}{6} +\frac{1}{6}\times\frac{1}{6}\times\frac{1}{6} +\frac{5}{6}\times\frac{1}{6}\times\frac{5}{6} +\frac{5}{6}\times\frac{5}{6}\times\frac{1}{6}\end{eqnarray}$$と計算できる。

より一般に$n$回後に白となる確率$p_n$は、
\begin{align*} p_n=p_{n-1}\times\frac{5}{6}+(1-p_{n-1})\times\frac{1}{6} \end{align*}
という漸化式をたて、これを解くことでも求めることができる。

遷移行列

これを行列の言葉を用いて次のように表現しよう。まず、遷移行列$T$を次のように定める。
$$\begin{eqnarray} T&= \begin{pmatrix} T_{11}&T_{12}\\ T_{21}&T_{22} \end{pmatrix}\\ &= \begin{pmatrix} 5/6&1/6\\ 1/6&5/6 \end{pmatrix}\end{eqnarray}$$この行列の成分$T_{ij}$は、状態$i$から状態$j$にうつる確率を表している。ここで、状態$1$を白とし$2$を黒とすることにしよう。つまり上の行列は左上$T_{11}$が白から白へ遷移する確率、右上$T_{12}$が白から黒へ遷移する確率、左下$T_{21}$が黒から白へ遷移する確率、右下$T_{22}$が黒から黒へ遷移する確立をそれぞれ表現している。

この$T$に対して、$T^2$を計算してみると $$\begin{eqnarray} T^2&=& \begin{pmatrix} 5/6&1/6\\ 1/6&5/6 \end{pmatrix} \begin{pmatrix} 5/6&1/6\\ 1/6&5/6 \end{pmatrix}\\ &=& \begin{pmatrix} 5/6\times5/6+1/6\times1/6&5/6\times1/6+1/6\times5/6\\ 1/6\times5/6+5/6\times1/6&1/6\times1/6+5/6\times5/6\\ \end{pmatrix}\end{eqnarray}$$となる。これの$(1,1)$成分ははじめ白で$2$回振った後にまた白である確率
$$\begin{eqnarray} \frac{5}{6}\times\frac{5}{6}+\frac{1}{6}\times\frac{1}{6}\end{eqnarray}$$と一致している。これは
$$\begin{eqnarray} T_{11}T_{11}+T_{12}T_{21}\end{eqnarray}$$であり、白白白の順に遷移する確率と白黒白の順に遷移する確率の和である。これ以外の成分も同様に$(i,j)$成分ははじめ状態$i$$2$回振った後に状態$j$となる確率である。実際、$T^2$$(i,j)$成分は
$$\begin{eqnarray} T_{i1}T_{1j}+T_{i2}T_{2j}\end{eqnarray}$$であるから、状態が$i,1,j$の順で遷移する確率と$i,2,j$の順で遷移する確率の和となっている。

同じように$T^3$$$\begin{eqnarray} T^3&=& T^2\times T\\ &=& \begin{pmatrix} 5/6\times5/6+1/6\times1/6&5/6\times1/6+1/6\times5/6\\ 1/6\times5/6+5/6\times1/6&1/6\times1/6+5/6\times5/6\\ \end{pmatrix} \begin{pmatrix} 5/6&1/6\\ 1/6&5/6 \end{pmatrix}\\ &=& \begin{pmatrix} (5/6\times5/6+1/6\times1/6)\times5/6+(5/6\times1/6+1/6\times5/6)\times1/6& (5/6\times5/6+1/6\times1/6)\times1/6+(5/6\times1/6+1/6\times5/6)\times5/6\\ (1/6\times5/6+5/6\times1/6)\times5/6+(1/6\times1/6+5/6\times5/6)\times1/6& (1/6\times5/6+5/6\times1/6)\times1/6+(1/6\times1/6+5/6\times5/6)\times5/6 \end{pmatrix}\end{eqnarray}$$となり、$(i,j)$成分ははじめ状態$i$$3$回振った後に状態$j$となる確率である。例えば$(1,1)$成分は、$$\begin{eqnarray} T_{11}T_{11}T_{11}+T_{12}T_{21}T_{11}+T_{11}T_{12}T_{21}+T_{12}T_{22}T_{21}\end{eqnarray}$$であり、白白白白、白黒白白、白白黒白、白黒黒白の遷移確率の和になっている。

したがって、サイコロを振る前に黒で$3$回振った後に白になっている確率は$T^3$$(2,1)$成分を見ればよく、これははじめに計算した通り
$$\begin{eqnarray} T_{21}T_{11}T_{11}+T_{21}T_{12}T_{21}+T_{22}T_{21}T_{11}+T_{22}T_{22}T_{21} &= \frac{1}{6}\times\frac{5}{6}\times\frac{5}{6} +\frac{1}{6}\times\frac{1}{6}\times\frac{1}{6} +\frac{5}{6}\times\frac{1}{6}\times\frac{5}{6} +\frac{5}{6}\times\frac{5}{6}\times\frac{1}{6} \end{eqnarray}$$となることがわかる。

一般にはじめの状態が$i$$N$回後に状態$j$となる確率は$T^N$$(i,j)$成分となることがわかる。

周期条件

次にある時刻$N$での位置が初期位置と一致する、という条件をつけて何らかの条件付き確率を計算したいとしよう。あるいは、カードの状態遷移が周期的であるという仮定をつける。

たとえば$N=3$周期という条件の下での条件付き確率を計算したい場合、最初が白で$3$回後も白である確率と、最初が黒で$3$回後も黒である確率の和によって正規化する必要がある。つまり、最初と$3$回後の色が同じ事象を$A$としたとき、事象$B$$A$を条件とした条件付き確率は
$$\begin{eqnarray} P(B\mid A)=\frac{P(A\cap B)}{P(A)}\end{eqnarray}$$であり、この分母$P(A)$を計算する。

前と同様に状態白を$1$、黒を$2$としよう。上での考察から、$3$回サイコロを振って白から白へ、つまり$1$から$1$へうつる確率は$T^3$$(1,1)$成分であり、$3$回サイコロを振って黒から黒へ、つまり$2$から$2$へうつる確率は$T^3$$(2,2)$成分である。したがって、$$\begin{eqnarray} P(A)&=(T^3)_{11}+(T^3)_{22}\\ &=\tr(T^3)\end{eqnarray}$$となることがわかる。

一般にはじめの状態と$N$回後の状態が一致する確率は$\tr(T^N)$となる。

終わりに

この記事に関連する内容として、$1$次元格子モデルの転送行列についての話を後日公開します。

投稿日:20201220

この記事を高評価した人

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

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

バッジはありません。

投稿者

数学が好きです。

コメント

他の人のコメント

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