08wk-1: 마코프체인 (4)

최규빈

2023-04-20

강의영상

youtube: https://youtube.com/playlist?list=PLQqh36zP38-yapWz131weSlgUlgS-0T98

• 영상2는 추후 재촬영예정임

imports

import numpy as np

Markovchain, Transition Matrix

- 정의: 카운터블한 상태공간 $E$을 가지는 이산시간 확률과정 $\{X_t{\}}_{t\ge 0}$을 고려하자. 아래가 성립한다면 확률과정 $\{X_t\}$을 마코프체인(Markov chain, MC)라고 한다.

• $\mathrm{\forall }t\ge 0,\mathrm{\forall }{i}_0,i_1,\dots ,i_{n-1},i,j\in E$:

$$\mathbb{P}(X_{t+1}=j|X_t=i,X_{t-1}=i_{t-1},\dots ,X_0=i_0)=\mathbb{P}(X_{t+1}=j|X_t=i)$$

만약에 $P(X_{t+1}=j|X_t=i)$가 모든 $t$에 대하여 일정하다면 $\{X_t\}$를 균질마코프체인¹(homogeneous Markov chain, HMC) 라고 한다.

¹ 진짜 억지로 변형한것, 마땅한 한글용어가 없음

- 정의: 아래의 수식을 마코프성질 (Markov property) 이라고 한다.

• $\mathrm{\forall }t\ge 0,\mathrm{\forall }{i}_0,i_1,\dots ,i_{n-1},i,j\in E$:

$$\mathbb{P}(X_{t+1}=j|X_t=i,X_{t-1}=i_{t-1},\dots ,X_0=i_0)=\mathbb{P}(X_{t+1}=j|X_t=i)$$

- 정의: 카운터블한 상태공간 $E$를 가지는 HMC $\{X_t{\}}_{t\ge 0}$를 고려하자. 상태 $i$에서 상태 $j$로 바뀌는 조건부 확률

$$p_{ij}=\mathbb{P}(X_{t+1}=j|X_t=0)$$

를 $\{X_t{\}}_{t\ge 0}$의 전이확률(transition probability)라고 한다.

- 전이확률의 특징: 이때 전이확률은 아래의 특징을 가진다.

• $p_{ij}\ge 0$
  
• $\sum _{j\in E}{p}_{ij}=1$

첫번째 식은 확률이 양수이어야 한다는 내용이고² 두번째 식은 임의의 시점에서 상태 $i$에 존재할 경우, 그 다음시점에서 상태집합 $V$ 중 어딘가로는 이동해야한다는 의미이다.

² 쓸모없는 내용

- 정의: 카운터블한 상태공간 $V$를 가지는 HMC $\{X_t{\}}_{t\ge 0}$를 고려하자. $p_{ij}$를 $\{X_t{\}}_{t\ge 0}$의 전이확률이라고 하자. $(i,j)$-th 원소를 $p_{ij}$로 가지는 행렬 $\mathbf{P}$를 전이확률행렬 (transition probability matrix) 혹은 줄여서 전이행렬 (transition matrix) 이라고 한다.

- 참고($\star$): 상태공간 $V$의 원소수가 무한일 수도 있으므로, 원래 $\mathbf{P}$를 행렬이라고 하기에는 무리가 있다. 하지만 행렬의 덧셈, 행렬의 곱셈과 같은 연산들은 일반적으로 잘 정의되므로 $\mathbf{P}$를 행렬로 생각할 수 있다. 이러한 $\mathbf{P}$는 row와 col이 무한대로 있다고 생각하면 된다.

• $|E|=\mathrm{\infty }$ 인 경우 $\mathbf{P}$의 예시: $\mathbf{P}=\left[\begin{array}{ccc}{p}_{00}& p_{01}& \cdots \\ p_{10}& p_{11}& \cdots \\ \cdots & \cdots & \cdots \end{array}\right]$

- 전이행렬의 특징: 모든 row의 합이 1이다.

• $\sum _{j\in E}{p}_{ij}=1$ 이어야 하므로

Distribution, Distribution Function

- 예제1: 동전예제

