確率数がエ

マルコフ連鎖の重要な性質

・既約性・再帰性・正再帰性・周期性

興味の興

平均再帰時間--収

平均吸収時間極 限 分 布
（定常分布

収束？

-

以降で、これらを調べる

既育進

咀（到達可能性）

I=10.1.2....｝：状態空間
o 状 態 j eI n 状 態 i f Iから到達進

越o I

n cos tP"という）>o（pco）（in）=1，が（ううぱはな）
は"Toうとうが相互到幸學
村やえーうかつるーっう（定義よりiii）
確率数理工学11

ン→○と書く.
noも入ってる.

か国と書く.

/ /1 / 10

した"

（推移的）

んーる，jいたならinたもチェックせよ.

y型（相互到達可能性の同値関係）

反射律（2） 対称律：
（I）

（う）

：

推移律：

うくーいた

（n=0でがない=1>o）i<→うi←>う，ういたかj e s ii ← > た（証明は各自で示してもらいたい）

1生

集合 B c I が 既 通（irreducible)

H e なるGBがえくーつる をみたす。
特にI（状態空間全体）が既約なら、そのマルコフ連鎖は既約であると言う

甠

集合Bc Iが閉じ（closed幽 なd B，なGBに対し、i+>う匤（同値類の例）

たい州に
𧪄：：：
0 1

00

1

（1tartに1，pair.Do）

確率数理工学11である。

）（13内から外に出れない）

た。※く 鬻

<○ーー既約⑦
だが、閉じてない.
2 / 10

!

再帰性
-_-

阯（初到達時刻）

状 態 が I への初到達't_これは確率変数
T t i nf { n 21| X n j }=ただし、 UnE l で X n キラなら T=とする.

f （うか= P（たくかどう）= I P （な=n | x。=i)：

到達確率
ー甠（再帰性）

らが再帰的 Edt
らが非再帰的越Nj-think I（必ずいつかは帰ってくる）「和来ないかも𦥯aマルコフ連全員が時刻に1.2....でるを訪れる回考

9には）：= P( N ; - o l X o =Thanf なん）=1ー

ん が 再帰的iえ（無限_回訪れる確率）i )⇐）9に.う）= Iが非再帰的 ← >gain)=0/※ gli.え）は0かI で中間はないTear

確率数理工学113 / 10

Proof-「初到達時刻の方法」： なの値によって事象を分割
P (N: Z n I X。こう）=高PCMZ n には、X。=j ) P（たた俗のT

時刻たで初めてうに到達& P( N ? I た = k ) Pしたた八にま）=n（：Markov性、時刻たでえにいるので、その前のことは忘れて良い）= & PCM z n t l X i i ) P （たFIX。こう）（時刻たと時刻0とおきかえる。すでに1回うに来ているので.

N i のカウントを1つ減らす）

