マルコフ過程

マルコフ過程とは †

マルコフ性をもつ確率過程のことをいう。すなわち、未来の挙動が現在の値だけで決定され、過去の挙動と無関係であるという性質を持つ確率過程である。このような過程は例えば、確率的にしか記述できない物理現象の時間発展の様子に見られる。

アンドレイ・マルコフ †

Andrey (Andrei) Andreyevich Markov、1856年6月14日 - 1922年7月20日、日付はいずれも新暦）は、ロシアの数学者。特に確率過程論に関する業績で知られる。彼の研究成果は、後にマルコフ連鎖として知られるようになった。

同じアンドレイ・アンドレイヴィッチ・マルコフという名前を持つ彼の息子（1903 - 1979）もまた著名な数学者であり、構成的数学や再帰関数論の発展に寄与した。

アンドレイ・アンドレイヴィッチ・マルコフは、リャザンの森林管理局長を勤めていたアンドレイ・グリゴールヴィッチ・マルコフと、その最初の妻であったナジェージダ・ペトローヴナ・マルコワの息子として、リャザンの地で生まれた。

1866年、サンクトペテルブルク第5グラマースクールに入学

グラマー・スクール在学中の17歳の時に、彼はヴィクトール・ブニャコフスキー、アレクサンドル・コルキン、イェゴール・ゾロタレフといった数学者に対して、線形常微分方程式の全く新しい解法を提案しており、その結果コルキンの学生らが集ういわゆる「コルキンの土曜日」に招待された。

1874年に学校を卒業すると、彼はサンクトペテルブルク大学で物理数学の研究を始めた。

修士号を得た後の1880年秋に始まった。彼は私講師として、微積分の講義を行った。後に彼は解析学の入門講座、確率論（1882年に退職したチェビシェフの後任）、差分法などの講義を受け持った。1895/96年から1905年まで彼はさらに微分法の講義も担当した。

1886年に彼は特任教授に指名され、さらに科学アカデミー会員にも推挙された。ブニャコフスキーの死後、1890年にはアカデミーの特別メンバーとなった。

1894年には母校サンクトペテルブルク大学で、（通常の）教授職を得ることができた。

1896年には、チェビシェフの後継としてアカデミーの一般メンバーに推挙された。1905年に彼はmerited professor となり退職の権利を得たが、彼はすぐにそれを行使した。とは言え、彼は1910年まで差分法の講義を続けた。

1908年、学生運動との関連により、サンクトペテルブルク大学の教授・講師は彼らの学生を監視するよう命じられた。マルコフは最初にこの命令を拒否し、なぜ彼が「支配者の代理人」となることを拒否するのかの説明文を著した。マルコフは大学でこれ以上教育を続けることを拒否され、結局大学からは完全に退職することになった。

1913年、サンクトペテルブルク大学の評議会は9人の科学者を名誉会員として推挙した。マルコフもその中に含まれていたが、教育省は彼の推薦を認めなかった。しかしそのわずか4年後、1917年の2月革命の後に、推薦は認められることになった。マルコフは教壇に戻り、1922年に死去するまで確率論と差分法の講義を続けた。

↑

マルコフ性 †

マルコフ性（英: Markov property）とは、確率論における確率過程の持つ特性の一種で、その過程の将来状態の条件付き確率分布が、現在状態のみに依存し、過去のいかなる状態にも依存しない特性を持つことをいう。すなわち、過去の状態が与えられたとき、現在の状態（過程の経路）は条件付き独立である。マルコフ性のある確率過程をマルコフ過程と呼ぶ

↑

マルコフ連鎖 †

マルコフ連鎖とは、確率過程の一種であるマルコフ過程のうち、とりうる状態が離散的（有限または可算）なもの（離散状態マルコフ過程）をいう。また特に、時間が離散的なもの（時刻は添え字で表される）を指すことが多い（他に連続時間マルコフ過程というものもあり、これは時刻が連続である）。マルコフ連鎖は、未来の挙動が現在の値だけで決定され、過去の挙動と無関係である（マルコフ性）。各時刻において起こる状態変化（遷移または推移）に関して、マルコフ連鎖は遷移確率が過去の状態によらず、現在の状態のみによる系列である。

↑

有限状態マルコフ連鎖 †

状態空間が有限ならば、遷移確率分布は行列で表現され、これは遷移行列と呼ばれる。この行列Pの第(i, j)要素は