선언1: $(\mathrm{\Omega },2^{\mathrm{\Omega }},\mathbb{P})$ 를 확률공간이라고 하자. 여기에서 확률 $\mathbb{P}$은 아래와 같이 정의되는 set function 이다.

• $\mathbb{P}(\mathrm{\varnothing })=0$
• $\mathbb{P}(\{H\})=1/2$
• $\mathbb{P}(\{T\})=1/2$
• $\mathbb{P}(\mathrm{\Omega })=1$

선언2: 확률변수 $X:(\mathrm{\Omega },2^{\mathrm{\Omega }})\to (V,2^V)$를 아래와 같이 선언하자. (단, $V=\{0,1\}$)

• $X(H)=0$
• $X(T)=1$

생각: 이제 $B\in 2^V$ 에 대하여 아래와 같은 표현들을 고려하자.

• 표현1: $\mathbb{P}(X\in B)$ // 고등학교 부터 쓰던 그 표현
• 표현2: $\mathbb{P}(\{\omega :X(\omega )\in B\})$ // 이번에 배운 표현, 표현1의 정확한 버전
• 표현3: $\mathbb{P}(X^{-1}(B))$ // 표현2의 다른 버전, inverse image의 느낌이 확 살아 있음
• 표현4: $(\mathbb{P}\circ X^{-1})(B)$ // 생각해보니까 이것도 가능함. $\mathbb{P}$, $X$ 모두 함수였잖아?

새로운 함수 $\mu :=\mathbb{P}\circ X^{-1}$는 이 경우 어떻게 정의할 수 있을까?

• $\mu (\mathrm{\varnothing })=0$
• $\mu (\{0\})=\frac{1}{2}$
• $\mu (\{1\})=\frac{1}{2}$
• $\mu (\{0,1\})=1$

표현1과 4만 모아서 살펴보면 아래와 같다.

• $\mu (\mathrm{\varnothing })=0$ $\iff$ $\mathbb{P}(X\notin \{0,1\})=0$
• $\mu (\{0\})=\frac{1}{2}$ $\iff$ $\mathbb{P}(X=0)$
  
• $\mu (\{1\})=\frac{1}{2}$ $\iff$ $\mathbb{P}(X=1\})$
• $\mu (\{0,1\})=\frac{1}{2}$ $\iff$ $\mathbb{P}(X\in \{0,1\})$ $\iff$ $\mathbb{P}(X\le 1)$

- 예제2: 동전예제(2)

$(V,2^V)$ 대신에 $(\mathbb{R},\mathcal{R})$ 으로 바꾸어도 위의 동전예제는 잘 정의된다.

선언1: $(\mathrm{\Omega },2^{\mathrm{\Omega }},\mathbb{P})$ 를 확률공간이라고 하자. 여기에서 확률 $\mathbb{P}$은 아래와 같이 정의되는 set function 이다.

• $\mathbb{P}(\mathrm{\varnothing })=0$
• $\mathbb{P}(\{H\})=1/2$
• $\mathbb{P}(\{T\})=1/2$
• $\mathbb{P}(\mathrm{\Omega })=1$

선언2: 확률변수 $X:(\mathrm{\Omega },2^{\mathrm{\Omega }})\to (\mathbb{R},\mathcal{R})$를 아래와 같이 선언하자.

• $X(H)=0$
• $X(T)=1$

생각: 이제 $B\in \mathcal{R}$ 에 대한 표현들. 편의상 $B=\{b:b\le 0.5\}$ 라고 가정하자.

• 표현1: $\mathbb{P}(X\in B)=\mathbb{P}(X\le 0.5)=\mathbb{P}(X=0)=\frac{1}{2}$
• 표현2: 생략
• 표현3: 생략
• 표현4: $(\mathbb{P}\circ X^{-1})((-\mathrm{\infty },0.5])$

표현1과 4만 모아서 살펴보면 아래와 같다.

• $\mu ((-\mathrm{\infty },x])$ $\iff$ $\mathbb{P}(X\le x)$
• $\mu (A)$ $\iff$ $\mathbb{P}(X\in A)$

- 생각의 시간

