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가 동일한 벡터를 가진다면1 \({\bf P}^\star\)의 임의의 row-vector \({\bf p_{\star}^\top}\) 를 \(\{X_t\}\)의 극한분포 (limiting distribution) 라고 한다.

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

    • - 이론: 극한분포가 존재한다면, 유일하다. (그래서 극한분포는 기껏해야 (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 라고 하자.2 그렇다면 극한분포 \({\bf p}_{\star}^\top\)이 항상 존재한다.

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

    • 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
    느낌 데이터로 계산한 평균값 이론적인 기대값 이론적인 수렴값

    이론들의 의미를 다시 고찰

    - 에르고딕정리: 임피리컬분포와 정상분포에 관련한 정리 (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의 정의를 만족하지 않음.