マルコフ過程とは

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

アンドレイ・マルコフ

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)要素は

markovchane1.png

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

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

markovchane2.png

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

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

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

markovchane3.png

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

状態推移図

StateTransitionDiagram.JPG

お天気の確率

晴と雨の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

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

  • 問題1.XiをX0で、要素表示しなさい。
    • 定常分布をΠベクトルとするとき
      Π1=(1/2)Π1+(2/3)Π2
      Π2=(1/2)Π1+(1/3)Π2
      となる。Π1=(4/3)Π2となり、確率なので合計Π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と-1/6である。 まず、固有値1に対する固有ベクトルを求める。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を定義する。
      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,y2,....,yn}から推定する方法を見つけなさい.但しyt、t=1~n は晴の時を1、雨の時0の値をとるものとする。
    • θ0が与えられたときの、時刻tに晴れる確率をθtと置くと
      θt=4/7+(θ0-4/7)(-1/6)^t
      である。このことから、t期のytの期待値は
      E(yt|θ0)=1θ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 個の1次独立な固有ベクトルを持つことである.  このとき, n 個の1次独立な固有ベクトルを縦ベクトルとして並べたものをP とすると, P−1AP は, 対応するn 個の固有値が対角線に並ぶ対角行列である.

推移確率行列

StateTransitionMatrix.JPG

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

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

ルーレット型ゲームのマルコフ連鎖 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  .

マルコフ過程

A氏とB氏が、ホームページを持っている。当初、A氏の閲覧量は、2人合計の閲覧量の10%であった。B氏は90%なので、a0=0.1、bo=0.9で表そう。 ある時、A氏がとても良い記事を書いたので、B氏がリンクを参照したところ、その後、A氏の以前のシェアの90%を確保しつつ、B氏のシェアの20%が、A氏のページを見るようになった。 そして、B氏は残り80%のシェアを確保しつつ、A氏のシェアの10%がB氏のページを見るようになった。

  • この関係は、次式で表される。
    ak+1=0.9*ak+0.2*bk
    bk+1=0.1*ak+o.8*bk
    初期状態 a0=0.1、bo=0.9
    この連立漸化式は、ベクトル表示すれば
    Xk+1=A*xk
    Xk=(ak,bk)
    のように、表されます。
  • k 年より後の状態はk 年の状態によって、全て決まり,状態間の遷移(移り変わり)は行列A の成分ai j でj 状態からi 状態への遷移確率(aij) として表されます.状態の変動をこのようにモデル化することをマルコフ過程といい,特に上の例のように時間が離散的である場合を「マルコフ連鎖」といいます。
  • 漸化式xk+1 = Axk の解はxn = Anx0 で与えられるから,A を対角化してAn を計算すれば済みます.それは練習問題にしましょう.
  • 解法:特性方程式 det|A-λI|=0を解く。固有値は、λ = (1, 0.7)それらに対応 する固有ベクトルを並べた変換行列はPは、1行が(2 ,1)、2行が(1, −1)の行列です。したがって,
    D = P^(−1)AP は、対角要素に1, 0.7を持ち、他は0の要素をもつ対角行列。
    A^n = [PDP^(−1)]^n = PD^nP^(−1)
    これを計算すれば、n期の状態X^nは
    markov.JPG
    で表せます。
  • n->無限大での最終状態は、x=Axの解です。これは、n-->∞  で 0.7^n-->0なので、x1=200/3=67%に近づく。A氏とB氏の閲覧量の比は、67%対33%に最終的になります。

上記は、ホームページの例題ですが、ビールや携帯などでも、最新時点の販売量のシェアと、最新の期間の販売シェアの推移行列を用いて、将来のシェアを予測し生産計画を立てる場合などにも、応用できます。

ガウス=マルコフの定理とは

あるパラメタを観測値の線形結合で推定するとき、残差を最小にするような最小二乗法で求めた推定値が、不偏で最小の分散を持つことを保証する定理である。


添付ファイル: fileStateTransitionDiagram.JPG 408件 [詳細] fileDiagonalTransformation.JPG 424件 [詳細] filePTmatrix.JPG 416件 [詳細] fileTmatrix.JPG 417件 [詳細] fileStateTransitionMatrix.JPG 442件 [詳細] filemarkov.JPG 478件 [詳細] filemarkovchane3.png 454件 [詳細] filemarkovchane1.png 534件 [詳細] filemarkovchane2.png 463件 [詳細]

トップ   差分 バックアップ リロード   一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2010-09-21 (火) 13:23:00 (3339d)