$(\mathrm{\Omega },\mathcal{F},\mathbb{P})$가 확률공간이고 $X\to \mathbb{R}$이 확률변수라면, $\mu$는 언제나 잘 정의된다.

• 모든 $B\in \mathcal{R}$에 대하여 $X^{-1}(B)$가 시그마필드의 원소가 아닐 수 없다. (만약 그렇다면 $X$는 확률변수가 아닌걸?)
• 모든 $B\in \mathcal{R}$에 대하여 $\mathbb{P}(X^{-1}(B))$의 값을 모순되게 정의할 수 없다. (만약 그렇다면 $(\mathrm{\Omega },\mathcal{F},\mathbb{P})$는 확률공간이 아닌걸?)

결론: $\mu$는 안전해!

- $\mu$도 메져의 조건을 만족한다.

• 정의역이 시그마필드임
• $\mathrm{\forall }B\in \mathcal{R}:\mu (B)\ge 0$.
• $\mathrm{\forall }{B}_1,B_2,\cdots \in \mathcal{R}$ such that $B_1,B_2\dots$ are disjoint: $\sum _{i=1}^n\mu (B_i)=\mu ({\uplus }_{i=1}^{\mathrm{\infty }}{B}_i)$

- $\mu$를 부르는 용어 ($\star \star \star$): $X$를 확률공간 $(\mathrm{\Omega },\mathcal{F},\mathbb{P})$에서 정의된 확률변수라고 하자. 이때 $X^{-1}\circ \mathbb{P}$로 정의가능한 함수 $\mu :\mathcal{R}\to [0,1]$ 를 $X$의 distribution 이라고 부른다.

- $F(x)$의 정의: $X$를 확률공간 $(\mathrm{\Omega },\mathcal{F},\mathbb{P})$에서 정의된 확률변수라고 하자. $F:\mathbb{R}\to [0,1]$ 인 함수를 아래와 같이 정의하자.

$$F(x)=\mu ((-\mathrm{\infty },x])$$

이러한 함수 $F$는 아래와 같이 표현할 수 있다.

$$F(x)=\mathbb{P}(X\le x)$$

함수 $F$를 확률변수 $X$의 distribution function 이라고 한다.

- 참고사항 (그냥 교양임, 시험에 안냄):

• $\mu$가 언제나 잘 정의되므로 $F(x)$도 언제나 잘 정의된다.
• $F(x)$는 어떠한 성질들을 가진다. (비감소함수, 오른쪽연속 등..)
• $F(x)$는 $F(x)=F_c(x)+F_s(x)+F_d(x)$ 와 같이 분해가능하다.
• $F(x)=F_c(x)$라면 $F(x)$는 연속형확률변수의 cdf가 된다. $F(x)=F_d(x)$라면, $F(x)$는 이산형확률변수의 cdf가 된다.
• $F(x)=F_c(x)+F_d(X)$라면 혼합형확률변수의 cdf가 된다.
• $F(x)=F_s(x)$인 경우는 pdf, pmf가 존재하지 않는다.

- Borel sets (어떤 학생이 헷갈려해서.. 제가 헷갈리게 설명해서..)

• $\mathrm{\Omega }=\mathbb{R}$ 일때 $2^{\mathbb{R}}$ 역시 시그마필드임.
• 따라서 적당한 메져가 존재하여 $2^{\mathbb{R}}$의 모든 집합을 잴 수 있음. (모든 원소를 0으로 측정하는 메져라든가..)
• 하지만 르벡메져는 $2^{\mathbb{R}}$의 모든 원소를 잴 수 없음. 따라서 $2^{\mathbb{R}}$의 모든 원소에서 확률을 정의하는 것이 불가능함.
• 그러나 $\mathrm{\Omega }=\mathbb{R}$일때 $\mathcal{R}$이라는 시그마필드는 모든 원소에서 확률을 정의할 수 있음.
• $\mathcal{R}$을 Borel sets 이라고 부름.

- $\mathbb{R}$을 포함하는 Borel sets 은 $\mathcal{B}(\mathbb{R})$로 표현하기도 함. 즉 $\mathcal{R}=\mathcal{B}(\mathbb{R})$ 이다.

