12wk-2: 마코프체인 (11)

최규빈

2023-05-23

강의영상

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

예비학습

- 약어: $X$가 ${\mathbb{N}}_0$에서 값을 가지는 이산형확률변수이고 ${\mathit{\mu }}^{\mathrm{\top }}$ 가 $X$의 분포라고 하자. 이해를 위해서 아래와 같은 확률분포표를 가정한다면

$X$	$0$	$1$	$2$
$\mathbb{P}(X=k)$	$0.1$	$0.2$	$0.7$

${\mathit{\mu }}^{\mathrm{\top }}=[0.1,0.2,0.7]$ 이다. 이럴 경우 평균은

• $\mathbb{E}(X)=0\times 0.1+1\times 0.2+2\times 0.7$

와 같이 표현가능한데, 이를 좀 더 명확하게 하기 위하여

• ${\mathbb{E}}_{\mathit{\mu }}(X)=0\times 0.1+1\times 0.2+2\times 0.7$

라고 표현하기도 한다. 마찬가지로

• $\mathbb{P}(X=0)=0.1$
• $\mathbb{P}(X=1)=0.2$
• $\mathbb{P}(X=2)=0.7$

를 좀 더 명확하게 하기 위해서

• ${\mathbb{P}}_{\mathit{\mu }}(X=0)=0.1$
• ${\mathbb{P}}_{\mathit{\mu }}(X=1)=0.2$
• ${\mathbb{P}}_{\mathit{\mu }}(X=2)=0.7$

와 같이 표현하기도 한다.

- 예시: $X$의 분포 $\mathit{\mu }$와 $\mathit{\nu }$가 각각 아래와 같다고 하자.

$\mathit{\mu }$의 정의

$X$	$1$	$6$
$\mathbb{P}(X=k)$	$0$	$1$

$\mathit{\nu }$의 정의

$X$	$1$	$6$
$\mathbb{P}(X=k)$	$1$	$0$

이 경우 아래의 표현들이 가능하다.

1. ${\mathbb{E}}_{\mathit{\mu }}(X)=6$, ${\mathbb{E}}_{\mathit{\nu }}(X)=1$
2. ${\mathbb{P}}_{\mathit{\mu }}(X=1)=0$, ${\mathbb{P}}_{\mathit{\mu }}(X=6)=1$, ${\mathbb{P}}_{\mathit{\nu }}(X=1)=1$, ${\mathbb{P}}_{\mathit{\nu }}(X=6)=0$

- 약어: 확률변수 $X$가 $X=x$에서만 확률을 가지고 그 외에는 1이라고 할 경우 분포 $\mathit{\mu }$를 ${\mathit{\delta }}_x$라고 표현하기도 한다. 따라서 이 경우

• ${\mathbb{P}}_{{\mathit{\delta }}_x}(X=x)=1$, ${\mathbb{P}}_{{\mathit{\delta }}_x}(X\ne x)=0$
• ${\mathbb{E}}_{{\mathit{\delta }}_x}(X)=x$

와 같은 표현들이 가능하다.

- 예시: $X$의 분포 $\mathit{\mu }$와 $\mathit{\nu }$가 각각 아래와 같다고 하자.

$\mathit{\mu }$의 정의

$X$	$1$	$6$
$\mathbb{P}(X=k)$	$0$	$1$

$\mathit{\nu }$의 정의

$X$	$1$	$6$
$\mathbb{P}(X=k)$	$1$	$0$

이 경우 아래의 표현들이 가능하다. (??)¹

¹ 사실 이렇게 쓰는걸 본적은 없음

1. ${\mathbb{E}}_{{\mathit{\delta }}_6}(X)=6$, ${\mathbb{E}}_{{\mathit{\delta }}_1}(X)=1$
2. ${\mathbb{P}}_{{\mathit{\delta }}_6}(X=1)=0$, ${\mathbb{P}}_{{\mathit{\delta }}_6}(X=6)=1$, ${\mathbb{P}}_{{\mathit{\delta }}_1}(X=1)=1$, ${\mathbb{P}}_{{\mathit{\delta }}_1}(X=6)=0$

