マルコフ連鎖についての問題なのですが．．

マルコフ連鎖についての問題なのですが．．

half tone guy さんの書込 (2009/06/20(Sat) 11:06)

はじめまして，大学１年生の者です． 大学の講義でどうしてもわからない問題があります． 「Ω状態のマルコフ連鎖においてRを遷移行列とするとき，詳細つりあいの条件， R_{ij}p_{j}^{(s)}=R_{ji}p_{i}~{(s)} が成り立つとき， (e^{tR})_{ij}p_{j}^{(s)}=(e^{tR})_{ji}p_{i}^{(s)} が成り立つことを証明せよ．」 という問題なのですが，講義中に習ったことを用いて式変形してみたのですが， どうしても証明できません． 講義で習った証明に使えそうなものは， 「指数関数で累乗の位置に行列があるときのTylor展開の方法」 「マルコフ連鎖における，マスター方程式」 「 e^{tR} は時間をt進める行列」 です． 僕は最初に e^{tR} をTaylor展開して，それから最初の条件式を 使って証明しようとしました． 証明の仕方，あるいは証明の方向性を指摘してもらえたらありがたいです． よろしくお願いします．

Re: マルコフ連鎖についての問題なのですが．．

toorisugari no Hiro さんのレス (2009/06/20(Sat) 17:04)

\hat R を遷移演算子( (\hat R)_{ij}=R_{ij} )としましょう．

(\hat R)_{ij}p_{j}^{(s)}=(\hat R)_{ji}p_{i}^{(s)} ならば， (\hat R^2)_{ij}p_{j}^{(s)}=(\hat R^2)_{ji}p_{i}^{(s)} , (\hat R^3)_{ij}p_{j}^{(s)}=(\hat R^3)_{ji}p_{i}^{(s)} , \cdots が成り立つことを示したらいいのでは?

(\hat R^2)_{ij} &= \sum_{k_1}R_{ik_1}R_{k_1j}\\(\hat R^3)_{ij} &= \sum_{k_1,k_2}R_{ik_1}R_{k_1k_2}R_{k_2j}

ですよね．

Re: マルコフ連鎖についての問題なのですが．．

half tone guy さんのレス (2009/06/20(Sat) 18:42)

返信ありがとうございます！ おかげで証明することができました． しかし，もう一つ疑問が，，， 結局示した等式の左辺，および右辺は一体どのような確率を表しているのでしょうか？ 僕は「 e^{tR} が時間をｔ進める行列だから，左辺と右辺はそれぞれ，マルコフ連鎖が定常分布に落ち着いてからt秒後に p_{j}^{(s)},p_{i}^{(s)} にいる確率」と考えているのですが，どうにも短絡的すぎると思えて仕方ありません． 重ね重ねの質問で申し訳ないんですがよろしくおねがいします．

Re: マルコフ連鎖についての問題なのですが．．

toorisugari no Hiro さんのレス (2009/06/20(Sat) 19:36)

そもそもの R_{ij} の定義は何ですか？

時刻 t に状態 i にいる確率を p_i ，時刻 t+\Delta t に状態 i にいる確率を p'_i とあらわすとします(定常とは限りません)． \Delta t を微小として p'_i は \{p_i\} と \{R_{ij}\} (あるいは \hat R )でどう表現できるか考えてみてください． # 当然時間的に一様なマルコフ連鎖をかんがえてます．

Re: マルコフ連鎖についての問題なのですが．．

half tone guy さんのレス (2009/06/21(Sun) 11:38)