The Stationary Distribution of an HMC

- 정의: stationary distribution (정확한 버전)

$(E,\mathcal{B}(E))$를 잴 수 있는 공간이라고 하고 $\mu$를 $(E,\mathcal{B}(E))$에서의 distribution 이라고 하자. 만약에 아래식을 만족하면 $\mu$ 를 stationary distribution 이라고 한다.

$$\mu p=\mu$$

여기에서 $\mu p(\{x\}):=\sum _{y\in E}\mu (\{y\})p_{yx}$ 를 의미한다.

- 정의: stationary distribution (쉬운버전)

아래식을 만족하는 distribution $\mathit{\mu }$ 를 stationary distribution 이라고 한다.

$${\mathit{\mu }}^{\mathrm{\top }}\mathbf{P}={\mathit{\mu }}^{\mathrm{\top }}$$

- 예시1: 아래와 같은 transition matrix를 고려하자.

P = np.array([[0.2,0.8],
              [0.3,0.7]])
P

array([[0.2, 0.8],
       [0.3, 0.7]])

수렴할까?

np.linalg.matrix_power(P,50)

array([[0.27272727, 0.72727273],
       [0.27272727, 0.72727273]])

결과분석

1. 특징1: ${\mathbf{P}}^{\star }$로 수렴한다.
2. 특징2: 수렴한 매트릭스를 세로로 읽으면 값이 같다. $\Rightarrow$ … $\Rightarrow$ ${\mathbf{P}}^{\star }$의 아무 row나 가져오면 정상분포가 된다.
3. 특징3: ${\mathit{\pi }}^{\mathrm{\top }}\mathbf{P}={\mathit{\pi }}^{\mathrm{\top }}$ $\Leftarrow$ $({\mathit{\mu }}^{\mathrm{\top }}{\mathbf{P}}^{\star })\mathbf{P}={\mathit{\pi }}^{\mathrm{\top }}$
4. 특징4: 초기분포에 ${\mathit{\pi }}^{\mathrm{\top }}$을 대입하면 $\{X_t\}$는 동일한 분포를 가진다.

- 예시2: 아래와 같은 transition matrix를 고려하자.

P = np.array([[0.4,0.6],
              [0.9,0.1]])
P

array([[0.4, 0.6],
       [0.9, 0.1]])

수렴할까?

np.linalg.matrix_power(P,50)

array([[0.6, 0.4],
       [0.6, 0.4]])

결과분석

1. 특징1: ${\mathbf{P}}^{\star }$로 수렴한다.
2. 특징2: 수렴한 매트릭스를 세로로 읽으면 값이 같다. $\Rightarrow$ … $\Rightarrow$ ${\mathbf{P}}^{\star }$의 아무 row나 가져오면 정상분포가 된다.
3. 특징3: ${\mathit{\pi }}^{\mathrm{\top }}\mathbf{P}={\mathit{\pi }}^{\mathrm{\top }}$ $\Leftarrow$ $({\mathit{\mu }}^{\mathrm{\top }}{\mathbf{P}}^{\star })\mathbf{P}={\mathit{\pi }}^{\mathrm{\top }}$
4. 특징4: 초기분포에 ${\mathit{\pi }}^{\mathrm{\top }}$을 대입하면 $\{X_t\}$는 동일한 분포를 가진다.

- 예시3: 어지간하면 다 수렴할 것 같으니까 아래와 같이 특이한 transition matrix를 고려하자.

P = np.array([[1.0, 0.0],
              [0.05,0.95]])
P

array([[1.  , 0.  ],
       [0.05, 0.95]])

np.linalg.matrix_power(P,50)

array([[1.        , 0.        ],
       [0.92305502, 0.07694498]])

수렴안하나?

np.linalg.matrix_power(P,100)

array([[1.        , 0.        ],
       [0.99407947, 0.00592053]])

np.linalg.matrix_power(P,500)

array([[1.00000000e+00, 0.00000000e+00],
       [1.00000000e+00, 7.27449156e-12]])

결국에는 한다.

결과분석

