학습목표
마코프 체인의 개념과 전이행렬, 고정된 분포(stationary distribution)을 이해할 수 있다.
핵심 키워드
- 마코프 체인(Markov Chain)
- 전이확률(transition probability)
- 전이행렬(transition matrix)
- 고정된 분포(stationary distribution)
학습하기
31강- 마코프 체인(Markov Chains)
학습내용
마코프 체인(Markov Chains)
(→ iid 가정이 성립하지 않은 경우에는 어떻게 해야 하는가? (LLN 등이 여전히 성립하는가?)
정의) X_0, X_1, X_2,...X0,X1,X2,... 가 어떤 시간 구간(이산적인 시공간의 개념)에서의 '상태(state)'라고 하였을 때,
P(X_{n+1} = j|X_n = i, X_{n-1} = i_{n-1}, ..., X_0 = i_0)P(Xn+1=j∣Xn=i,Xn−1=in−1,...,X0=i0)
= P(X_{n+1} = j |X_n = i)=P(Xn+1=j∣Xn=i)
\Rightarrow⇒ 즉, 과거와 미래는 현재의 상태가 주어졌을 때 조건부 독립이 성립한다(conditionally independent)
= q_{ij}=qij → 전이확률(Transition probability). nn에 의존하지 않는다.
- Xn의 상태에서 Xn+1 상태로 넘어갈 때, 각각의 확률
전이행렬(Transition Matrix)
Q= q_{ij}Q=qij
시점 nn에 X_nXn는 \vec ss⃗ 의 분포를 따른다고 할 때 (\vec ss⃗ 는 1 \times M1×M 행렬이다),
P(X_{n+1} =j) = \displaystyle \sum _i P(X_{n+1} = j | X_n = i)P(X_n = i)P(Xn+1=j)=i∑P(Xn+1=j∣Xn=i)P(Xn=i)
= \displaystyle \sum _i s_i q_{ij}=i∑siqij ( \rightarrow \space \vec sQ(→ s⃗Q의 j번째 항))
\vec s Qs⃗Q 는 (n+1)(n+1) 시점에서의 분포,
\vec s Q^2s⃗Q2 는 (n+2)(n+2) 시점에서의 분포,
\cdots⋯
\vec s Q ^ks⃗Qk 는 (n+k)(n+k) 시점에서의 분포이다.
P(X_{n+1} = j| X_n = i) = q_{ij}P(Xn+1=j∣Xn=i)=qij
P(X_{n+2} = j| X_n = i) = \displaystyle \sum _k P(X_{n+2} = j| X_{n+1} = k, X_n = i)P(X_{n+1} = k|X_n = i)P(Xn+2=j∣Xn=i)=k∑P(Xn+2=j∣Xn+1=k,Xn=i)P(Xn+1=k∣Xn=i)
= \displaystyle \sum _k q_{ik}q_{kj}=k∑qikqkj (\rightarrow \space Q^2(→ Q2의 (i, j)(i,j) 번째 항)
\cdots ⋯
P(X_{n+m} = j |X_n = i) = Q^mP(Xn+m=j∣Xn=i)=Qm의 (i,j)(i,j) 번째 항
고정된 분포(Stationary Distribution)
(→ 마코프 체인이 반복되다 보면 언젠가는 어떤 상태에 수렴하게 되는가?)
\vec ss⃗ (1\times M1×M의 확률 벡터)는 \vec s Q = \vec ss⃗Q=s⃗ 를 만족할 때 고정된 분포이다.
체크사항:
- 고정된 분포라는 것이 존재할 수 있는가?
- unique한 분포인가?
- 마코프 체인이 실제로 \vec ss⃗ 에 결국 수렴하는가?
- 고정된 분포 \vec ss⃗를 어떻게 구할 수 있는가?