2017年8月31日木曜日

Markov Chains and Monte Carlo Methods 01日目

Ioana A. Cosma and Ludger Evers, Markov Chains and Monte Carlo Methods
http://users.aims.ac.za/~ioana/notes.pdf
CC-by-nc-sa 2.5
http://creativecommons.org/licenses/by-nc-sa/2.5/za/legalcode

Chapter 1. Markov Chains

1.1 Stochastic processes

Markov chain は無記憶性という特別な性質を持つ確率過程の一種である. Markov chainをよく学ぶため,まずはStochastic processの概念を形式的に定義する.

Definition 1.1 (Stochastic process)

がstochastic processである
という,を添字集合とした確率変数の集合であって,domainとrangeは共通である. は”time”(時刻)で,は”state space”(状態空間)と呼ばれる.

には様々な集合が考えられるが,我々が当面扱うのはが離散的な集合である場合(stochastic processes in discrete time)で,例えばの場合である. ほかにはのような連続時間における過程やのような空間的な過程を考えることもある.
また,がどのような集合かも問題で,が離散的な集合であれば(がr.v.として離散的であれば),このような過程を離散過程(discrete process)という.

Definition 1.2 (Sample path)

について,におけるsample path という.

ならばsample pathは点列で,ならばsample pathはなる関数である.
fig.1.1はsample pathの例である.
figure 1.1
stochastic processはのそれぞれの分布のみではなく,それらの依存関係によっても特徴づけられる. この依存関係の構造はprocessのfinite-dimentional distributionsによって表現できる.すなわち

という具合である. であればjoint distibution function(同時分布)は

と記述できる.



を満たすとき,のfinite dimentional distribution functionはconsistentであるという.
stochastic process について,がfinite dimentional distributionsによって完全に記述できるか否かについての部分的な答えが以下の定理である.

Theorem 1.3 (Kolmogorov)

はconsistent なfinite-dimensional distribution functionの族とする. このとき,以下を満たすprobability spaceとstochastic process が存在する.

この定理から,あるprocessのfinite-dimensional distributionsを与えれば,そのprocessを特徴づけられる(本当か?). ただし,あるfinite-dimensional distributionsによって特徴づけられるは一意ではない. しかし,そのdistributionsはたかだか可算個のr.v.によるeventの全てに確率を一意に割り当てることができて,この講義の範囲ではそれで十分である.

1.2 Discrete Markov chains

1.2.1 Introduction

この節ではMarkov chainのうち,とくにであるときを考える. これをdiscrete Markov processと呼ぶことはすでに述べた(の時も含むが,深くは考えない). discrete Markvo processではとして一般性を失わない.

Definition 1.4 (Discrete Markov chain)

はdiscrete stochastic processで,しかも時間についてもdiscreteとする.
がMarkov chain (with discrete state space)

またこの性質をMarkov propertyという.

この定義は,ある時刻における状態がその直前の時刻における状態のみによって決まる(確率的)ということの定式化である.

Proposition 1.5

Markov propertyが成立する
任意のについて

Example 1.1 (Phone line)

電話線が使われている状態(1とする)と使われていない状態(0とする)があって,毎分この電話線を監監視する過程のstochastic processを考える. がMarkov chainと仮定する. すなわち,これまでどれほど長く電話をしていても1分間後にその電話が切れている確率は変わらず,同様にどれほど長く電話がかかってこなかったとしても1分後に電話がかかってきている確率は変わらない仮定する. Markov assumptionはが同じ分布であることを要求しないので,(は昼頃), (は深夜)というふうに,時刻によって利用のパターンが異なるモデルにも適用できる.

Example 1.2 (Random walk on )

から始まるrandom walkという確率過程を考える. 全ての時刻で,次の時刻に今あるstateにとどまるか,+1進むか,-1進むかを確率的に選ぶ過程である. 現在あるstateにかかわらず,そのstateにとどまる確率を, -1進む確率を, 進む確率をとする.である.
を,任意のに成立するr.v. によって

と記述する.このとき

であることは明らかである.さらに

が成り立つから,はMarkov chainである.

Markov chainの分布は初期分布によって完全に定まる.さらに*transition probabilitiesを と定めると,以下の命題が成立する.

Proposition 1.6

discrete Markov chain について,

