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\geq 0}\)을 고려하자. 아래가 성립한다면 확률과정 \(\{X_t\}\)을 마코프체인(Markov chain, MC)라고 한다.

• \(\forall t\geq 0, \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) 이라고 한다.

• \(\forall t\geq 0, \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\geq 0}\)를 고려하자. 상태 \(i\)에서 상태 \(j\)로 바뀌는 조건부 확률

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

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

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

• \(p_{ij} \geq 0\)
  
• \(\sum_{j\in E}p_{ij}=1\)

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

² 쓸모없는 내용

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

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

• \(|E|=\infty\) 인 경우 \({\bf P}\)의 예시: \({\bf P}=\begin{bmatrix} p_{00} & p_{01} & \cdots \\ p_{10} & p_{11} & \cdots \\ \cdots & \cdots & \cdots \end{bmatrix}\)

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

• \(\sum_{j \in E}p_{ij} = 1\) 이어야 하므로

Distribution, Distribution Function

- 예제1: 동전예제

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

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

선언2: 확률변수 \(X: (\Omega, 2^\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(\emptyset) = 0\)
• \(\mu(\{0\}) = \frac{1}{2}\)
• \(\mu(\{1\}) = \frac{1}{2}\)
• \(\mu(\{0,1\}) = 1\)

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

• \(\mu(\emptyset) = 0\) \(\Leftrightarrow\) \(\mathbb{P}(X \notin \{0,1\})=0\)
• \(\mu(\{0\}) = \frac{1}{2}\) \(\Leftrightarrow\) \(\mathbb{P}(X=0)\)
  
• \(\mu(\{1\}) = \frac{1}{2}\) \(\Leftrightarrow\) \(\mathbb{P}(X=1\})\)
• \(\mu(\{0,1\}) = \frac{1}{2}\) \(\Leftrightarrow\) \(\mathbb{P}(X\in \{0,1\})\) \(\Leftrightarrow\) \(\mathbb{P}(X\leq 1)\)

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

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

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

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

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

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

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

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

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

• \(\mu((-\infty,x])\) \(\Leftrightarrow\) \(\mathbb{P}(X \leq x)\)
• \(\mu(A)\) \(\Leftrightarrow\) \(\mathbb{P}(X\in A)\)

- 생각의 시간

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

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

결론: \(\mu\)는 안전해!

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

• 정의역이 시그마필드임
• \(\forall B \in {\cal R}:~ \mu(B)\geq 0\).
• \(\forall B_1,B_2,\dots \in {\cal R}\) such that \(B_1,B_2 \dots\) are disjoint: \(\sum_{i=1}^{n}\mu(B_i) = \mu(\uplus_{i=1}^{\infty}B_i)\)

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

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

\[F(x) = \mu((-\infty, x])\]

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

\[F(x) = \mathbb{P}(X \leq 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 (어떤 학생이 헷갈려해서.. 제가 헷갈리게 설명해서..)

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

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

The Stationary Distribution of an HMC

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

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

\[\mu p = \mu\]

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

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

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

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

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

• \({\bf P} = \begin{bmatrix} 1-a & a \\ b & 1-b \end{bmatrix}\)

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

• \(\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: \({\bf P}^{\star}\)로 수렴한다.
2. 특징2: 수렴한 매트릭스를 세로로 읽으면 값이 다르다?
3. 특징3: 어?
4. 특징4: 어????? (이건 그냥 되는데?)

특징3: 정상분포

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

\[{\boldsymbol \mu}^\top {\bf P} = {\boldsymbol \mu}^\top\]

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

특징4: 정상확률과정

\({\bf P}= {\bf I}\) 이므로 당연히 \(\{X_t\}\)는 모든 \(t\geq 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: 정상분포

만약에 \({\boldsymbol \pi}=\begin{bmatrix} 1/2 \\ 1/2 \end{bmatrix}\) 로 설정한다면 아래가 성립한다.

\[{\boldsymbol \pi}^\top {\bf P} = {\boldsymbol \pi}^\top\]

따라서 \({\boldsymbol \pi}\)는 정상분포가 된다.

특징4: 정상확률과정

만약에 \({\boldsymbol \pi}=\begin{bmatrix} 1/2 \\ 1/2 \end{bmatrix}\) 로 설정한다면 \(\{X_t\}\)는 모든 \(t\geq 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개는 존재한다.