Markov Chain

: http://pages.uoregon.edu/dlevin/MARKOV/markovmixing.pdf

이 포스팅을 시작하는 이유는 내가 다음의 내용을 수학적으로 증명하려고 하기 위해서이다. 

학습을 할 때, 좋은 예제만 보여주는 것 보다 안 좋은 예제를 같이 보여주는 것이 (물론 이것이 안좋다는 정보와 함께) 더 효과적인 학습을 가능하게 한다. 

당연해보이는 글귀이지만, 이를 수학적으로 보이기 위해선 몇 가지 세팅이 필요하다. 먼저 우리가 학습하는 것이 무엇인가에 대한 것이다. 여기서 학습이라는 것은 주어진 환경에서 어떤 행동을 하는 것이 옳은지를 나타낸다. 수학적으로는 어떤 공간 '$X$'가 있을 때, 이 공간과 행동들의 집합 '$U$'를 연결해주는 어떤 함수 '$f: X \to U$'를 찾는 것이라고 볼 수 있다. 

여기까지는 Markov chain과 전혀 연관이 없어보인다. 하지만 우리가 '$x_t \in X$'를 돌아다니면서 해당 위치에서 얻은 '$f(x_t)$'를 관측하고, 이렇게 모인 데이터를 통해서 '$f$'를 추론한다고 하면 약간의 연관 관계가 생긴다. 즉 '$x_t$'가 임의로 움직이는 것이 아니라 어떤 확률 모델을 통해서 움직일 때 우리는 이를 Markov chain이라고 볼 수 있기 때문이다. 서론이 길었다. 자 시작해보자. 

얼마나 이 책을 커버할 수 있을지는 모르겠다.. 

위의 그림은 각 챕터의 dependency를 나타낸 것이다. 4장 까지만 할 수 있었으면 좋겠다. 

Chapter 1 Introduction to Finite Markov Chains

A finite Markov chain의 정의는 다음과 같다. 우리에게 finite set '$\Omega$'가 주어졌고, 특정 위치 '$x \in \Omega$'에 있을 때, 다음 번 위치는 특정 확률 '$P(x, \cdot)$'에 의해서 결정이 된다. 좀 더 정확히 말하자면, a sequence of random variables '$(X_0, X_1, ...)$' is a Markov chain with state space '$\Omega$' and transition matrix '$P$' if for all '$x, y \in \Omega$', all '$t \ge 1$', and all events '$H_{t-1} \cap_{s=0}^{t-1}\{ X_s = x_s \}$' satisfying '$P(H_{t-1} \cap \{ X_t=x \}) > 0$', we have

복잡하고 어려워 보이지만, 결국 위의 (1.1)이 의미하는 것은 특정 state '$x$'에서 '$y$'로 가는 확률은 그 둘에만 달려있다는 것이고, 이는 이러한 이동 확률을 '$|\Omega| \times |\Omega|$'의 크기를 갖는 '$P$'로 나타낼 수 있게한다. 물론 '$P$'의 row-sum은 1이된다. 

간단한 예를 들어보자. 

만약 위의 개구리가 매일 어느 연못에 있을지를 동전을 던저서 정한다고 하자. 즉 양쪽 연못에는 동전이 하나씩 있고, 해당 연못에서 동전을 던저서 앞면이 나오면 다른 연못으로 이동하고, 그렇지 않으면 그자리에 있는다고 하자. 물론 두 동전의 앞면이 나올 확률은 다르다고 생각하자. 그러면 이 상황에서 transition matrix는 다음과 같을 것이다. 

개구리가 일요일에는 왼쪽 연못에 있었다고 가정하자. 이 상황에서 이 개구리가 월요일에 오른쪽 연못으로 갈 확률은 '$p$'이고, 제자리에 있을 확률은 '$1-p$'이다. 이를 써보면 아래와 같다. 

