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가 더 유리하다.

헷갈리는 표현: \(\infty\)의 포함

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

• \(\mathbb{R} \cup \{-\infty\} \cup \{\infty\} = \bar{\mathbb{R}}\)
• \(\mathbb{N} \cup \{-\infty\}\)

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

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

• \(\forall n \in \mathbb{N}:~ 0<\frac{1}{n} \leq 1\)

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

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

• \((-\infty, b] = \{x: x\leq b, ~x,b \in \mathbb{R}\}\)
• \((-\infty, b) = \{x: x < b,~ x,b \in \mathbb{R}\}\)

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

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

\[\lim_{t\to \infty}{\bf P}^{t} = {\bf P}^\star\]

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

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

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

\[{\bf p}_\star^\top {\bf P} = {\bf p}_\star^\top\]

즉 \({\bf p}_\star^\top\)는 정상분포의 정의를 만족한다.

• 의미1: 따라서 \({\bf p}_\star^\top\)가 존재한다면, \({\bf p}_\star^\top={\boldsymbol \pi}^\top\)라고 놓을 수 있다.
• 의미2: \({\bf P}\)가 동일한 row를 가지는 어떠한 매트릭스로 수렴한다면, 아무 row나 가져와서 \({\boldsymbol \pi}^\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 라고 하자.² 그렇다면 극한분포 \({\bf p}_{\star}^\top\)이 항상 존재한다.

FINITE HMC에 대한 정리

이론의 정리

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

CaseNO	대표예제	FINITE	IRR(연결)	AP(비주기)	\({\bf 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, 정상분포, 극한분포

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

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

	Empirical 분포	정상분포	극한분포
용어가 통용되는 범위	모든 확률과정	모든 확률과정	마코프체인
기호	\(\bar{\boldsymbol \pi} = \frac{1}{T}\begin{bmatrix}{\tt sum}(X_t==0) \\ {\tt sum}(X_t==1)\end{bmatrix}\)	\({\boldsymbol \pi}=\begin{bmatrix}\mathbb{E}(I(X=0))\\ \mathbb{E}(I(X=1)) \end{bmatrix}\)	\({\bf p}_{\star}= \lim_{t\to \infty}\begin{bmatrix}p_{?0}^{(t)} \\ p_{?1}^{(t)} \end{bmatrix}\)
\(\omega\)의 고려	하나의 \(\omega\)만 고려해 계산	모든 \(\omega\) 고려해 계산	\(\omega\)를 고려하지 않고 계산
통계느낌(분포느낌?)	O	O	X
이론적인값?	X	O	O
데이터와 관련	O	X	X
극한과 관련	O	X	O
LLN과 관련	O	O	X
느낌	데이터로 계산한 평균값	이론적인 기대값	이론적인 수렴값

\(P^{(t)}_{?0}\) t번만에 0에 갈 확률

마코프 체인이 finite한 공간에 있고 연결)irreducible)하다는 것을 가정하면 에르고딕 이론을 이용해서 정상분포가 존재한다.

이론들의 의미를 다시 고찰

- 에르고딕정리: 임피리컬분포와 정상분포에 관련한 정리 (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\)를 신경안씀
• \({\boldsymbol \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 \({\bf P}\) (혹은 그 비슷한 것) 가 아래와 같다고 하자.

\[{\bf P} = \begin{bmatrix} 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{bmatrix}\]

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

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

정상분포 \({\boldsymbol \pi}^\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: \({\bf P}\)의 거듭제곱이 동일한 row vector를 가지는 매트릭스로 수렴하지만, \({\bf p}_\star^\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]])

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

Footnotes

1. 세로로 읽을때 값이 같다면

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