08wk-2: 마코프체인 (5)
2023-04-25
강의영상
youtube: https://youtube.com/playlist?list=PLQqh36zP38-zHbA2xrF58wfGjzkhNzxnL
import
review
-
지난시간 복습
특징1(수렴) | 특징2(동일row) | 특징3(정상분포) | 특징4(정상과정) | |
---|---|---|---|---|
예시1(나이스) | O | O | 존재O, 유일O | O |
예시2(나이스) | O | O | 존재O, 유일O | O |
예시3(흡수) | O | O | 존재O, 유일O | O |
예시4(단위행렬) | O | X | 존재O, 유일X | O |
예시5(주기) | X | NA | 존재O, 유일O | O |
-
목표: 예시4와 예시5를 좀 더 공부해보자.
irreducible
Motivating Examples
예제1
-
아래의 전이확률을 고려하자.
P =np.array([0.5, 0.5, 0.0, 0.0,
0.5, 0.5, 0.0, 0.0,
0.0, 0.0, 0.5, 0.5,
0.0, 0.0, 0.5, 0.5]).reshape(4,4)
P
array([[0.5, 0.5, 0. , 0. ],
[0.5, 0.5, 0. , 0. ],
[0. , 0. , 0.5, 0.5],
[0. , 0. , 0.5, 0.5]])
-
특징1: \({\bf P}\)는 수렴함
array([[0.5, 0.5, 0. , 0. ],
[0.5, 0.5, 0. , 0. ],
[0. , 0. , 0.5, 0.5],
[0. , 0. , 0.5, 0.5]])
-
특징2: 모든 row가 같은건 아님
-
특징3: 정상분포는 유일하게 존재하지 않음
array([[0.16666667],
[0.16666667],
[0.33333333],
[0.33333333]])
(array([[0.16666667, 0.16666667, 0.33333333, 0.33333333]]),
array([[0.16666667, 0.16666667, 0.33333333, 0.33333333]]))
-
특징4: 초기분포가 정상분포라면 정상확률과정
-
특징5: 상태공간 \(E\) 에 equivalence class 가 2개 있는 느낌
예제2
-
아래의 전이확률을 고려하자.
P =np.array([1/4, 1/4, 0.0, 1/2,
1/4, 1/4, 0.0, 1/2,
0.0, 0.0, 1.0, 0.0,
1/2, 1/4, 0.0, 1/4]).reshape(4,4)
P
array([[0.25, 0.25, 0. , 0.5 ],
[0.25, 0.25, 0. , 0.5 ],
[0. , 0. , 1. , 0. ],
[0.5 , 0.25, 0. , 0.25]])
-
특징1: \({\bf P}\)는 수렴함
matrix([[0.35, 0.25, 0. , 0.4 ],
[0.35, 0.25, 0. , 0.4 ],
[0. , 0. , 1. , 0. ],
[0.35, 0.25, 0. , 0.4 ]])
-
특징2: 모든 row가 같지는 않음
-
특징3: 유일한 정상분포를 가지는건 아님
array([[0.07],
[0.05],
[0.8 ],
[0.08]])
-
특징4: 초기분포가 정상분포라면 정상확률과정
-
특징5: 상태공간 \(E\)에 equivalence class 가 2개 있는 느낌
정의 및 이론
-
용어
- irreducible (기약) // reducible (비기약)
- (strongly) connected
-
정의
-
느낌
- 연결되어있는 느낌. 즉 모든 \(x,y \in E\)에 대하여 \(x\to \cdots \to y\) 인 path 나 \(y \to \cdots \to x\) 인 path 가 존재함
- 겉도는 그룹이 없음 (상태공간 \(E\)에 단 하나의 equivalence class가 존재함)
-
Thm: HMC \(\{X_t\}\) 가 (1) finite state space 를 가지고 (2) irreducible 이라면 \(\{X_t\}\)의 유일한 정상분포 \({\boldsymbol \pi}\)가 존재하며 모든 state에 대한 확률은 양수이다.
aperiodic
Motivating Examples
예제1
-
아래와 같은 전이확률을 고려하자.
array([[0., 1., 0.],
[0., 0., 1.],
[1., 0., 0.]])
-
다이어그램
flowchart LR 0 -->|1| 1 1 -->|1| 2 2 -->|1| 0
-
특징1: \({\bf P}\)는 수렴안함
-
특징2:
-
특징3: 정상분포는 유일하게 존재함.
(array([[0.33333333, 0.33333333, 0.33333333]]),
array([[0.33333333, 0.33333333, 0.33333333]]))
-
특징4: 초기분포가 정상분포라면 정상확률과정
-
특징5: 상태공간 \(E\)에 equivalence class 가 1개
-
특징6: 주기성을 가짐 (주기는 3)
- 관찰: 어떠한 상태 \(x \in E\) 에 있더라도 반드시 3번 안에는 원래 상태로 되돌아옴.
예제2
-
아래와 같은 전이확률을 고려하자.
P = np.array([0.0, 1.0, 0.0, 0.0,
0.0, 0.0, 0.0, 1.0,
0.0, 1.0, 0.0, 0.0,
1/3, 0.0, 2/3, 0.0]).reshape(4,4)
P
array([[0. , 1. , 0. , 0. ],
[0. , 0. , 0. , 1. ],
[0. , 1. , 0. , 0. ],
[0.33333333, 0. , 0.66666667, 0. ]])
-
다이어그램
flowchart LR 0 -->|1| 1 1 -->|1| 3 2 -->|1| 1 3 -->|1/3| 0 3 -->|2/3| 2
-
특징1: \({\bf P}\)는 수렴안함
array([[0. , 1. , 0. , 0. ],
[0. , 0. , 0. , 1. ],
[0. , 1. , 0. , 0. ],
[0.33333333, 0. , 0.66666667, 0. ]])
-
특징2: Pass
-
특징3: 정상분포는 유일하게 존재함.
array([[0.11111111],
[0.33333333],
[0.22222222],
[0.33333333]])
(array([[0.11111111, 0.33333333, 0.22222222, 0.33333333]]),
array([[0.11111111, 0.33333333, 0.22222222, 0.33333333]]))
어떻게 찾음?
array([0.11111111, 0.33333333, 0.22222222, 0.33333333])
-
특징4: 초기분포가 정상분포라면 정상확률과정
-
특징5: irr
-
특징6: 주기성을 가짐 (주기는3)
flowchart LR 0 -->|1| 1 1 -->|1| 3 2 -->|1| 1 3 -->|1/3| 0 3 -->|2/3| 2
0에서 시작한다면?
- \(0 \to 1 \to 3 \to 0\)
- \(0 \to 1 \to 3 \to 2 \to 1 \to 3 \to 0\)
- \(0 \to 1 \to 3 \to 2 \to 1 \to 3 \to 2 \to \cdots\)
3번만에 되돌아오거나, 6번만에 되돌아오거나, 9번만에 되돌아오거나 … \(\Rightarrow\) 주기는 3 (3,6,9의 최대공약수는 3)
1에서 시작한다면?
- \(1 \to 3 \to 0 \to 1\)
- \(1 \to 3 \to 2 \to 1 \to 3 \to 0 \to 1\)
- \(\dots\)
2에서 시작한다면?
3에서 시작한다면?
꿀팁: HMC \(\{X_t\}\)가 irreducible 이라면 모든 \(x \in E\) 는 같은 주기를 가진다.