11wk-1: 마코프체인 (8)

최규빈

2023-05-11

강의영상

youtube: https://youtube.com/playlist?list=PLQqh36zP38-wPUBATQ2c1npACK21EgDsx

예비학습

약한조건, 약한정리, 강한조건, 강한정리

- 정리: 어떠한 조건을 만족하면, 어떠한 결론이 나온다.

• 결론: 우리가 원하는 것.
• 조건: 우리가 원하는 것을 얻기 위한 고난과정.

- 결론이 동일하다면 조건이 약할 수록 유리하다.

• 정리1: 수업에 온라인으로 참석하거나 오프라인으로 참석한다면 모두 출석으로 인정한다.
• 정리2: 수업에 오프라인으로 참석할때만 출석으로 인정한다.

정리2의 조건이 만족되면 정리1의 조건은 자동으로 만족된다. 따라서 정리2의 조건이 더 강한 조건이다. 조건이 강할수록 불리하므로 정리2가 더 불리하다.

- 조건이 동일하다면 결론이 강한 쪽이 유리하다.

• 정리1: 중간고사와 기말고사를 모두 응시한다면, B학점 이상이다.
• 정리2: 중간고사와 기말고사를 모두 응시한다면, A학점 이상이다.

정리2의 결론이 만족되면 정리1의 결론은 자동으로 만족되므로 정리2의 결론이 더 강하다. 결론은 강할수록 유리하므로 정리2가 더 유리하다.

헷갈리는 표현: $\mathrm{\infty }$의 포함

- 자연수집합 $\mathbb{N}$은 $\{\mathrm{\infty }\}$를 포함하지 않는다. 마찬가지로 실수집합 $\mathbb{R}$ 역시 $\{-\mathrm{\infty }\},\{\mathrm{\infty }\}$를 포함하지 않는다. 만약에 이를 포함하고 싶을 경우는 아래와 같이 표현한다.

• $\mathbb{R}\cup \{-\mathrm{\infty }\}\cup \{\mathrm{\infty }\}=\overline{\mathbb{R}}$
• $\mathbb{N}\cup \{-\mathrm{\infty }\}$

여기에서 $\overline{\mathbb{R}}$은 확장된 실수라고 부르는데 교재에따라 사용하기도 하고 사용하지 않기도 한다.

- 만약에 $\mathbb{N}$이 $\{\mathrm{\infty }\}$를 포함한다면

• $\mathrm{\forall }n\in \mathbb{N}:0<\frac{1}{n}\le 1$

와 같은 표현은 불가능할 것이다.

- 구간에 대한 표현들: 구간에 대한 몇가지 표현을 정리하면 아래와 같다.

• $(-\mathrm{\infty },b]=\{x:x\le b,x,b\in \mathbb{R}\}$
• $(-\mathrm{\infty },b)=\{x:x<b,x,b\in \mathbb{R}\}$

Transition matrix의 수렴 – 극한분포 관련내용

- 정의: Finite HMC $\{X_t\}$를 고려하자. $\mathbf{P}$를 $\{X_t\}$의 전이행렬이라고 하자. 만약

$$\underset{t\to \mathrm{\infty }}{lim}{\mathbf{P}}^t={\mathbf{P}}^{\star }$$

가 존재하고 ${\mathbf{P}}^{\star }$의 모든 row가 동일한 벡터를 가진다면¹ ${\mathbf{P}}^{\star }$의 임의의 row-vector ${\mathbf{p}}_{\star }^{\mathrm{\top }}$ 를 $\{X_t\}$의 극한분포 (limiting distribution) 라고 한다.

¹ 세로로 읽을때 값이 같다면

- 이론: 극한분포가 존재한다면, 유일하다. (그래서 극한분포는 기껏해야 (at most) 1개 존재한다.)

- Thm: Finite HMC $\{X_t\}$를 고려하자. 운이 좋아서 $\{X_t\}$의 극한분포 ${\mathbf{p}}_{\star }^{\mathrm{\top }}$가 존재한다고 하자. 그렇다면 극한분포 ${\mathbf{p}}_{\star }^{\mathrm{\top }}$는 아래식을 만족한다.

$${\mathbf{p}}_{\star }^{\mathrm{\top }}\mathbf{P}={\mathbf{p}}_{\star }^{\mathrm{\top }}$$

즉 ${\mathbf{p}}_{\star }^{\mathrm{\top }}$는 정상분포의 정의를 만족한다.