P( N j z m l x i i ) E P （たた1にま）は、i )f（たくIx。=j ) =P=P ( N j ? a t IX。こう） f=i
=（すう）

なん）
P( N i z u l x - え ） f た が " ft h z e d=f （うん）が.が'IM-）やとすればこ こ で うこうとして.

8ない）=
11

橋 PCNjz.nlx i )=11P （だがい N o
確率数理工学11こう）=|fば""）(Ht.ん）=1）/4 / 10

Iんが再帰的 ← >なX。= j のときZntにFp(i i ) =.

しない(Xn#i)

N i - E z n であることに注意する（うと話すれる回数）.とする。

洋調収束

このとき

E [ E Z u IX。=i ]=F E [Znlx。ここに Iが（うん）

一方で、 この左辺は次のようにも言平価できる：

E [I Zn IX i n ]=E [N:11にうた

E lたE1N Nick}1が I

6=E P ( N i s hN i i )た1=首 Hi.いた が前の定理の証明より
よって、

確率数理工学11☹が再帰的⇐） fainに I t&がないにg5 / 10❤
❤
区（ランダムウォーク）

1回の推移で右に移る確率：p-1回のsP(Mt''（O.O）=0

Pに"（o.o）= （別pnqn=左：s1-p=S器，phqn(n回右の回左）Stirlingの公式より

n！三辰がなど"（し、Pah）（o.o)E 答なのでここで、 4 P G E 1 で、p=q=上のときのみなので、 以下をえる.

488斗た8ニシのとき（i）

E pGn）（o，。）=are再帰上（ii) ptqの と きEpに"（o.o）く

it

非再行連
4人。

.

確率数理工学11

2次元格子上のランダムウォークは再帰的（対称性は役割

3次元以上だと非再帰_的

6 / 10-既約性と 再帰性血い）状態のが再帰的かつ えいう なうえも再帰的に） 有限で閉じた集合A では再帰状態が少くともには存在.
Proof-（1）まずを示す （特におう）

H i .i ) = 1

らが再帰的なのでがんに1である。

えっるより、あるうこう。， i......☹にうなる経路が存在してp（うえ、）P(t.dz)-_-P にいる）>0

たからうへ至り、うからんへ2度と戻らない事象をとできる。 今、考えると.
0 =以上より.
すると、

1 - H i i ) ？ H i , i.）-_-P仙 は ） ( t fは、i D（えに戻らない）hf （えん）=1である。

iee>

lT

0hee

2からうに戻らないが！

うである。

tある m . n o が存在して、PCm)に.う）>o ,PC"（しん）70

で& paintた）は、う）と & が）は、う） P はどう）がなる）=がない（燄はない）がたま）
一> 。

、= 。 一>oたんは再帰的）=確率数理工学11

よって、うは再帰的.

o/7 / 10全ての h e A が非再帰的として、矛盾を導く。に）前の定理の証明より. な E I に対し、

E l N i N。こう]=I f に.が f は、いくである。よって、 A が有限であることよりo f

臿 E l N i lX。こう]= E [ 高 MIX。こう）であるが. A は閉じているため、常にその中に状態Xn はとどまるので、巫に前、N : = かとなるので、矛盾する.

y集合A が有限で既約かつ閉なら、 A の会い状態は再帰的である.
つはLem のに）より、 A 内に再帰的な状態が少くとも I

A は既約なので、なGAに対し、えっう である. うが再帰的なので、 Lenいうより沖再帰的/含まれる。それをえとする.

正（一致団結の性質）
同一の同値類に属する状態は全て再帰的か、全て非再帰的かのいずれかである.

yに Lemじ）より、ほぼ自明）
再帰性は既約成分全体の性質 クラスの性質※
ー

確率数理工学11ー

8 / 10直 （既約成分への分割）
下 に は I う E I でえーっう だがみつう）消滅部分
既約閉再帰的R F " Rュとすると、

I - T=( R i n Rj=中 には） p,、

R u Rw-_-と分割できて、 各 R t は_既約が国.
さらに. I

曜が有限なら全ての R k は再帰的のE I T

よって、〇x、消滅部分う）=12|i →う）
を と っ て き 2.CCとおくにから到達可能のG T より、任意の i t
つまり.

シ。〇，な領域）うなように対してる→んである。

なE C G ) は え か う である「たl E C Cう）は. た←つう. l ←ってであるので、 f e e dでもある。

すなわち、 C くん）は既約.

さらに、 C （う）は閉であることがわかる。 なぜなら、ある K E I に対して、 まーったであるとすると、

j ECG)として、えっるであることからえーった となるので、 k E C G ) である。 つまり、 C （う）は閉.

以上より、 CG)は既約かつ閉.
このようにして、各 i G E Tは既約が閉な集合C ( i ) に含まれている。もし、別の J E E T に関するC （う）が.（(DncC h i tをみなすなら、よって、ま たitうも成り立つので. （（う）=（くう）である。

R uRu-_-と分割できる。

Re は再帰的最後に.I が有限なら各 R tも有限なので、も前のy確率数理工学11Thinより

9 / 10齲""ii!がた：：：鬭
"P

B . . . RN T

R2R,

=r Q e, Q-z _ --_ --O N S-_--_-on!

※ T は消滅部分(dissipative point)と呼ぶ。
T は前の補題より. h e T は非再帰的（えが再帰的なら、おうであるとみたとなり、i 4 T となる.）

確率数理工学1110 / 10