に等しい。さらに、マルコフ連鎖が時間的に均一、つまり遷移行列Pが添え字 n によらないならば、k-段階遷移確率は遷移行列のk乗、つまりPk と書ける。

定常分布π は行ベクトルで、次の式を満たす：

言い換えると、定常分布π は遷移行列の正規化された左側固有ベクトルで、その固有値は 1 である。

もしくはπ を、行列Pに対応する単位単体上の線形（連続）変換での不動点と見ることもできる。単位単体上の任意の連続変換は不動点を持つから、定常分布は必ず存在するが、一般にただ1つであるという保証はない。しかし、マルコフ連鎖が既約かつ非周期的ならば、定常分布πがただ1つ存在する。

さらにPkが、各行が定常分布πであるような行列に収束するならば、

（ここで1はすべての成分が1である列ベクトル）となる（ペロン・フロベニウスの定理）。つまり、時間が経つにつれてマルコフ連鎖は、初期分布に関わりなく、定常分布に収束するということである。

↑

状態推移図 †

↑

お天気の確率 †

晴と雨の2通りの状態とします。今日の状態から明日の状態への推移は、次の推移確率行列A={aij}で表わせるとします。

a11=1/2:晴-->晴
a12=2/3:雨-->晴
a21=1/2:晴-->雨 
a22=1/3:雨-->雨