• 의미1: 따라서 ${\mathbf{p}}_{\star }^{\mathrm{\top }}$가 존재한다면, ${\mathbf{p}}_{\star }^{\mathrm{\top }}={\mathit{\pi }}^{\mathrm{\top }}$라고 놓을 수 있다.
• 의미2: $\mathbf{P}$가 동일한 row를 가지는 어떠한 매트릭스로 수렴한다면, 아무 row나 가져와서 ${\mathit{\pi }}^{\mathrm{\top }}$라고 주장해도 무방하다.
• 주의: 이 이론에서 finite의 조건이 빠진다면 분포의 정의를 만족하지 않을 수 있다. (좀 이따가 설명)

- 예제1: 극한분포가 존재하지 않는 경우1 (AP조건을 만족하지 않는 경우)

예시1

P= np.array([[0,1],
             [1,0]])
P

array([[0, 1],
       [1, 0]])

예시2

P= np.array([[0,1,0],
             [0,0,1],
             [1,0,0]])
P

array([[0, 1, 0],
       [0, 0, 1],
       [1, 0, 0]])

- 예제2: 극한분포가 존재하지 않는 경우2 (IRR조건을 만족하지 않는 경우)

예시1

P = np.array([[1,0],
              [0,1]])
P

array([[1, 0],
       [0, 1]])

예시2

P = np.array([[1,1,0,0],
              [1,1,0,0],
              [0,0,1,1],
              [0,0,1,1]])/4
P

array([[0.25, 0.25, 0.  , 0.  ],
       [0.25, 0.25, 0.  , 0.  ],
       [0.  , 0.  , 0.25, 0.25],
       [0.  , 0.  , 0.25, 0.25]])

- Thm: 확률변수열 $\{X_t\}$가 finite, irreducible, aperiodic HMC 라고 하자.² 그렇다면 극한분포 ${\mathbf{p}}_{\star }^{\mathrm{\top }}$이 항상 존재한다.

² 에르고딕 마코프체인이라는 의미

FINITE HMC에 대한 정리

이론의 정리

- $\{X_t\}$는 HMC 라고 하자.

CaseNO	대표예제	FINITE	IRR(연결)	AP(비주기)	$\mathbf{P}$의 수렴	극한분포유일존재	정상분포존재	정상분포유일	에르고딕정리를 만족	에르고딕
1		O	X	X	X	X	O	X	X	X
2	단위행렬	O	X	O	O	X	O	X	X	X
3	순환이동	O	O	X	X	X	O	O	O	X
4	나이스	O	O	O	O	O	O	O	O	O

- CaseNO==1 의 예제

Emprical 분포, 정상분포, 극한분포

- Emprical distribution, 정상분포, 극한분포

• ${\overline{\mathit{\pi }}}^{\mathrm{\top }}$: 하나의 $\omega$에 대한 확률변수열 $\{X_t\}$의 emprical distribution (time average로 분포를 추정)
• ${\mathit{\pi }}^{\mathrm{\top }}$: 모든 $\omega$를 고려하였을 경우 확률변수열 $\{X_t\}$의 정상분포.
• ${\mathbf{p}}_{\star }^{\mathrm{\top }}$: $\omega$와 무관하게 $\mathbf{P}$의 극한으로 얻어지는 $\{X_t\}$의 극한분포. // 마코프체인에 특화

- 표로 정리하면 아래와 같다.

	Empirical 분포	정상분포	극한분포
용어가 통용되는 범위	모든 확률과정	모든 확률과정	마코프체인
기호	$\overline{\mathit{\pi }}=\frac{1}{T}\left[\begin{array}{c}\mathtt{s}\mathtt{u}\mathtt{m}(X_t==0)\\ \mathtt{s}\mathtt{u}\mathtt{m}(X_t==1)\end{array}\right]$	$\mathit{\pi }=\left[\begin{array}{c}\mathbb{E}(I(X=0))\\ \mathbb{E}(I(X=1))\end{array}\right]$	${\mathbf{p}}_{\star }=\underset{t\to \mathrm{\infty }}{lim}\left[\begin{array}{c}{p}_{?0}^{(t)}\\ p_{?1}^{(t)}\end{array}\right]$
$\omega$의 고려	하나의 $\omega$만 고려해 계산	모든 $\omega$ 고려해 계산	$\omega$를 고려하지 않고 계산
통계느낌(분포느낌?)	O	O	X
이론적인값?	X	O	O
데이터와 관련	O	X	X
극한과 관련	O	X	O
LLN과 관련	O	O	X
느낌	데이터로 계산한 평균값	이론적인 기대값	이론적인 수렴값

이론들의 의미를 다시 고찰

- 에르고딕정리: 임피리컬분포와 정상분포에 관련한 정리 (LLN보다 더 약한 조건을 가짐)

