아이고리즘

이 글에선 Fundamental Theorem of Markov Chains의 증명을 마루리 하고자 한다. 지난글: https://cultivated-algorist.tistory.com/entry/Fundamental-Theorem-of-Markov-Chains-1 이전 글에서 Finite Markov chain은 항상 stationary distribution이 존재함을 보였다. 과연 stationary distribution은 unique할까? 그리고 임의의 시작 분포에서 시작하더라도 stationary distribution으로 수렴할까? 이 두 질문에 답하기 위해 두가지 개념을 생각하고자 한다. Irreducibility Markov chain을 directed graph라고 생각하자. 이때 그..

Stochastic Process 2022. 8. 4. 14:48

시작하기 앞서 Markov chain을 처음 들어보는 사람들을 위해 이를 간단하게 설명하고자 한다. Markov chain은 시간이 흐르면서 변화가 어떻게 이루어지는 지에 대한 확률 과정인 stochastic process의 특수한 경우이다. 이때 Markov chain에서의 시간의 변화는 이산적이다. 예를 들어 동전을 계속 던지는 게임을 한다고 생각하자. 동전을 한 번 던지는 것을 한 라운드로 생각한다면, 여기서의 시간의 변화는 라운드의 변화로 생각할 수 있다. 즉 $t$ 시점에서 $t+1$ 시점으로 가는 것을 $t$ 라운드에서 $t+1$ 라운드로 가는 것으로 생각할 수 있다는 것이다. 여기서 "변화"라는 것은 Markov chain의 용어로 설명하자면 "어떤 상태(state)에서 어떤 상태로 이동"하..

Stochastic Process 2022. 8. 2. 18:06