1. 특징1: ${\mathbf{P}}^{\star }$로 수렴한다.
2. 특징2: 수렴한 매트릭스를 세로로 읽으면 값이 같다. $\Rightarrow$ … $\Rightarrow$ ${\mathbf{P}}^{\star }$의 아무 row나 가져오면 정상분포가 된다.
3. 특징3: ${\mathit{\pi }}^{\mathrm{\top }}\mathbf{P}={\mathit{\pi }}^{\mathrm{\top }}$ $\Leftarrow$ $({\mathit{\mu }}^{\mathrm{\top }}{\mathbf{P}}^{\star })\mathbf{P}={\mathit{\pi }}^{\mathrm{\top }}$
4. 특징4: 초기분포에 ${\mathit{\pi }}^{\mathrm{\top }}$을 대입하면 $\{X_t\}$는 동일한 분포를 가진다.

- 공식 (쓸모없는): transition matrix 가 아래와 같은 (2,2)-matrix이라고 하자.

• $\mathbf{P}=\left[\begin{array}{cc}1-a& a\\ b& 1-b\end{array}\right]$

그러면 대응하는 정상확률분포는 아래와 같다.

• ${\pi }_0=\frac{b}{a+b}$
• ${\pi }_1=\frac{a}{a+b}$

예시1의 경우를 이 공식에 넣으면

0.3/(0.8+0.3),0.8/(0.8+0.3)

(0.2727272727272727, 0.7272727272727273)

예시2의 경우를 이 공식에 넣으면

0.9/(0.6+0.9), 0.6/(0.6+0.9)

(0.6, 0.39999999999999997)

예시3의 경우를 이 공식에 넣으면

0.05/(0+0.05) , 0/(0+0.05)

(1.0, 0.0)

- 예시4: $a+b=0$ 이라면?

P = np.array([[1.0, 0.0],
              [0.0, 1.0]])
P

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

수렴은 할텐데..

결과분석

1. 특징1: ${\mathbf{P}}^{\star }$로 수렴한다.
2. 특징2: 수렴한 매트릭스를 세로로 읽으면 값이 다르다?
3. 특징3: 어?
4. 특징4: 어????? (이건 그냥 되는데?)

특징3: 정상분포

일단 모든 $\mathit{\mu }$에 대하여 아래가 성립하긴한다.

$${\mathit{\mu }}^{\mathrm{\top }}\mathbf{P}={\mathit{\mu }}^{\mathrm{\top }}$$

따라서 이 경우 모든 확률측도 $\mathit{\mu }$는 정상분포가 된다. 유일한 정상분포를 가지지 않는다!!

특징4: 정상확률과정

$\mathbf{P}=\mathbf{I}$ 이므로 당연히 $\{X_t\}$는 모든 $t\ge 0$에 대하여 동일한 분포를 가진다.

- 예시5 ($\star \star \star$)

P = np.array([[0.0, 1.0],
              [1.0, 0.0]])
P

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

P@P

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

P@P@P

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

결과분석

1. 특징1: 수렴을 안하는데?
2. 특징2:
3. 특징3:
4. 특징4:

특징3: 정상분포

만약에 $\mathit{\pi }=\left[\begin{array}{c}1/2\\ 1/2\end{array}\right]$ 로 설정한다면 아래가 성립한다.

$${\mathit{\pi }}^{\mathrm{\top }}\mathbf{P}={\mathit{\pi }}^{\mathrm{\top }}$$

따라서 $\mathit{\pi }$는 정상분포가 된다.

특징4: 정상확률과정

만약에 $\mathit{\pi }=\left[\begin{array}{c}1/2\\ 1/2\end{array}\right]$ 로 설정한다면 $\{X_t\}$는 모든 $t\ge 0$에 대하여 동일한 분포를 가진다.

- 생각의 시간

	특징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

특징3에서 정상분포가 존재하면 특징4는 그냥 성립한다. 지금까지 살펴본 예제에서는 모두 정상분포가 존재했다. 혹시 정상분포가 존재하지 않을 수도 있을까?

- Thm: finite state를 가지는 HMC는 정상분포가 최소한 1개는 존재한다.