マルコフ連鎖 ■推移行列 ・マルコフ性:過去のいかなる状態(X1,X2,...Xn)もXn+1の予測には無関係であるという仮定. ・マルコフ連鎖は推移確率行列で表される. ・自分に戻る確率が1になる状態を吸収状態という.ギャンブルの場合,目標額や破産が吸収状態. ・例として気象連鎖を考える.2日後に雪になる確率は,1日後のそれぞれの天気になる確率と, その天気から雪になる確率の席で表される. ・よってm+nステップ後にiからjに推移する確率はマルコフ性よりmステップ後に状態kになる確率と nステップ後にkからjになる確率を掛け合わせたものの和で示される.これをチャップマン-コルモゴロフ方程式という ・上の確率は推移行列の積の要素として表すことができる.ギャンブルを20回やる場合は推移行列を20回かける. ・ ■状態の分類 ・状態yを出発して状態yに戻る時刻の最小値を停止時刻と呼ぶ. ・強マルコフ性:初期状態yではじめる連鎖とyに戻ってきた状態からの連鎖は振る舞いが同じ.前までのいかなる情報も無関係. ・ある状態xから出発し,状態yに到達する確率が正の時,xはyにコミュニケートする(x→y)という. ・集合内の要素すべてが相互にコミュニケートする集合を「既約」であるという. ■極限の挙動 ・状態yに再び戻る確率が1未満(非再帰的)であるとき,yに戻る確率は0に収束する.では再帰的な場合はどうなるか. ・状態が元に戻る確率p(x,x)>0となるようなnの最大の約数を周期と呼ぶ.例えば合計N個のボールが2つの壺にあるとき, 1つのボールを別の壺に移し替える試行(エーレンフェスト連鎖)を考えると,周期は2になる. ・状態が収束する時の極限までの移動を定常分布と呼ぶ.定常分布は各状態に潜在する割合の極限になっておりπ(y)で表される. ■特別な例 ・反射壁をもつランダムウォークを考えたとき,推移確率行列の行の和はマルコフ性により1になるが,列の和も1になる.これを2重確率 と呼ぶ. ・状態xからyに1ステップで移る量とyからxに1ステップで移る量が同じとき,詳細つり合いであるという.例えば出生死亡連鎖では状態推移が隣を 飛び越えないので詳細つり合い条件が成立する. ■無限状態空間 ・状態空間が無限になった時の定常分布は,詳細つり合いの条件から求める.このとき再帰性には,正再帰的,零再帰的,非再帰的の3つが存在する. ・零再帰的とは,停止時刻が有限である確率が1である条件(再帰性)を満たすが,停止時刻の期待値が無限になるものを指す. ・定常分布がただ1つ存在することは,全ての状態が再帰的であることと同値である. ■質疑 ・t→∞とはどういうことか. 道路ネットワークが∞になるということ.定常状態が定義できない. 交通の場合は収束するという条件で期待値を求めた. ・詳細つり合いとの関係性は. マルコフ連鎖での特殊なケース.相互の推移が同じということ. 車の場合だと,上下線の交通量が同じという意味.しかし1本道だから分かる.複数本では成り立たない. ・無限に走り回っているなら成り立つが,吸収状態があるため成り立たないのでは 吸収状態で吸収した分と同じだけでていくとすると同じになる.各ODで発生と集中が等しいと置けば定常状態は成り立つ. ・1台の車で見たときに,最終的に吸収されるからボールの入れ替えのようなことにはならない ・交通量配分で1個前だけでなく2個前まで考えた配分は可能か. OD×ODの行列で(リンク間遷移にすることで)可能である. ・前の論文ゼミでやったセルオートマトンみたいに,独立性を考えたときに2つ前3つ前のことは考慮できるのか. 単純に切ってやって1次2次3次4次で計算量の違いを見ることは可能では. 回遊は2箇所3箇所で終わってしまう. ・座標としてみてみる,縮約として考えたときにどうなるか. 3次マルコフでは空間を取っている.しかし非効率. ・例えば周南のアンケートでまち中は先に用事を済ますので百貨店に行ったら外に出なくなる.みたいなことは考えられる.