cocolog:76226644

ごく普通のランダムウォークなマルコフ連鎖…プラス方向に p、マイナス方向に q の確率で遷移するもの…は、p が 1/2 でなければ再帰しないが、r_n = (2 * p - 1) * n みたいな「再帰軸」を取れば、その周りのおいて再帰する。(はず) (JRF 1705)

JRF 2013年4月18日 (木) Tweet

私は、他の問題を解析するためにマルコフ連鎖を学習(復習)している。そこで、ランダムウォークが p が 1/2 ではないとき再帰的じゃない…という事実にモヤッと来た。

前なら読み飛ばしていたところだが、よく考えると少し変だ。

JRF2013年4月18日3081

マルコフ連鎖の他の定理に p(i,j) > 0 かつ p(j,i) > 0 のとき i と j が同じ同値類に属すると定義したとき、同じ同値類に属するものの一つが再帰すれば、同値類に属するすべてが再帰するというものがある。

この定理は、つまり、再帰するものがひとたびあったら、そこから有限で到達できるところには、やはり何度でも現れうるといったことを示している。

JRF2013年4月18日9594

しかし、じゃあ、逆に一つが再帰じゃないとわかったとき、どこか向こうのほうでは一度も帰ってこなくなるのか？というと、ここが微妙で、等比級数 (1/R)^n 以下のごく薄いものが現れるのは無視するというほどのことでしかない。マルコフ連鎖の普通の理論では…ね。

JRF2013年4月18日2890

p が 1/2 でないランダムウォークってのは、いってみれば「中心」みたいなのが徐々にずれるから、0 には戻って来ない的に判断が下るわけだが、逆に、「中心」を追っかけていく…これを「再帰軸」と呼ぶ…と、それは再帰しているのと同じようなことにならないか…と考えた。

(つい [google: 再帰軸] を [google: 再生軸] っていっちゃいそうになるんだよな…。自分で定義した言葉だけど「再帰」はすでにあるからそこに合わさないといけないのに。)

JRF2013年4月18日9237

具体的に計算すると、p > 1/2 ならば、r_n = 2 * floor(p * n) - n、p < 1/2 ならば、r_n = 2 * ceil(p * n) - n とすれば、P{X_n = r_n | X_0 = 0} は、各項では 1/sqrt(n) ぐらいの感じで、0 に収束するけど、級数は発散するので、再帰に似た感じになる。

JRF2013年4月18日3046

(計算は、P{X_n = 2 * r - n} = Comb(n,r)* p^r * q^(n-r) だから、それにスターリング(Stirling)の公式［参２］を使えばいい。誤差項を含むところは、e^(-1) より大きくなるし、上の条件だと、常に 1/sqrt(n) のオーダーより大きいと言えるようになるから、1/sqrt(n) の級数が発散する以上、これで発散は証明できてるはず。)

(ちなみに floor は切り捨て、ceil は切り上げ、Comb は組み合わせの数の関数。)

JRF2013年4月18日4167

……。

で、上と違って、ここからはただの妄想。

この「再帰軸」、もっと自由に取ってもいいはずなんだよね。振動させたりしてもいいし、何だったら、回転させてもいい、うずまき型でもいい。r_n を r(i, X) = <j, Y> みたいな二変数関数にして、次を示す関数ということにすれば、一端は戻ってくるみたいなことも書ける。

JRF2013年4月18日0553

うずまき型にすれば、中央付近では再帰軸上だけでなくその周りが確率的に同じようなもの…「溶ける」と表現すべきか…になる。このあたり、伊藤の公式やブラックホールとかと考え方が似ている。

二変数関数の r が連続だというのは、のちのちには欲しいかもしれないが、離散的にはあまり意味がない。このあたり、ルベーグ積分的なのだろうか？

JRF2013年4月18日1740

再帰軸への吸収と既約の関係はどういうことになるのか。既約の定義の簡単さと、既約なときに再帰な状態と同値なのは再帰になるというのは、再帰軸がありそう…という立場からすると、信じがたい。再帰軸の r を使って既約を定義したり、「吸収」といった概念を定義したりしたいが、既約の定義のシンプルさが、どうも都合よくない。

再帰軸の方向に「吸収ベクトル」が向いている。「溶ける」と、ベクトルなしの「自由圈」になるという感じか？

でも、再帰軸の考え方って、要は、方向によって濃度が変わるということで、ちょっとおかしい。半導体か偏向グラスか、そんな感じではあるが…。

JRF2013年4月18日4817

……。

で、こういうことを考えはじめたのは、次の問題でつまずいたから。これは［参１］の第１章 2.4、ほぼこの本の最初に出てくる問題群の中の一つ。

「ギャンブラーは、次のような戦略で賭けに臨むものとする。２回続けて賭つ場合は、２ドル賭ける。そうでない場合には１ドル賭ける。時刻 n でのギャンブラーの財産を X_n とすると、この確率過程はマルコフ連鎖であると言えるか？」

JRF2013年4月18日0061

これって、「普通」に答えれば、マルコフ連鎖は現在の状態のみから次の状態が決まるものというのが定義だから、２つ前の状態が必要なこの問題に関してはマルコフ連鎖ではない…といった解答になるのだと思う。

JRF2013年4月18日1105

でも、情報工学者は、オートマトンを非決定性から決定性に直したり、最小化したりといった訓練を受けたことがあるから、状態をまとめて一つにするという操作が自然に思いつく。すると、一つ前が勝っているときは c が 1、負けてるときは c が 0 とし、現在の持ち金 X と合わせて、<c, X> を一つの状態として現せばいいとわかる。整数にしないといけないといったとしても、2 * X + c にすれば、整数に落ちる。

JRF2013年4月18日8774

ただ、これのマルチンゲールとかを求めるとき、期待値をとるのに、c がいっぱい足されたのを平均したみたいなのが X の項に及んでくると意味がないから、そこはオートマトンの最小化みたいな操作とか、何か写像を使ったりする必要があるのかもしれない。でも、少なくとも、「できない」という話ではないはず。

JRF2013年4月18日5447

それで「できないという話ではない」ということなら、やってみるべきなので、やろうと計算等をしたところ、上の「再生軸」のような問題意識が芽生えてきた。…ってのが経緯。

JRF2013年4月18日8869

それで、さっき Wikipedia を調べると N 階マルコフ連鎖(N 階マルコフ過程)という、まさに状態をまとめる話が書いてあって、きっとこのあたりはすでに解析されてるんだと思う。「再帰軸」の話もアイデアはありふれたものだと思う。

もうちょっと、自分でやってみるけど、この辺は適当に切り上げてもいいのかな…。

JRF2013年4月18日3388

［参１］
『マルコフ連鎖から格子確率モデルヘ』(R.B.シナジ 著, 今野＆林 訳, シュプリンガー・フェアラーク東京, 2001年)
http://www.amazon.co.jp/dp/4431708650

［参２］
『コルモゴロフの確率論入門』(A. コルモゴロフ et al. 著, 丸山＆馬場 訳, 森北出版, 2003年)
http://www.amazon.co.jp/dp/4627095112

JRF2013年4月18日0899

《マルコフ連鎖 - Wikipedia》
http://ja.wikipedia.org/wiki/%E3%83%9E%E3%83%AB%E3%82%B3%E3%83%95%E9%80%A3%E9%8E%96

JRF2013年4月18日1296

typo 「自由圈」→「自由圏」。

JRF2014/7/250878