確 率 数 が エ

マルコフ連鎖の重要な性質
・既約性・再帰性・正再帰性・周期性

興味の興
-

-

収

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

収束？

-

以降で、これらを調べる

既育進

咀（到達可能性）
I=10.1.2....｝：状態空間。状態 ifI か ら 状 態 j eI へ 到 達 籅越o In cos tP"という）>o

ン →○と書く.
（がいう）=1，呦（うえに。（うな）
o う ととする）、北うが相互到幸興

はえーうかつるーっう（定義よりうか）
確率数理工学11 (2023)

か国と書く./，
1 / 10

した"

（推移的）

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

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

反射律

（I）

：

うくーいた

（n=0 でがない=1>o）（2）

対称律：i<→ う（う）

推移律：

i

←>う，ういたj e s iかi ← > た（証明は各自で示してもらいたい）

1生

集合 B c I が 既 通（irreducible)

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

集合 Bc I が閉じ（closed幽 な d B，な GB に対し、i+>う匤（同値類の例）
た い 州に
𧪄：：：
0 /oo

1

（1tart に 1，pair.Do）

確率数理工学11 (2023)である。

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

た。※
く 鬻
○名

_既約だが閉じてない.
2 / 10酢型!

阯（初到達時刻）

状態が I への初到達選T「恣鬱競煮ことに注意）

tinffnz.tl xn=j｝

ただし、 UnEl で Xn キラなら T=とする.

f（うか= P（たくかどう）=IP（な=n|x。=i）：到達劯選甠（再帰性）
らが再帰的 Edtfなん）=1らが非再帰的越 t h i n k INj（戻って来ないかも𤇾

マルコフ連全員が時刻に 1.2....でるを訪れる回考

9 には）：=P(N；-ol X o = i ）直（糙いっかは帰ってくる）

え（無限 1_回訪れる確率）

んが 再 帰 的⇐ ）9（う.i に Ii が非再帰的← >gain）=0/※ gli.え）は 0 か I で 中 門 等

確率数理工学11 (2023)

3 / 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 にま）P（たく I x。=j ) = f は、i )=P ( N j ? a t IX。こう） f=i=（すう）

P ( N i z u l x - え ） f た が " f なん）t h z e d=f （うん）が.が'I
こ こ でうこうとして. M-）やとすれば8 ない）= 橋 PCNjz.nlx
1111P （だがい N oこう）
確率数理工学11 (2023)=i )=|fば""）(Ht.ん）=1）/4 / 10

#I

んが再帰的 ← >なX。=j のときZntとする。にFp（i.i）=

しない（Xn#i）

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

このとき.

E l Ezulx。=i］=瀧豳で 1 とジ］=I がいい

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

E [ EZn IXin］=

E[Nil とこうた ETH Nick}Nil=IP(Nish N i i ）二首 Hi.いた
よって、が再帰的⇐ f（でん）=I #）確率数理工学11 (2023)が前の定理の証明より

EP（でん）=g5 / 10❤
❤
区（ランダムウォーク）nigerien

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

P に"（o.o）= （別 pnqn=

(n 回右の回左）Stirling の公式よりPah）（o.o)E左s

器 ，phqn

n！三辰がなど"（し、答：1-p=q

ここで、なので4PGE1 で、p=q=上のときのみ 488=1

邈！！4 強が 4 に於いた 8 ニシのとき（i）

E pGn）（o，。）=

are 再帰上（ii) ptq の と き

Ep に"（o.o）く

it

非再行連
4人。

.

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

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

確率数理工学11 (2023)

6 / 10-既約性と 再帰性

生。再帰性は伝播（1）状態のが再帰的かつ えいうなうえも再帰的する！に） 有限で閉じた集合 A では再帰状態が少くともには雄二に熱（1）まず（閉でも無限なら反例あり）

Hi.i）=1を示す （特におう）

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

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

たからうへ至り、うからんへ 2 度と戻らない事象を考えると.
o =1-Hii）？ P'「仙は第"た。荘資らな門（えに戻らない）

以上より.
すると、

f（えん）=1である。

i t うである。

ある m.no が存在して、PCm）に.う）>o, PC"（しん）70
で&paint た）は、う）と & が'（すう）P はどう）がなう）の器がい=

よって、うは再帰的.

確率数理工学11 (2023)

た"鶽が礐じえは再帰的）/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いうより沖再帰的 /含まれる。それをえとする.

正（一致団結の性質）
同一の同値類に属する状態は全て再帰的か、全て非再帰的かのいずれかである.に Lemじ）より、ほぼ自明）※ 再帰性は既約成分全体の性質
確率数理工学11 (2023)

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

( R i n Rj=中 には） p,、シ。

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

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

〇 ，〇x、消滅部分う）=12|i →う）
をとってき 2.CCとおくにから到達可能な領T域）のG T より、任意の i t う なように対してる →んである。
つまり.

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

よって、 「たでもある。

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

さらに、C （う）は閉であることがわかる。 なぜなら、 j ECG)として、ある K E I に対して、 まーったであるとすると、えっるであることからえーった となるので、 k E C G ) である。 つまり、C （う）は閉.

以上より、CG) は既約かつ閉.
このようにして、各 i G E T

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

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

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

Thinより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 となる.）

確率数理工学11 (2023)

10 / 10