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

최규빈

2023-05-23

강의영상

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

예비학습

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

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

\({\boldsymbol \mu}^\top = [0.1,0.2,0.7]\) 이다. 이럴 경우 평균은

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

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

  • \(\mathbb{E}_{\boldsymbol \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}_{\boldsymbol \mu}(X=0)=0.1\)
  • \(\mathbb{P}_{\boldsymbol \mu}(X=1)=0.2\)
  • \(\mathbb{P}_{\boldsymbol \mu}(X=2)=0.7\)

와 같이 표현하기도 한다.

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

\({\boldsymbol \mu}\)의 정의

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

\({\boldsymbol \nu}\)의 정의

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

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

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

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

  • \(\mathbb{P}_{{\boldsymbol \delta}_x}(X=x)=1\), \(\mathbb{P}_{{\boldsymbol \delta}_x}(X\neq x)=0\)
  • \(\mathbb{E}_{{\boldsymbol \delta}_x}(X)=x\)

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

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

\({\boldsymbol \mu}\)의 정의

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

\({\boldsymbol \nu}\)의 정의

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

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

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

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

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

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

  • 2 \(X_0 \sim {\boldsymbol \delta}_i^\top\) 를 가정하고 구한 확률

  • 3 \(X_t \sim {\boldsymbol \pi}^\top\) 를 가정하고 구한 확률인것 처럼 보임, 하지만 사실 \(X_0 \sim {\boldsymbol \pi}^\top\)를 가정한 것

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

    nature (cont)

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

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

    - 의미:

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

  • 4 \(t=0\) 시점에 마을 \(y\)에 존재하던 나그네

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

    \[\mathbb{P}_i(T_i<\infty)=1\]

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

    \[\mathbb{E}_i[T_i] < \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}^{\infty} E_k\]

    이때

    1. \(E_1,E_2,E_3,\dots\) 는 서로소
    2. \(\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}^{\infty} E_k\]

    이때

    1. \(E_1,E_2,E_3,\dots\) 는 서로소
    2. \(\forall k:\) \(E_k\) 는 IRR
    3. \(\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{\boldsymbol \pi}^\top {\bf P} = \tilde{\boldsymbol \pi}^\top\]

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

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

    \[\tilde{\boldsymbol \pi}^\top = [1,1,1,\dots]\]

    이 수식

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

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

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

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

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

  • 5 irreducible 한 homogeneous markov chain

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

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

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