[확률과정] 1.3 transition matrix

각각의 실행 때마다 어떤 체인으로 관측이 될지 궁금한 경우도 있겠지만, 여러번 실행한 결과가 어떻게 될지 궁금한 경우도 있을 것이다. 예를 들어, 넷플릭스에 회원가입한 상태를 E, 구독하여 구독료를 내고 있는 상태를 A라고 했을 때, 아래 그림대로 transition probability를 가진다고 가정해보자. 이번달에 구독하고 있는 유저는 다음달에 구독을 유지할 확률($p(A|A)$)이 60%, 다음달에 구독을 해지할 확률($p(E|A)$)이 40%...

 

Joxemai4, CC BY-SA 3.0, via Wikimedia Commons

 

만약 이번달에 비구독 가입상태인 유저가 천만명, 구독 상태인 유저가 2천만명이라고 했을 때, 다음달에는 비구독인 가입자와 구독 가입자의 수는 어떻게 변할까?

 

먼저, 다음달이 되면 비구독 유저 천만명 중에서 70%인 7백만명이 신규로 구독하게 될 것이다. 그러나 기존 구독 유저 중 40%인 8백만명이 구독을 해지하게 될 것이므로, 총 백만명이 감소한 1900만명이 구독 유저, 1100만명이 비구독 유저가 될 것이다. 그 다음달에는 다시 1900만명 중 40%가 해지하고, 1100만명 중 70%가 신규 구독하여, 1910만명의 유저가 구독하게 될 것이다.

#transition matrix

이 계산을 일반화하기 위하여, 가능한 state를 1, 2, ..., $N$이라고 하고, state $i$에서 state $j$로의 transition probability를 $p(i,j)$라고 하자. 그리고 ${\varphi }_i^{(t)}$를 시간 $t$에 state $i$에 있는 체인의 수라고 하자. 현재 state $i$에 ${\varphi }_i^{(t)}$개의 체인이 있다고 하면, $t+1$ 시점에 $i$에서 $j$로 전이되는 수는 ${\varphi }_i^{(t)}p(i,j)$가 된다. 결국 $t+1$ 시점에 $j$로 전이되는 수는 이 값들($j$ 자신도 포함되어 있다)을 모두 합한 값이 될 것이다.

$${\varphi }_j^{(t+1)}=\sum _{i=1}^N{\varphi }_i^{(t)}p(i,j)$$

이 식은 행렬의 곱으로 표현이 가능하다. 행렬 ${\varphi }^{(t)}$을

$$\begin{array}{l}(i\text{번째 열: }t\text{ 시점 state }i\text{ 개수})\\ {\varphi }^{(t)}=\left[\begin{array}{ccccc}{\varphi }_1^{(t)}& \cdots & {\varphi }_i^{(t)}& \cdots & {\varphi }_N^{(t)}\end{array}\right]\end{array}$$

로 쓰고, 행렬 $P$를

$$\begin{array}{l}(j\text{번째 열})\\ P=\left[\begin{array}{ccc}& ⋮& \\ \cdots & i\to j\text{ 전이 확률}& \cdots \\ & ⋮& \end{array}\right](i\text{번째 행})\end{array}$$

로 쓴다면, 위 식은 다음과 같은 행렬의 곱으로 표현된다.

$${\varphi }^{(t+1)}={\varphi }^{(t)}P$$

이 때 transition probability 값들을 성분으로 가지는 행렬 $P$를 transition matrix라고 부른다.

 

넷플릭스 예제를 적용하기 위해 E를 1번째 state, A를 2번째 state라고 하자. 그러면 transition matrix는

$$P=\left[\begin{array}{cc}.3& .7\\ .4& .6\end{array}\right]$$

그리고 $t$ 시점에 state matrix는

$${\varphi }^{(t)}=\left[\begin{array}{cc}1\times {10}^7& 2\times {10}^7\end{array}\right]$$

따라서 $t+1$ 시점에 state matrix는

$${\varphi }^{(t+1)}={\varphi }^{(t)}P=\left[\begin{array}{cc}1.1\times {10}^7& 1.9\times {10}^7\end{array}\right]$$

그리고 $t+2$ 시점에 state matrix는

$${\varphi }^{(t+2)}={\varphi }^{(t+1)}P={\varphi }^{(t)}{P}^2=\left[\begin{array}{cc}1.09\times {10}^7& 1.91\times {10}^7\end{array}\right]$$

처럼 $P$ 행렬의 거듭제곱을 이용하여 쉽게 계산할 수 있다.

 

만약 initial state가 하나의 값이 아니라 확률 분포 ${\varphi }^{(0)}$로 주어진다고 한다면, $t$ 시점의 state 분포는

$${\varphi }^{(t)}={\varphi }^{(0)}{P}^t$$

로 계산할 수 있다. 넷플릭스 예제에서 1번째 state에 1/3, 2번째 state에 2/3 비율로 분포해 있으므로, 이 식을 이용해 1달이 지난 시점, 2달이 지난 시점의 비구독자, 구독자 분포를 계산할 수 있다.

 

또한, initial state가 E일 때, $t=10$에서 state가 A일 확률을 계산하려면, initial state 분포를

$${\varphi }^{(0)}=\left[\begin{array}{cc}1& 0\end{array}\right]$$

로 설정하고 ${\varphi }^{(10)}={\varphi }^{(0)}{P}^{10}$을 계산하여 state가 E일 확률과 A일 확률을 얻을 수 있다.

#stochastic matrix

잠시 넷플릭스 예제의 transition matrix를 살펴보자.

$$P=\left[\begin{array}{cc}.3& .7\\ .4& .6\end{array}\right]$$

행렬의 각 행의 합을 살펴보면 모두 1이라는 것을 확인할 수 있다. transition matrix는 각 항이 반드시 1이 되는데, 이러한 성질은 각 성분값이 가지는 의미를 생각해보면 당연하다.

 

먼저, 행,열 (1,1) 위치에 있는 0.3은 현재 E에 있을 때, E에 그대로 있을 확률이다. (1,2) 위치에 있는 0.7은 현재 E에 있을 때, A로 전이될 확률이다. 이 둘을 합한 값은 현재 E에 있을 때, 다음에 E 또는 A에 있을 확률, 사실상 어디에든 있을 확률이므로 당연히 1이 되어야 한다. stochastic process가 $N$개의 상태에서 변화하는 것을 행렬로 표현한다면, 각 성분값은 확률을 표현하므로 0~1 사이의 값이 되어야 할 것이다. 또한 transition matrix처럼 각 행의 합이 항상 1이 되도록 구성하면 될 것이다. 따라서 이러한 성질을 만족하는 행렬을 stochastic matrix라고 부른다.

 

DEFINITION          stochastic matrix

$N\times N$ 행렬 $P$ 가 $i$행, $j$열 성분 p_{ij}에 대하여, $$\begin{array}{rl}p\le p_{ij}\le 1& \text{ for all }1\le i,j\le N\\ \\ \sum _{j=1}^N{p}_{ij}=1& \text{ for each }1\le i\le N\end{array}$$을 만족하는 경우, $P$를 stochastic matrix라고 부른다.

 

당연히, Markov chain의 transition matrix는 stochastic matrix의 일종이다.