만약 다음날은 어떨까? 다음날에 대한 확률을 써보면 다음과 같다. 

조금 더 복잡해졌다. 이를 효과적으로 계산할 수 있는 방법은 다음과 같다. 만약 초기 상태 (혹은 확률)을 '$\mu_0$'라고 한다면, 시간 '$t$'에서 각 상태의 확률은 

$$ \mu_t = \mu_0 P^t $$

와 같이 나타낼 수 있다. 

자 그렇다면, 만약 이 개구리가 무한히 시간을 보냈을 때, 각 연못에 어느 정도의 확률로 거했을지는 어떻게 구할 수 있을까? 이는 다음의 수식을 통해서 구할 수 있다. 

$$ \pi = \pi P $$

우리의 개구리의 경우 '$\pi$'는 다음과 같다. 

$$ \pi(e) = \frac{q}{p+q}, ~~~~ \pi(w) = \frac{p}{p+q} $$

만약 우리가 

$$ \bigtriangleup_t = \mu_t(e) - \frac{q}{p+q} $$

라고 정의하면, 정의해 의해서 

$$ \bigtriangleup_{t+1} = (1-p-q)\bigtriangleup_t $$

를 만족한다. 

여기서 '$1-p-q$'라는 값은 '$P$'의 eigenvalue에 해당한다. 물리적으로는  현재 상황에서 empirical state distribution이 steady state distribution에 얼마나 빨리 다가가는지를 나타낸다. 

$$ \bigtriangleup_{t+1} = (1-p-q)^t \bigtriangleup_0 $$

여기서 한 가지 주의할 점은 우리의 '$P$'의 row들이 transition을 의미하므로, state 분포는 '$P$'의 '왼쪽'에 곱해져야 한다. 물론 state의 분포를 나타내는 vector는 row vector여야 한다. ('$\mu_t = \mu_0*P^t$')

Irreducible: 모든 state가 연결되어 있다. (직접이 아니더라도! 이 부분이 중요하다.) 즉 타고 타고 타고 .. 타고 넘어가서 연결되기만 해도 해당 Markov chain은 irreducible하다고 한다. 

Period: 각 state '$x$'에서 출발을 해서, 자기 자신으로 돌아올 수 있는 가능성이 있는 시간들의 집합을 '$\tau$'라 했을 때, 이 '$\tau$'의 최대공약수를 해당 state의 period라고 한다. 최대공약수 (gcd)가 나오는 이유는 chain이기 때문에 돌고 돌고 돌 수 있기 때문이다. 

Chapter 2 Classical (and Useful) Markov Chains

몇 가지 간단한 Markov Chain에 대해서 알아보자. 

Gambler's Ruin - 도박사의 망함? 

어떤 도박사가 있어서, 동전의 앞면이 나오면 1달러를 벌고, 뒷면이 나오면 1달러를 잃는다고 하자. 이 경우, '$\{ 0, 1, 2, ... \}$'의 vertice 위에서 random walk를 한다고 볼 수 있을 것이다. 여기서 두 가지 질문을 할 수 있다. 

1. 도박사의 목표가 n달러를 버는 것이라 할 때, 과연 얼마만에 파산, 혹은 n달러를 벌 수 있을까?

2. 각 종착지의 확률은 얼마일까?

도박사가 갖고 있는 동전의 앞, 혹은 뒤가 나올 확률은 공평하다고 하자. 그리고 '$X_t$'를 시간 '$t$'에서 도박사가 갖고 있는 돈이라 하고, '$\tau$'를 '$X_t$'가 '$0$' 또는 '$n$'이 되는데까지 걸린 시간이라 하자. 

처음에 갖고 있는 돈을 '$X_0 = k$'라 하면, 

$$ P_k\{ X_{\tau} = n \} = \frac{k}{n} $$

이고, 

$$ E_k(\tau) = k(n-k) $$

이다. 

