#$

確 率 数 理 -!

❤

再帰性と到達の一咀（平均到達時間と平均再帰時間）
mini。）=状態iからjへの平均到達日跳上t|EたP（だたXI）=E1万1X。=i］（if P（なくかどう）=1）

wiythnhhhi
fには）（other

（Tj=int Inの1Xn=j｝）main）を平均再帰日
ー ー 寺 間品

甠（正再帰性）が再帰的なとき、うが正再帰的と呼ぶ

岬やmini）<o|iが零再帰的なman=。

（非再帰的なら自動的にmににaである）

再帰的再帰時間が..に非再帰的：再帰時間が無限になりう
有限𣟧蟵が再鱜熈一纃！
る灥_

確率数理工学12

1 / 12

%
平均到達時間の計啠.it？時刻にた倒長との後にえへ到達mには）=P（うま）×1+

高P（うた）|It mlk.
ttんかうたに行ってからうからyへI
stepで到達mいう） =う））

jに到達するのに必要な知数t㐂P（うた）m（たま）1じ がっ）t臿P（うた）=臿Hi.た）= 1 ）この方程式を各jごとに解く.

iうとすれば平均再帰時階でも求まる。

解が一意でなければ最小の非負解はいい）がそれになる-_⑧I I（証明は与えないが、補足資料の吸収確率の計算と同様に示せる.）（吸収確率）

i： 非 再 帰 的 な 状 態
で 再帰的な状態 も分解定理より、ある再帰的な既約成分に含まれる）
えからすへの吸収石屋-.-率d からのを含む再帰的な同値類への到達確率

I I

照

まが再帰的かつj→j'なら fは、お）=1である。

前田の講義資料より.Hi,if Iですが再帰的になることは示せている
よって、j'→なかっ.では再帰的なので、 再び同じ議論により、fはなに1でもニ ） このことから、ある，ぼには）で.

Hi.う）=f（うか）がわかる。
（まに到達すれば必ずおにも到達するし、逆もしかり）は" な隨再帰的製シズ前
同値に○はページに証明類

確率数理工学122 / 12

（参考）にだしは）について.Hi，た）=f（うら）になることの証明

Ht.た）=P(To Nii）？ftp.eETeegglなくせ）P（なくかい=i）
いさい

名を通ってから左に到達するがん=※な籅）哬くかどう）=がいたとかを逆にすれば、 f（う.た）Efは.た）も得るので、

ーfhた）=fはy吸収確率の計算方法ー

C（がまを含む再帰的な同値十選
T ： 非再帰的な元の集合
f（のう）=（閉かつ既約）

E Yimf（たの十岳pay f（たま）+EPに.た）性は）ーー；......、騃！！
この方程式を解けばたが、良臿、，Ri.た）tE,Hi.た）f（あま）い...................！！！！
たEC（ま）

ここでfは、う）=1

fair，=u（分解定理）

なので、f（うう）=解が一意でない場合は最小の非負解がそれ2なる.

確率数理工学123 / 12❤

亜ギャンブラーの破産確率でた。 . . . 式 確 率 所持金た産
8で雚万円（破産）十万円

資産iから始めて破産する確率を求めるにtho））

a(i）：んから始めて破産する確率

doに1，方程式：a(i）= p a l m ) tdo）=（には、-.-）

q aに り1plan）-a（う）］=q[a(i）-aにリ］

f aに）

|

a t

=

a(i） =p信）「（P#9）

した9=主）

ftp.i

k . あるd.PERを用いて書ける.

（i)

pのとき

（とう）

o Each)ElよりP=0よってdo）=1 から d = 1 なので91う）=1にもなくば9た）で言い（もう）we必ず破産する（ii) P = 9 のとき

O f a（う）E I

よりやはり f = 0do）=1 より の 二 I で aに）=1w（III)

P > 8 のときi →

一方、必ず破産する.

eでaに） → 人（h)である。

i=0で a（ 0） =ド f=1

よって 最小の非負解は d=0， P=1 で達成される。

つまり'am=（がe確率数理工学12t

運が良ければ破産しない
4 / 12%#

直 （平均再帰時間の性質と 正再帰性の条件）
任意のでるに対し、

橋 市

eP"では特にうが正再帰的 なTmは、かくか））=-_-到達確率いる）