- 약어: $\{X_t\}$가 상태공간 $E$에서 정의된 HMC 라고 하자.

1. ${\mathbb{P}}_i(X_t=k):={\mathbb{P}}_{{\mathit{\delta }}_i}(X_t=k)=\mathbb{P}(X_t=k|X_0=i)$²
2. 1의 표현에서 ${\mathit{\delta }}_x$ 대신에 일반적인 $\mathit{\mu }$를 쓰기도 함.
3. ${\mathbb{P}}_{\mathit{\pi }}(X_t=k)={\pi }_k$³

² $X_0\sim {\mathit{\delta }}_i^{\mathrm{\top }}$ 를 가정하고 구한 확률

³ $X_t\sim {\mathit{\pi }}^{\mathrm{\top }}$ 를 가정하고 구한 확률인것 처럼 보임, 하지만 사실 $X_0\sim {\mathit{\pi }}^{\mathrm{\top }}$를 가정한 것

${\mathbb{P}}_i$, ${\mathbb{P}}_{\mathit{\pi }}$ 등이 자명한 기호는 아니므로 교재마다 초반부에 정의하고 들어감헷갈리는 편임. 일반적인 기호와 충돌이 오지만 정상분포일 경우 그 의미가 같음.

nature (cont)

- 정의: $\{X_t\}$가 상태공간 $E$에서 정의된 HMC 라고 하자. $y\in E$, $t\in {\mathbb{N}}_0$에 대하여 아래와 같은 기호를 정의하자.

1. $T_y=min\{t:X_t=y,t\ge 1\}=min\{t\ge 1:X_t=y\}$
2. $P_y(T_y<\mathrm{\infty })$

- 의미:

1. 나그네가 마을 $y$ 에 $t=0$, $t=2$, $t=5$, $t=88$ 에 방문하였다고 하자.
2. $\{t:X_t=y,t\ge 1\}=\{2,5,88\}$
3. $min\{t:X_t=y,t\ge 1\}=2$
4. $T_y=$ 나그네가 마을 $y$에 처음으로 방문한 시점, 단 $t=0$인 경우는 제외함.
5. $T_y=\mathrm{\infty }$ $\iff$ 나그네가 마을 $y$에 갈 일이 없음
6. $T_y<\mathrm{\infty }$ $\iff$ 나그네가 마을 $y$에 언제가는 돌아옴
7. ${\mathbb{P}}_y(T_y<\mathrm{\infty })=$ 초기상태를 마을 $y$에 출발한 나그네⁴가 언젠가 다시 $y$로 돌아올 확률
8. 7의 의미는 “마을 $y$에 존재하던 나그네가 언젠가 다시 마을 $y$로 돌아올 확률”이라 해석해도 무방하다.

⁴ $t=0$ 시점에 마을 $y$에 존재하던 나그네

- 정의: $\{X_t\}$가 상태공간 $E$에서 정의된 HMC 라고 하자. $T_i$를 상태 $i\in E$에 대한 return time 이라고 하자. 만약에 상태 $i\in E$ 가 아래의 식을 만족한다면

$${\mathbb{P}}_i(T_i<\mathrm{\infty })=1$$

$i$는 recurrent 하다고 표현하고, 그렇지 않으면 $i$는 transient 하다고 표현한다. 만약에 recurrent state $i$가 아래식을 만족한다면

$${\mathbb{E}}_i[T_i]<\mathrm{\infty }$$

state $i$를 positive recurrent 라고 하고 그렇지 않으면 null recurrent 라고 한다.

- 이론: HMC $\{X_t\}$가 IRR 이라면 모든 $i$는 같은 nature 를 가진다. 즉 $\{X_t\}$가 IRR 이면 아래중의 하나이다.

1. 모든 상태가 transient 하다.
2. 모든 상태가 null recurrent 하다.
3. 모든 상태가 positive recurrent 하다.

HMC $\{X_t\}$의 모든상태가 positive recurrent 이면, positive recurrent markov chain 이라고 간단히 부른다. 나머지 역시 마찬가지