proof.

この証明の1つめの等号は全てのr.v.の組に成立するが,2つ目の等号が成立するのはMarkov chain特有である.
Homogeneous Markov chainという更に特別なクラスはによってが変化せず,非常に扱いやすい.以下,全てのMarkov chainはhomogeneousとする.

Definition 1.7 (Homogeneous Markov Chain)

Markov chain がhomogeneous
というによらない実数が,任意のに存在する.

Definition (initial distribution)

initial distributionをと書く.の組によってhomogeneous Markov chainの分布は完全に定まる(後述).

Definition 1.8 (Transition kernel)


という行列をhomogeneous Markov chain のtransition kernelとかtransition matrixという.
が成立する.

Example 1.3 (Phone line(continued))



とするとき,transition kernelは

となる. transition probabilityを有向グラフを使って表現することが有る. Markov graphという. この例のMarkov graphはfig. 1.4のようになる.

Example 1.4 (Random walk on (continued))

前に挙げたrandom walkのhomogeneous Markov chainのtransition kernelは行,列ともに無限大のToeplitz matrix(テープリッツ行列)で,具体的には

という形をしている.

Definition 1.9 (m-step transition kernel)

homogeneous Markov chain について,-step transition kernelという.

Proposition 1.10

をhomogeneous Markov chainとすると,
i.
ii.
が成立する.

proof.

i. を示す.

ゆえにがたしかに成立し,帰納法によりである.
ii.

Example 1.5 (phone line(continued))


のm-step transition kernelは

1.2.2 Classificaton of states

Definition 1.11 (classification of states)

(a) あるがあって,が成り立つときを導くといい,と書く.
(b) であるときはcommunicateするといい,と書く.このときは同値関係である.

に同値関係を入れられたから,で同値類別できる. ある同値類の全ての元で他のの元に出るpathが無いとき(), はclosedであるという. ある同値類の元は様々な性質を共有していることをあとで示す.

Example 1.6


をtransition kernelにもつMarkov chainのMarkov graphはfig. 1.5のとおりである. が見て取れて,同値類別はであり,特にのみがclosedである.

figure 1.5

Definition 1.12 (Irreducibility)

の全ての元が互いにcommunicateするときはirreducibleであるという.

phone lineの例とrandom walkの例はreducibleであり,example 1.6はirreducibleである. ところで,ex. 1.6において,から再びに至るのは,から,から,からというステップを踏まなければならないので,
である. このような振る舞いをperiodicityという.

Definition 1.13 (Period)

(a) のperiod

と定める. periodを持たないstateも存在する.
(b) なら,aperiodicという.
(c) なら,periodicという.

Example 1.7 (Ex. 1.6 continued)

すでに述べたようにである. 同様にである.
まただから,.すなわちはaperiodicである.
ある同値類(以後,communicateによる同値類をcommunicating classか,単にclassという)においてperiodを共有しているのは偶然ではない.

Proposition 1.14

(a) あるclassの全ての元はperiodを共有する.
(b) irreducible chainでは全ての元はperiodを共有する.

1.2.3 Recurrence and transience

ex. 1.6のMarkov chainを辿り続けると,そのうちを往復するだけになる. このような振る舞いを定式化するため, number of visits in state :

を導入する. 初期値がであるときの条件付き期待値は

この値が有限か無限かによってstateを分類する.

Definition 1.15 (Recurrence and transience)

(a) がrucurrent

(b) がtransient

すなわち,がa.s.無限回訪れられるというのがrecurrentで,a.s.有限回訪れられるというのがtransientである.
prop. 1.14から,あるcommunication classの元たちはrecurrentであるか否かを共有する.

Proposition 1.16

あるcommunicating classにおいて,全ての元がrecurrentであるか,全ての元がtransientであるかのどちらかが成立する.

proof.

ならば,からに至る長さのpathがあり,からに一有る長さのpathがある. すなわちである.
とすると,

((1): からに行って,さらに後にまたに戻って,そこからに戻るという確率)
よってもまたtransientである.
またがrecurrentであるとき,

から,もrecurrent.

Proposition 1.17

(a) closedでないclassはtransient
(b) 有限かつclosedなclassはrecurrent

Example 1.8 (ex.16, 1.7 continued)