m はま）が平均再帰時間

品方言P"'は、j ) > 0（湖はCornF )直感的な興 で郎"どう1は"から出発してのステップ目までに平均的にまに滞在していた時間の割合"である→mなの時間後にまに戻るので、まず、うからうへ到達する確執（うら）.うに到達したら、平均的に高いの割合でるに滞在していることになる。

Iyが既幽あるとする..

（I) まが正再帰的なら はE I に対想え部になる） .した。>o=（ii) うが零再帰的なら. h e I においてO

橋 が（こう）-二( H : I が既約で.うが再帰的なi f
I n C i ) は T h mより示せる
i )（うまに1であることはすでに示している.

は 自明ではない. 証 明 は 省 略 .

(Thanの Proof)
Z n={b 毖望らE l N j( n ) I X。=i ] =）←とする.

時刻hまでにうにいたN j（が臿Z た

回 数とする.

E E l Z E N . = i ] = 臿Pは'(i.う） に注意する.

（l) まず えこうて考える (X。こうこう）なん） を状態うた を固めに訪れた時間とする （だなint{に11NjmZEDTj'"=0 とする、
確率数理工学12

そんなんが無ければとする

5 / 12

theだただたり とする. すると.tkは独立同一分布に従う. （Mark.性）
大数の強法則よりよって、

聖 = t . t h tた- f g l E H . E E [ T H E う ］=mは、ま）と舞。，_

なかの定義より だが川）En<な姑は川

また、

なので、礜
晶く 瑫礜、"噐"壬Njcn）→（a）ここでるが再帰的であると仮定すると 毖らに"である。

よって・（b） 一方、T！資料は

品川_， m（まる） （GS）

うが非再帰的ならPCGNj(n）は1X。こう）=1 なので.
Fg(jig）

表明 ー ー つ か（a.S.）である。 一方、 うが非再帰的なら、mは、う）=

君川 →

聖= 芸

でもあるので、mは.j） （as.） を得る.

（ii) i t jのとき、+

嶤（i）.（i）より、（零再帰的なと.）-がえきた 出しない （なか_-（たい）

いずれにしても炭， _>｛M（えう）（ifT e a ）（otherwise,MS.）Na t ' s m1が11万人か （as)
確率数理工学126 / 12

%
両辺の期待値をとればルベーグの優収束定理より

格すだがいる）= 1機三ハ興Nii］==E傴興lx。=i］

E1=一，高，11なくがけ。こう］.P何かX。こう） の礜=定常分布と極y咀（定常分布）

T=（なり、TH....）： I上の分布

下が定常分布
※咀が坿た平衡方程式には者がいたうりxMarkov連鎖で更新しても分布が変わらない.

（定常分布が存在するとは限らない）（極限分布）（石は初期分布）た（うに Eた。（d）がいる）

はステップ目にどの状態にいやすいかを表した分布）

下 が t d t

任意のーーなに対し、

htn（う） =Tは）4離散分布なので法則収束）/（極限分布が存在するとは限らない）

h P"'=IP'た

極限分布
確率数理工学12（なE I））という形をしていなければいけない.
4石（う）=（Oo....，0.1，0，0，-_-）とすればわかる.
7 / 12

#。極限分布が存在すれば、それは一意的な定常分布である.

N Iit チェックせよ.

定常分布が存在しても極限分布が存在するとは限らない.

。

な例

た（註）， p =(Y'。） 下1になり、不は定常分布の、。

しかし、昨1！。，！！蠶，周期性がある→T o =（10）とすると、大にしたり、ー鼺鬱
ーで収束しない、極限分布は存在しない.

-T I （マルコフ連鎖の定常分布）

マルコフ連会員は 既通であると仮定する。

すると、以下は同値が正再帰的に） 全てのー E I が正再帰的ーま（I) ある j E I（ろ）で、何より正再帰性はクラスの性質）定常分布たが存在する。

（l).に1.13）のもと、定常分布は一意に定まり、たま）=で与えられる.

凸h t & P"（する）= 不，'。。

（まからすに戻ってくるまでの平たる時 なる）
mt
間正再帰的なまに対し、M ( i ) = &= O P( X n= ☹ ， な >nnとすると.

たのに 器，|x=うに平均的に痾の割合で滞在）j)まるを出発に再び2に戻るまでにどれくらいえにいたかは定常分布になる。

m（工の既知性は仮定していない、定常分布は一意とは限らない）
確率数理工学12（た（う）はまを出発してるに戻るまでに、どれくらいにに滞在していたかを表す）

8 / 12

(Lem のProof） まずµ（う） = p （どう，な>o l X。=j）=1 である（P（たくかたう）=1にも注意）

また、 垚 M i ） =E EP（たん.な>n|Xi j ）= I N T > n Mir）
= & H T z n Iがる）
=E [ T . g l X。=j］ =m（おう）

なので.
では確率分布になる.FM？.i）=PNe=i.Tj7llXo=ま）F M ( N P(i,k）=とすると、 Mの定義より

EFT'か（うん）Pいた）である。 右辺=M（た）ならではµ）は定常分布になる.
（i）（たキシのとき）ET"'（う、i)Mink）

==

=
=

ここで.
（ii）

E H X i n ， た > l . Xe i た I X。こう）P（た>l、 X e i た I X。こう）P(T.pl+1， X e い た I X。こう）FM"（うた）（右辺）= M k ）Eはすぐわかる。

ぐうきた）（うきたに注意）（たまのとき）上と同様にET）は.'d)P(i.た）EP(Xii，な>e,Xen=！Iがる）
==

このとき、

確率数理工学12

P（た=1+1 1X。=j）☆（右辺）= P（な<o |X。=ま）=1 =1（う）y9 / 12

#(Proof of Thin）（2）→ （ 1 ）!

は明らか.

（I） -）（2）

Iを任意に取る. るEIは正再帰的であるとする

i E

既約性より. it

よって、ヨを，m E I N でjである。
PG）（う.う）>0.PCM）（すえ）>0 より、

だれに f i s t EP"（iii)
fis F i E

E=>𥫣とのがないが𤇾での器はいhtfneie礐e痴'Tjは正再帰的.

o

な り えは正再帰的.

mの性質より）

なが正再帰的なう。直前のLemよりある定常分布が存在する.

（2）→（3）（3） 一つに）既約性より、定常分布のに対し.た（う）>0なようについて.にGIでないんであるよって、あるMEI N で M Yj , i D oとできる. よって下に）= FT（う'）が）は！iに大（ま）がない）70となる.

t.ci
答

熱熱！な？
な EIにおいて分ば布なので）た。 元は）にEPM(kia））

表にした）fm
優骨着 は、う）
e e

確率数理工学1210 / 12

!
これと たくう）>0を合わせるとFj>0である。

よって、mは、かくか、つまりまは正再帰的.

特にまは再帰的.

既約性と再帰性より、tした。また1作）となり、T（うになるか）が成り立つ（一意性） 上の議論で、たまに なるか）が言えてしまっているので、一意性も示されている。

x咀 （周期性）

なるMIIの最大公約な久しま
この周期d（う）= ド（in)soえ←>jならdに）=d（う）

T I（周期はクラスの性𥫣

（極限分布の存在条件）

マルコフ連全員が既約であるとする。

連鎖が｛正再 な帰的 非周期的N I

この極限分布は定常分布でt極限分布不は）=t で与えられる.

正再帰的なら定常分布が存在.

凸

既約で正再帰的なマルコフ連鎖が非周期的ならもう.うEI で

f i g PG）（i.ま）=_たくう）（定常分布）.

=周期的（dには2）なら. PG）（i.う）は収束しない（証明は、カップリング法による.補足資料を参照のこと）
確率数理工学1211 / 12

(Proof o f Thin)(い） Lem による.に ） 極限分布が存在すれば、定常分布が存在するので、正再帰的また、先の Lem より周期的ならがいる）は収束せず極限分布が存在しなくなるので、非周期的でなくてはいけない

aT d （大数の強法則）

既約かつ定常分布たが存在するとき、 （極限分布の存在は仮定しない）
f : I → R が 炁 I f（ り け い ） < e （つまりた、[If( i ) 1 ] < a )なら、六点f (Xた） - ） E T H
品連鎖「1積分]（9.

x※ 大数の強法則により、 MCMC法が正当化される.

確率数理工学12

12 / 12