위 두 식 중 첫번쨰 식이 의미하는 것은 '$\tau$'라는 종착 시간에 도박사가 원하는 '$n$'의 돈을 벌 확률은 '$k/n$'이라는 것이다. 즉 초기 자본을 벌고 싶은 돈으로 나눈 것이다. 직관적이다. 

두 번째 식이 의미하는 것은 종착시간의 평균은 초기 자본 * 추가로 벌고자 하는 돈 이다. 

Proof) '$p_k$'를 도박사가 '$k$' 달러를 갖고 시작을 했을 때 '$n$'의 돈을 벌 수 있는 확률이라고 하자. (물론 파산하기 전에) 당연히 '$p_0 = 0$'이고, '$p_n = 1$'이다. 그리고 

$$ p_k = \frac{1}{2}p_{k-1} + \frac{1}{2}p_{k+1} ~~~~ for ~~ 1 \le k \le n-1 $$

이다. 

왜그럴까? 현재 Markov chain은 '$1/2$'의 확률로 왼쪽으로 (돈을 잃고), '$1/2$'의 확률로 오른쪽으로 (돈을 따고) 이동하기 때문이다. 위의 시스템을 풀게 되면 '$p_k = k/n$'을 얻을 수 있다. 

이를 그림으로 그려보면 위와 같다. 

이제 각 종료점으로 가는데 얼마나 걸리는지를 구하기 위해서 '$f_k$'를 '$k$'에서 시작을 해서 종료할 때 까지 걸리는 시간의 기대값이라고 하자. 이 경우엔 '$f_0 = f_n = 0$'이다. 즉 각 종료점에서 시작을 하면 바로 종료를 할 것이다. 이 경우도 위와 비슷하게 

$$ f_k = \frac{1}{2}(1+f_{k+1}) + \frac{1}{2}(1+f_{k-1}). $$

로 나타낼 수 있다. 먼저 움직임이 도박사에게 돈을 벌어준다면 (확률은 '$1/2$') 종료할 때 까지 걸리는 시간의 기대값은 '$1$'과 '$k+1$'의 돈을 갖고 있을 때 종료할 때 까지 걸리는 기대값의 합일 것이다. 마찬가지로 돈을 잃을 때도 종료할 때 까지 걸리는 시간의 기대값은 '$1$'과 '$k-1$'의 돈을 갖고 있을 때 종료할 때 까지 걸리는 시간의 기대값을 더한 것일 것이다. 

Coupon Collecting - 쿠폰 모으기?

어떤 회사가 '$n$'개의 다른 종류의 쿠폰을 발행한다고 하자. 그리고 어떤 수집가는 이 모든 쿠폰을 모으고 싶어한다. 해당 과자를 먹으면 '$n$'개의 쿠폰이 동등한 확률로 하나 주어진다고 하자. 그럼 몇 개의 과자를 먹어야 할까? 

이 세팅은 Markov chain과 상관없어 보일 수 있다. 하지만 '$X_t$'를 시간 '$t$'에서 모아진 서로 다른 종류의 쿠폰의 수라고 하자. 그럼 '$X_0 = 0$'일 것이다. 만약 수집가가 '$k$'개의 쿠폰을 갖고 있다면 '$n-k$'개의 쿠폰을 더 모아야 한다. 즉 '$n$'개의 쿠폰 중에서 오직 '$n-k$'만이 '$X_t$'를 높이는데 기여할 수 있다. 

$$ p\{X_{t+1} = k+1 | X_{t} = k \} = \frac{n-k}{n} $$

이고 

$$ p\{ X_{t+1} = k| X_t = k \} = \frac{k}{n} $$

이다. 

물론 '$X_{t+1}$'은 줄어들지는 않는다. 그리고 '$n$'에 도달할 경우 거기서 끝난다. 우리가 관심있는 값은 과면 얼마나 과자를 먹어야 모든 쿠폰을 얻을 수 있나 이다.