ex.1.6において,はclosedでないからtransient.
一方は有限かつclosedなのでrecurrent.

1.2.4 Invariant distribution and equilibrium

invariant distributionを導入して,Markov chainの長期的な振る舞いを調べる.

Definition 1.18 (Invariant distribution)

上のprobablility distributionとする. またがMarkov chainでtransition kernel をもつとする. invariant distribution (stationary distibution)

さらにこのとき,右からを掛けることで,

が成立する.したがってprop. 1.10より

が任意のに成立する. つまり,の分布は時刻によって変化しない.

Example 1.9 (Phone line (continued))


のstationary distributionを見つける.
を変形して,.よってのeigenvector(固有ベクトル)であって,ただし確率の公理からのそれぞれの要素は非負で,総和は1である.これを解くと,である.
Markov chainは必ずしもstationary distributionを持たない.上のrandom walkがその例である.

Example 1.10 (Random walk on Z (continued))


であることはすでに言った.の唯一の解だが,は無限次元のベクトルなので正規化できない.

ある種のMarkov chainは長期的にはstationary distributionに至る.

Theorem 1.19 (convergence to equilibrium)

がirreducibleかつaperiodicなMarkov chainで,stationary distribution をもつとする.このとき

が任意のに成立する.

proof. (sketch)

のinitial distribution, transition kernelをそれぞれ, とする. initial distribution (stational)とtransition matrix をもつ新しいMarkov chain を定める. またが初めてに同時に到達する時刻の確率変数をとする.すなわち

さらにであり,また新しいprocess

によって定める. の概略はfig.1.6のようになる. はinitial distribution をもち,transition kernel である. したがっては常に同じ分布を持つ.すなわちである.
のinitial distributionはstationaryなので,である. においてであって,ゆえに

Example 1.11 (Phone line (continued))

phone lineの例で,だから,.

Example 1.12

Theorem 1.19におけるaperiodicityの仮定が必須であることを示す.
, とする. これは明らかにirreducibleだがperiod 2である. stationary distibutionはだが,これは決定論的な過程だから,明らかにはこれに収束しない.

1.2.5 Reversibility and detailed balance

のように,現在(あるいは過去)を条件にした未来の状態の確率を論じてきたが,今度は逆に未来の状態を条件にした過去あるいは現在の状態の確率を議論する.

のように条件付き確率の前後が交換できるのはBayesの定理の教えるところである.
chainを逆に辿っていくような新しいMarkov chainの定義を動機づける.

definition 1.20 (Time-reversed chain)

について,をMarkov chainとする. とすると,のtime-reversed chainという.

である.

がhomogeneousでもがhomogeneousとは限らない.
しかし,のinitial distributionがstational であれば,が任意のに実数として決まって,

が成立するから,はhomogeneousである.

Example 1.13(Photo line(cont.))

すでに挙げた例で,
だから, 式(1.2)により

以上よりこの例ではは同じtransition probabilityをもつ. このようなchainはtime-reversibleであるという.

time-reversible であるか否かを判別する基準を導入する.

Definition 1.21 (Detailed balance, 詳細釣り合い条件)

transition kernel がdistribution によってdetailed balanceを満たす

detailed balanceは後で学ぶMarkov Chain Monte Carlo(MCMC)の議論でも極めて重要な役割を果たす. detailed balanceを満たすはstationary distributionであり,これはdef. 1.19の定義よりも扱いやすいことが多い.

Theorem 1.22

はMarkov chainで,そのtransition matrix をはdetailed balanceをによって満たすとする.このとき
(i) のstationary distributionである.
(ii) がinitial distributionであれば,はtime-reverisbleである.

proof.

(i)仮定より

((1): distributionの定義 (2): detailed balanceの定義)
よって確かにだから,はstationary distributionである.
(ii) のtime-reversalとする.

(1): 式1.2 (2): detailed balanceの定義
よって確かにはtransition matrixを共有する

一方,stationary distributionを持つからと行ってtime-reversibleであるとは限らない.

Example 1.14

.

というMarkov chainを考えると,stationary distributionは. Markov graphはfig.1.7の通り.
enter image description here
(1.2)からtime-reversed chain のtransition matrixが

と得られるが,これはと異なる行列である.

0 件のコメント:

コメントを投稿