❤

確 率 数 理 再帰性と到達の一
咀（平均到達時間と平均再帰時間）
mini。）=状態うからうへの平均到達時間ーーt ） 点 k P(Tj=k|X|）=E1 万 1X。=i"行 く か と な り 、 ， ，］"(otherwise）

o（ Tj=inf i n a l Xn=j｝）_f には）" " ' を 平- 均_ 再- 帰間， 、 呼 ぶ品

甠（正再帰性）が再帰的とする。このとき、うが正再帰的岬や m(in）<o| i が零再帰的な main）=（非再帰的なら自動的に m いん）=である.）

再帰的豳時間が.に有限𣟧で非再帰的：再帰時間が無限になりうる.
邈.it？？-！麤
確率数理工学12 (2023)

1 / 12

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

うから y へ s
I tepでm いう） =到 達

I tftmlk.
う））

んかうたに行ってからj に到達するのに必要な知数

1 t 㐂 P（うた）m（たま）じ がっ）t臿 P（うた）=臿 Hi.た）= 1 ）この方程式を各 j ごとに解く.
i うとすれば平均再帰時階でも求まる。

解が一意でなければ最小の非負解はいい）がそれになる-_⑧

I I（証明は与えないが、補足資料の吸収確率の計算と同様に示せる.）（吸収確率）

i： 非 再 帰 的 な 状 態
で再帰的な状態も分解定理より、ある再帰的な既約成分に含まれる）

えからすへの吸収石屋-.-率 d からのを含む再帰的な同値類への到達確率
I I

照

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

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

類

確率数理工学12 (2023)

2 / 12

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

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

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

ー

吸収確率の計算方法ー

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

ここでなので、（閉かつ既約）

E Yimf（たの十岳 payf（たま）+EP に.た）性は）
たEICは）-T
騃！！たf は、う）=1
た EC（ま）（分解定理）が、
fair，=uf（うう）= 臿、，Ri.た）tE,Hi.た）f（あま）ニ ） この方程式を角平けば良い（vg.ecm n u z Hi,j'）=f には）とすれば良い）解が一意でない場合は最小の非負解がそれ 2 なる-_-

確率数理工学12 (2023)

3 / 12

❤

亜

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

（破産）

万 円

資産 i から始めて破産する確率を求める
a(i）：んから始めて破産する確率do に 1，方程式：a(i）= p a l m ) tdo）=に tho））（には、-.-）

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

f a に）|a t=a(i） =p 信）「（P#9）

した 9=主）

ftp.i

R を用いて書ける.
k . ある d.PE（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 でw（III)P > 8 のとき

i →a に）=1必ず破産する.

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

一方、 i=0 で a（ 0） =ド f=1よって 最小の非負解は d=0， P=1 で達成される。

つまり'

am=（がe

確率数理工学12 (2023)

t

運が良ければ破産しない
4 / 12%直（平均再帰時間の性質と 正再帰性の条件）
任意のでるに対し、無言&Phi,j）
特にうが正再帰的 なTm は、かくか）と譽に到達確率=の ，が平均再帰時間

島方言 P"'は、j）>0（湖は CornF ）直感的な興 で郎"どう 1 は"から出発して n ステップ目までに平均的にまに滞在していた時間の割合"である→

まず、うからうへ到達する確執（うら）.うに到達したら、m なる時間後にまに戻るので、平均的に高いの割合でるに滞在していることになる。

y

I が既製あるとする.
（I） まが正再帰的なら に EI に 対ht 部になる）=.した。，

so(ii） うが零再帰的なら. h e I に お い て

二 O 橋（H:が（こう）I が既約で.うが再帰的なら、f（うまに 1 であることはすでに示している.

I n Ci）は Thm より示せるi ） は自明ではない. 証 明 は 省 略 .に時刻のまでにも甾巌（Than の Proof)

Zn=｛f 毖望らE l Nj(n)IX。=i］ =（l） ま ず）

えこうて考えるとする.

Nj（が高 Z た とする.

E E l Z E N . = i ］ = 臿 P は'（i.う） に注意する.
（X。こうこう）なん） を状態うた を固めに訪れた時間とする （だな int｛に 11NjmZEDTj'"=0 とする、
確率数理工学12 (2023)

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

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

聖 = たけたでた學 ，器 EH，］=E［な 1 どう］=m は、ま）と憥羅瑩山、

また、 なかの定義より だな""En くな""が川なので、礜壬晶く 瑫礜、"噐"である（a）ここで Iが再帰的であると仮定すると Nj(n）→よって・は（ように 1）

（as）

品川_， m（まる） （GS）（b） 一方、 うが非再帰的なら

PCGNj(n）は 1X。こう）=1 なので.
Fg(jig）

表明 ー ー つ か（a.S.）である。 一方、 うが非再帰的なら、m は、う）=（ii) i t j のとき、

聖= 芸嶤

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

君川 →（i）.（i）より、、前田資料より.

+-がえきた 出しない （なか_-（たい）

いずれにしても炭，->｛Mなる）（if た<a）（otherwise,MS.）

告白に なっ m 前，

11 万人が （as)

確率数理工学12 (2023)

6 / 12

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

桔すだがいる）= 1 稿三 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 (2023)（な EI））という形をしていなければいけない.
4 石（う）=（Oo....，0.1，0，0，-_-）とすればわかる.
7 / 12

!

N I。極限分布が存在すれば、それは一意的な定常分布である.
it チェックせよ.

。

定常分布が存在しても極限分布が存在するとは限らない.
な 例 た（註），p=（Y'。） 下 1になり、不は定常分布①、_「2〇(n：奇数）
しかし、がた［P（り） （n：偶数）

周期性がある→To=（10） とすると.

た=1 にい 鼺鬱

で収束しない、極限分布は存在しない-_--TI（マルコフ連鎖の定常分布）

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

すると、以下は同値（I） あ る jE I が 正 再 帰 的に） 全てのーーま EI が正再帰的（3）にりにはり正再帰性はクラスの性質）

定常分布たが存在する。

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

凸h EP"は、ま）= は_，（まからすに戻ってくるまでの平たる時間 m なる）t うに平均的に痾の正再帰的なまに対し、E。P(Xn=M(N=とすると.

たのに m 器，割合で滞在），な>n|x=j）まるを出発に再び 2 に戻るまでには定常分布になる。

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

8 / 12

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

また、 垚 Mi） =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 の定義より

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

==

=
=

ここで.
（ii）

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

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

このとき、☆（右辺）= P（な<o |X。=ま）=1 =1（う）

確率数理工学12 (2023)

y

9 / 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)
E fis F i E
𥫣とのがないが=>なり

𤇾での器はい htfneie

礐e痴'Tj は正再帰的.

oえは正再帰的.

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

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

t.ci
答

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

優骨着確率数理工学12 (2023)

表にした）fmは、う）
10 / 12!
Fj>0 である。

これと たくう）>0 を合わせるとよって、m は、かくか、つまりまは正再帰的. 特にまは再帰的.
既約性と再帰性より、t した。また 1 作）となり、T（うに なるか）が成り立つ（一意性） 上の議論で、たまに なるか）が言えてしまっているので、一意性も示されている。

咀（周期性）

x

なる MII の最大公約な久しま
この周期 d（う）=ド（in)so

え ←>jなら dに）=d（う）

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

（極限分布の存在条件）

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

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

この極限分布は定常分布でt

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

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

凸

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

I で

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

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

11 / 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 (2023)

12 / 12