• 의미1: 에르고딕 정리를 만족하지 못하는 경우 하나의 확률변수열을 이용한 추론이 불가능

## 예시
P =np.array([[1,1,0,0],
             [1,1,0,0],
             [0,0,1,1],
             [0,0,1,1]])/2
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: 에르고딕 정리를 만족하는 경우 $X_1,X_2,\dots$이 동일한 분포를 가지지 않지만 무시하고 $\pi$를 추정할 수있다.

- 극한분포와 관련된 이론: 극한분포의 느낌은 초기값에 대한 삭제임

• 극한분포는 어차피 $\omega$를 신경안씀
• ${\mathit{\mu }}_0$는 아무상관이 없음
• 결국 극한분포가 존재한다면 시간의존성이 삭제된다는 의미임

스토리정리

- FINITE HMC는 일단 정상분포라는게 존재함. 그런데 유일하지 않을 수 있음.

- FINITE HMC는 크게보면 IRR인 케이스와 IRR 아닌 케이스로 나누어짐

• 그런데 IRR이 아닌 케이스는 IRR인 케이스들의 조합으로 나누어 생각할 수 있음
• 그래서 어차피 신경쓸 필요 없음.
• 따라서 모든 마코프체인은 IRR이라고 가정해버려도 무방

- 만약에 HMC가 (1) FINITE (2) IRR 이면 유일한 정상분포가 존재.

• 심지어 이 조건에서는 에르고딕정리를 이용해서 임피리컬 분포로 정상분포를 estimate 할 수 있음.

- 그러면 HMC가 (1) FINITE (2) IRR 이면 다 끝?

• 언뜻 생각하면 그런거 같음.
• 그런데 에르고딕 정리를 만족한다고 해서 초기분포에 대한 기억이 사라지는건 아님
• 몇 가지 응용예제에서는 초기분포에 대한 의존성을 삭제시키는 것이 매우 중요함.
• 이걸 위해서는 AP조건이 추가되어야 함.

- HMC가 (1) FINITE (2) IRR (3) AP 라면 아주 좋음.

예제: 오른쪽으로만 갈래

확률변수열 $\{X_t\}$가 HMC라고 하고, 그 transition matrix $\mathbf{P}$ (혹은 그 비슷한 것) 가 아래와 같다고 하자.

$$\mathbf{P}=\left[\begin{array}{cccccc}0& 1& 0& 0& 0& \dots \\ 0& 0& 1& 0& 0& \dots \\ 0& 0& 0& 1& 0& \dots \\ 0& 0& 0& 0& 1& \dots \\ \dots & \dots & \dots & \dots & \dots & \dots \end{array}\right]$$

- 의미: $i\to i+1$와 같은 평행이동만 한다는 뜻이다.

- 특징1: 정상분포가 존재하지 않음.

정상분포 ${\mathit{\pi }}^{\mathrm{\top }}=[{\pi }_0,{\pi }_1,{\pi }_2,\dots ]$ 가 존재하기 위해서는 아래가 성립해야 한다.

• ${\pi }_0={\pi }_1$
• ${\pi }_1={\pi }_2$
• ${\pi }_1={\pi }_2$
• $\dots$

즉 모든 $n\in {\mathbb{N}}_0$에 대하여 ${\pi }_0={\pi }_n$이 성립해아한다. 그런데 그럴 수 없다.

- 특징2: $\mathbf{P}$의 거듭제곱이 동일한 row vector를 가지는 매트릭스로 수렴하지만, ${\mathbf{p}}_{\star }^{\mathrm{\top }}$가 극한분포가 되지 않음.

P = np.array([[0,1,0,0,0],
              [0,0,1,0,0],
              [0,0,0,1,0],
              [0,0,0,0,1],
              [0,0,0,0,0]])
P@P

array([[0, 0, 1, 0, 0],
       [0, 0, 0, 1, 0],
       [0, 0, 0, 0, 1],
       [0, 0, 0, 0, 0],
       [0, 0, 0, 0, 0]])

${\mathbf{p}}_{\star }^{\mathrm{\top }}$는 그냥 0으로 수렴한다. (왜냐하면 모든 $i\in S={\mathbb{N}}_0$에 대하여 ${\mathbf{p}}_{\star }^{\mathrm{\top }}$의 $i$-th element는 0 이므로) 따라서 $\mathtt{s}\mathtt{u}\mathtt{m}({\mathbf{p}}_{\star }^{\mathrm{\top }})=0$ 이다. 그래서 ${\mathbf{p}}_{\star }^{\mathrm{\top }}$은 pmf의 정의를 만족하지 않음.