- Thm(상태의분해1): $\{X_t\}$가 HMC라고 하고, $E$를 $\{X_t\}$가 정의되는 상태공간이라고 하자. 기호 $\leftrightarrow$는 $E$에서 정의된 euivalence relation이 된다. 따라서 집합 $E$의 원소는 $\leftrightarrow$를 기준으로 아래와 같이 나눌 수 있다.

$$E={\uplus }_{k=1}^{\mathrm{\infty }}{E}_k$$

이때

1. $E_1,E_2,E_3,\dots$ 는 서로소
2. $\mathrm{\forall }k:$ $E_k$ 는 IRR

이다.

- Thm(상태의분해2)(Durrett 2019, Thm 5.3.5): $\{X_t\}$가 HMC라고 하고, $E$를 $\{X_t\}$가 정의되는 상태공간이라고 하자. 집합 $E$는 아래와 같이 분해할 수 있다.

Durrett, Rick. 2019. Probability: Theory and Examples. Vol. 49. Cambridge university press.

$$E={\uplus }_{k=1}^{\mathrm{\infty }}{E}_k$$

이때

1. $E_1,E_2,E_3,\dots$ 는 서로소
2. $\mathrm{\forall }k:$ $E_k$ 는 IRR
3. $\mathrm{\forall }k:$ $E_k$ 의 모든 원소는 PR 이거나 NR 이거나 TR

이다.

- 따라서 transition matrix는 일반적으로 아래와 같이 분해하여 생각할 수 있다.

그림1: 전이행렬의 분해 (Brémaud 2020, p 117)

Brémaud, Pierre. 2020. Markov Chains: Gibbs Fields, Monte Carlo Simulation, and Queues. Springer Cham.

nature와 정상분포

- 정의 $\{X_t\}$가 HMC라고 하자. 아래의 식을 만족하는

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

$\mathbf{0}$이 아닌 ${\tilde{\mathit{\pi }}}^{\mathrm{\top }}$ 를 invariant measure 라고 한다. 만약에 ${\tilde{\mathit{\pi }}}^{\mathrm{\top }}$ 이 분포의 정의를 만족하면 stationary measure 혹은 stationary distribution 이라고 부른다.

- 예시: “오른쪽으로만 갈래” 예제에서는

$${\tilde{\mathit{\pi }}}^{\mathrm{\top }}=[1,1,1,\dots ]$$

이 수식

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

을 만족한다. 따라서 이 예제에서 ${\tilde{\mathit{\pi }}}^{\mathrm{\top }}=[1,1,1,\dots ]$ 은 invariant measure 이다.

- $\{X_t\}$가 HMC라고 하자. 각각에 대하여 아래가 성립한다.

IRR	nature	$\mathrm{\exists }!\tilde{\mathit{\pi }}$ up to multiplier	$\mathrm{\exists }!\mathit{\pi }$	에르고딕정리($\approx$LLN)
$O$	PR	$O$	$O$	$O$
$O$	NR	$O$	$X$	$X$
$O$	TR	$\mathrm{\Delta }$	$X$	$X$

- 이론: $\{X_t\}$가 IRR-HMC⁵ 라고 하자. $\{X_t\}$가 정상분포를 가진다는 조건과 유일한 정상분포를 가질 조건은 동치이다.

⁵ irreducible 한 homogeneous markov chain

• 즉 $\{X_t\}$가 IRR-HMC 일때, 정상분포가 존재한다는 사실만 보이면 자동으로 유일성이 보장된다.

- Thm: $\{X_t\}$가 IRR-HMC 라고 하자. 그러면 positvite recurrent 와 $\mathrm{\exists }!\mathit{\pi }$ 은 동치조건이다. 즉

• IRR-HMC $\{X_t\}$ 가 positive recurrent 하다면 항상 $\{X_t\}$ 는 유일한 정상분포를 가진다.
• IRR-HMC $\{X_t\}$ 가 정상분포를 가지면 (그 분포는 유일해지고) $\{X_t\}$는 항상 positive recurrent 하다.