返信ありがとうございます． p_{i}^{'} =(1- ?tΣ R_{ji}(i\not=j))p_{i} でしょうか？ この等式すら自信がないうえに， (e^{tR})_{ij}p_{j} がどんな確率を表すかまったくわかりません． もう少しヒントをいただけませんか？

Re: マルコフ連鎖についての問題なのですが．．

toorisugari no Hiro さんのレス (2009/06/22(Mon) 11:21)

# 私もよく分かっていないので，間違っていたら，よろしく．>識者の方

p'_{i} = p_{i} + \Delta t \sum_{j \ne i}R_{ij}p_{j} - \Delta t \sum_{j \ne i}R_{ji}p_{i}

ではないでしょうか． これと

\left(\mathrm{e}^{\Delta t \hat R}\right)_{ij} &\approx \left(\hat 1 + \Delta t \hat R \right)_{ij}=\delta_{ij} + \Delta t R_{ij}

をくみあわせると関係式が出ませんか?

Re: マルコフ連鎖についての問題なのですが．．

half tone guy さんのレス (2009/06/22(Mon) 21:56)

出てくる関係式は \sum_{j \ne i}(e^{\Delta tR})_{ij}p_{j}=\sum_{j \ne i}(e^{\Delta tR})_{ji}p_{i} であっているでしょうか？ それから，示した式が何を表すのかは，やはりさっぱりわかりません．

Re: マルコフ連鎖についての問題なのですが．．

mNeji さんのレス (2009/06/22(Mon) 23:02)

half tone guyさん，横から失礼します．

門前の小僧モードですが， (\mathrm{e}^{\Delta t R})_{ij} は言うならば，複数のパスを通って，j→k1→k2→...→iにいく確率を示すのではないでしょうか．

すると，左辺は，ある時刻tいるj状態からi状態への遷移確率の総和ですから，結局, 時刻t〜t+Δtの間に，他の全ての状態からi状態に流入する確率を示すのではないでしょうか，

逆に，右辺は，あるi状態から，時刻t〜t+Δtの間に，他の全ての状態へ流失する確率を示すと思えます．

両者をあわせて，i状態は動的な平衡を示していると，考えられそうですね．当てずっぽうですが...，面白そうですね．

Re: マルコフ連鎖についての問題なのですが．．

toorisugari no Hiro さんのレス (2009/06/23(Tue) 15:11)

> 出てくる関係式は > \sum_{j \ne i}(e^{\Delta tR})_{ij}p_{j}=\sum_{j \ne i}(e^{\Delta tR})_{ji}p_{i} > であっているでしょうか？

p'_{i} = p_{i} + \sum_{j}\left(\mathrm{e}^{\Delta t \hat R}\right)_{ij}p_{j} - \sum_{j}\left(\mathrm{e}^{\Delta t \hat R}\right)_{ji}p_{i}

ですね．これをテーラー展開したものがmNejiさんの描像にあたります．

ここで平衡状態では p'_{i} = p_{i} =p^{\mathrm{(s)}}_{i} (\text{for }\forall i) が成り立つので，これを代入すると求める式が出てきます．

Re: マルコフ連鎖についての問題なのですが．．

half tone guy さんのレス (2009/06/23(Tue) 18:55)

toorisugari no Hiroさん，mNejiさん，返信ありがとうございます． なるほど，j=iにする必要はないんですね． 出てくる関係式は，平衡状態の条件を使って， \sum _{j}(e^{\Delta t \hat R})_{ij}p_{ij}^{(s)}=\sum _{j}(e^{\Delta t \hat R})_{ji}p_{ji}^{(s)} ですよね． この関係式と， (e^{t \hat R})_{ij}p_{j}^{(s)}=(e^{t \hat R})_{ji}p_{i}^{(s)} とどのように結びつければいいんでしょうか？ t を微小にしたときの \Delta t のときにしか，上の関係式は成り立たないと思うのですが．

Re: マルコフ連鎖についての問題なのですが．．

toorisugari no Hiro さんのレス (2009/06/23(Tue) 20:38)

\hat Q_{t} = \mathrm{e}^{t \hat R} と表しましょう．微少量 \Delta t に対して
\left(\hat Q_{\Delta t} \right)_{ij}p_{j}=\left(\hat Q_{\Delta t} \right)_{ji}p_{i}

が成り立つなら， \{p_i\} が平衡状態の式を満たすのはあきらか． また，同じ条件の下で，Qのn乗の関係式

\left(\hat Q^n_{\Delta t} \right)_{ij}p_{j}=\left(\hat Q^n_{\Delta t} \right)_{ji}p_{i}

が任意の自然数 n で成り立つので，

\left(\hat Q_{t} \right)_{ij}p_{j}=\left(\hat Q_{t} \right)_{ji}p_{i}

が任意の t で成り立つのも自明．

Re: マルコフ連鎖についての問題なのですが．．

half tone guy さんのレス (2009/06/24(Wed) 22:37)

返信ありがとうございます．

はい．確かにその条件があります．

Re: マルコフ連鎖についての問題なのですが．．

toorisugari no Hiro さんのレス (2009/06/25(Thu) 11:26)

>> もしかして >> \sum_{j}R_{jk}&=0 &(\text{for }\forall k) >> という条件がありますか?

> はい．確かにその条件があります．

前提条件をすべて出してもらわないと問題は解けません．まだ，他にないですか?

Re: マルコフ連鎖についての問題なのですが．．

half tone guy さんのレス (2009/06/25(Thu) 12:52)

返信ありがとうございます．

すいません．おそらくこれで全部です．

Re: マルコフ連鎖についての問題なのですが．．

toorisugari no Hiro さんのレス (2009/06/25(Thu) 13:48)

だと議論がずいぶん簡単に，かつ，つじつまが合うようになりますね． # そもそも，ちゃんと R の定義を述べてもらえれば，簡単だったのに．．．．

先に挙げた式

p'_{i} = p_{i} + \Delta t \sum_{j \ne i}R_{ij}p_{j} - \Delta t \sum_{j \ne i}R_{ji}p_{i} \qquad(|\Delta t| \ll 1)

は(確率が意味を持つための条件の一つである)ノルム保存則 \left(\sum_{i}p'_{i}=\sum_{i}p_{i}\right) を満たしますが，

> 返信ありがとうございます．
>  |6dc021bab519a66a3966219996835e14| =(1- ?tΣ |ee4ae2ba9ba0702580404a9130b7830d| 
> でしょうか？

の

p'_i &= p_i - \Delta t \sum_{j \ne i}R_{ji}p_{i}

は \sum_{k \ne i}R_{ki} = 0 もしくは \sum_{k}R_{ki} &= R_{ii} を任意の i で満たさないとノルム保存則を満たしません．

ただし， \sum_{k}R_{ki}=0 ~~(\text{for }\forall i) が前提条件になるなら，第一の式は簡単な

p'_{i} &= p_{i} + \Delta t \sum_{j}R_{ij}p_{j} \qquad(|\Delta t| \ll 1)

になり(当然保存則を満たします)，ここから

p^{t+\Delta t}_{i} &= \sum_{j} \left(\mathrm{e}^{\Delta t \hat R}\right)_{ij}p^{t}_{j}

が任意の \Delta t に対して成り立ちます．

ここから，平衡状態の議論も導けます．

問題: ノルム保存則により

\sum_{k} \left(\mathrm{e}^{\Delta t \hat R}\right)_{ki}=1

ですが，これを \sum_{k}R_{ki}=0 から証明してください．