この時、初期状態をx0=(0期に晴の確率、0期に雨の確率）とする。状態は、変数で定義すべきなので、X0=(θ0,1-θ0)'の確率ベクトルとしましょう。但しθ0(0<θ<1)です。 i期後の状態は、次のマルコフ連鎖で表わされる。

Xi+1=Axi
    =A^(i)x0

現在の状態は、前期の状態のみによって決まる（マルコフ性）から、任意の時点の状態も初期状態で、きまってくる。

問題１.XiをX0で、要素表示しなさい。
- 定常分布をΠベクトルとするとき
```
Π1=(1/2)Π1+(2/3)Π2
Π2=(1/2)Π1+(1/3)Π2
```
  となる。Π1=(4/3)Π２となり、確率なので合計Π1+Π2=1から、Π1=4/7、Π2=3/7が得られる。
- 一方、Aの固有値を計算してみよう。Ax=λx(λ：固有値)より
```
det|A - λI| = 0
```
  が成立する。これを特性方程式と呼ぶ。
```
(1/2-λ)(1/3-λ)-(1/2)(2/3)=0
λ^2-(1/2+1/3)λ-1/6=0
(λ-1)(6λ+1)=0
```
  固有値は１と-1/6である。まず、固有値１に対する固有ベクトルを求める。Ax=xなので[A-E]x=0となるベクトルである。
```
A-E=|-1/2  2/3|
    | 1/2 -2/3|
```
  なので、x'=(4,3)はこれにあてはまる。つぎに、1/6の固有値の固有ベクトルは,同様に
```
A-(1/6)E=|1/2+1/6  2/3    |
         |1/2      1/3+1/6| 
```
  なので　X'=(1,-1)はこれに当てはまる。これらを列ベクトルにもつ、変換行列　Ｔを定義する。
```
T = |4 1 |
    |3 -1|
```
  これを用いれば、AT=ΛT(Λは固有値を対角要素にもつ行列）なのでT-1AT=Λ　のように対角化できる。また
```
(T−1AT)(T−1AT)....(T−1AT) = T−1A^nT =Λ^n
```
  であるので
```
A^n=TΛ^nT-1
```
  のように、A^nも計算できる。このように線形漸化式のn期の一般解xn=A^nx0は、λ1=1のn乗とλ2=-1/6のn乗の線形和で得られる。
```
xn1=a(1)^n+b(-1/6)^n=a+b(-1/6)^n
xn2=1-xn1
```
  n=0では、初期状態と一致する必要がある。
```
a+b=θ0
```
  また、n-->無限大　では、定常分布に一致する必要がある。
```
a=4/7
```
  ゆえに、代入すれば
```
xn1=4/7+(θ0-4/7)(-1/6)^n
xn2=1-xn1
```
  と要素表示できる。

問題2.定常分布を求めなさい。
- i-->無限大の時、x=(4/7,3/7)
問題3.初期状態を観測された、お天気データ｛y1,ｙ2,....,yn}から推定する方法を見つけなさい.但しyt、t=1~n　は晴の時を１、雨の時０の値をとるものとする。
- θ0が与えられたときの、時刻tに晴れる確率をθtと置くと
```
θt=4/7+(θ0-4/7)(-1/6)^t
```
  である。このことから、t期のytの期待値は
```
E(yt|θ0)=１θt+0(1-θt)=θt
```
  この期待値と実績値Ytとの誤差は
```
et=Yt-θt
  =Yt-(4/7)[1-(-1/6)^t]-(-1/6)^tθ0
```
  と書くことができる。これは、未知数θ0の1次式になっているので
```
et=at+btθ0
```
  と書ける。全期間の誤差2乗和は,
```
J=Σet^2=Σ(at+btθ0)^2　t=1,n
```
  これを最小にするθ0を求めればよい。一階微分して0が必要条件なので計算する。
```
Σ2et(det/dθ0)=0
Σ (at+btθ0)bt=0
Σatbt+(Σbt^2)θ0=0
```
  以上より、最小二乗推定値は
```
θ0*= Σ(atbt)/Σ bt^2  Σはt=1,nの合計
ただし、
at=Yt-(4/7)[1-(-1/6)^t]
bt=-(-1/6)^t
```

↑

固有値を用いた対角化 †

固有値の定義 n 次の正方行列 A に対して，0 でないベクトル x があって，
```
Ax = λx 
```
が成り立つとき（ x ≠ 0 の解をもつとき），λ を A の固有値，x を固有ベクトル（一般的に，一意には決まらない．固有ベクトルをスカラー倍したものも固有ベクトルになる）という．したがって，固有値は，
```
|A - λI| = 0 （固有方程式，又は，特性方程式という） 
```
の根となる．
対角化とは n 次正方行列A が対角化可能であるための必要十分条件は, A がn 個の１次独立な固有ベクトルを持つことである. 　このとき, n 個の１次独立な固有ベクトルを縦ベクトルとして並べたものをP とすると, P−1AP は, 対応するn 個の固有値が対角線に並ぶ対角行列である.

推移確率行列

に対して, P^n を計算してみよう.

ここでは, p + q > 0 を仮定する. 固有値を求めると, 1, 1 − p − q となる. p + q > 0 を仮定しているから, この2 つの固有値は異なる. 固有ベクトルを求めて,それを使って対角化行列を計算すると
となる
であるので、P^nは次式で表わされる。

↑

ルーレット型ゲームのマルコフ連鎖　On a Markov chain roulette-type game †

A Markov chain on non-negative integers which arises in a roulette-type game is discussed. The transition probabilities are p01 = ρ, pNj = δNj, pi,i+W = q, pi,i−1 = p = 1 − q, 1 ≤ W < N, 0 ≤ ρ ≤ 1, N − W < j ≤ N and i = 1, 2, ..., N − W. Using formulae for the determinant of a partitioned matrix, a closed form expression for the solution of the Markov chain roulette-type game is deduced.

↑

ロシアン　ルーレット　の数学的理論 †

On the mathematical theory of splitting　and Russian roulette techniques

↑

ランダム　ウオーク　問題の例題 †

Exercise　of　Stochastic Processes A roulette wheel has 18 red pockets, 18 black pockets and 1 green pockets. On each spin, the roulette ball falls randomly into one of the pockets. A player starts with £60 and wins £1 if the roulette ball falls into a red pocket, and loses £1 otherwise. The player continues until losing all the money or reaching the target of £100. What is the probability that the player reaches the target? If the player bets £5 each time instead of £1, then what is the probability of reaching the target of £100. In each of the situations described above, what is the expected duration of the game. If the player bets £5 each time instead of £1, then what is the probability of reaching the target of £100. In each of the situations described above, what is the expected duration of the game.

We have p = 18/37 (the probability to win in each trial) and q = 19/37 (the probability to lose in each trial) so that q/p = 19/18. The player starts with £60, so k = 60, the target is £100, so N = 100. The probability that the player reaches the target is
```
Pr(reaching target) = (1 − (q/p)k)/(1 − (q/p)N)
= (1 − (19/18)60)/(1 − (19/18)100) .=. 0.111.
```
Betting £5 is like taking k = 60/5 = 12 and N = 100/5 = 20. So
```
Pr(reaching target) = (1 − (q/p)12)/(1 − (q/p)20) .=. 0.468.
```
The expected duration is
```
Dk=[N*( (1-(q/p)^k)/(1-(q/p)^N )-k]/(p-q)
```
so that for £1 bets we get
```
p=18/37,q=19/37,k=60,N=100
D60 .=.(100*0.111-60)/(p-q) .=. 1809.3
D12 .=.( 20*0.468-12)/(p-q) .=. 97.7  .
```

↑