[응용통계] 11. 마코프 체인 (Markov Chains) (5)

안녕하세요, 이번 포스팅에서는 마코프체인의 나머지 진도를 나가보도록 하겠습니다.

저희는 지금부터, State 간의 관계에 대해서 여러가지 정의를 내려보도록 하겠습니다.

accessible에 대한 정의는 아주 간단합니다.

State i에서 State j로 이동하는 경로가 존재한다면 State i는 State j로부터 accessible한 것입니다.

위의 State Relation에서 0->0, 1->1, 1->2, 1->3, 1->0, 2->1, 2->2, 2->3, 2->0, 3->3 의 관계가 존재합니다.

​

commincate에 대한 정의는 State i 와 State j 가 양방향으로 accessible 한 경우를 나타냅니다.

위의 State 관계에서는 (0,0), (1,1), (1,2), (2,2), (3,3)이 communicate 하겠네요.

communicating classes는 State를 그룹으로 묶는데, 같은 그룹안에 포함된 state들은 서로 communicate한 관계를 가져야 합니다.

위와 같은 State 관계에서는 3개의 communicating class를 정의할 수 있습니다.

C1 : {0}

C2 : {1,2,3,...,n-1}

C3 : {n}

​

만약에 마코프 체인이 오직 하나의 communicating class를 가진다면 irreducible이라고 정의합니다.

위의 마코프 체인은 {0,1} 하나의 class를 가지므로, irreducible 이 됩니다.

period 라는 개념은 d(j), 즉 j state에서 j state로 되돌아 오는데 소모되는 단계들의 최대 공약수로 정의됩니다.

예시를 통해 이해하시는게 쉬울겁니다.

위와 같은 관계에서 d(0)을 구해보도록 해보겠습니다.

0에서 0으로 되돌아오기 위해서는, 0->1, 1->2, ... , n-1 -> n, n->0 의 과정을 거쳐야 하기 때문에 총 n+1번의 단계를 거쳐야 합니다.

그리고 추가적으로 (n+1), 2(n+1), 3(n+1) 단계를 거치는 것이지요.

이러한 값들의 최대 공약수인 (n+1)이 d(0)이 됩니다.

​

그리고 1개의 예시를 더 가져와보았습니다.

d(2)를 구해봅시다.

2->0->1->2 : 3단계

2->0->1->0->1->2 : 5단계

이런식으로 3,5,7,9, ... 단계의 경우의 수가 있는데, 이들의 최대 공약수인 1이 d(2)가 됩니다.

​

state의 period가 1일 경우, aperiodic이라고 정의합니다.

fijn 을 state i 에서 state j 로 n 번째 step에 처음으로 갈 확률이라고 정의할 때, fij 는 모든 n에 대하여 fijn 의 값을 다 더한 값입니다.

recurrent 와 transient는 위와 같이 정의되어 있는데, 딱 봐서는 무슨 뜻인지 이해하기 힘듭니다.

쉽게 말해서, recurrent 하면, 단계를 무한히 진행하더라도, 언젠가는 돌아 올 수 있습니다.

반면에, transient 하면 단계를 무한히 진행할 경우, 못돌아오게 됩니다.

​

참고로, 마코프 체인에서 모든 state는 transient할 수 없습니다. 왜냐하면, 만약 모든 state가 transient하다면 무한히 단계가 진행됬을 때, 갈 수 있는 state가 없게 됩니다.

​

이제 몇가지 정리에 대해서 살펴보도록 하겠습니다.

Thm 1.은 Thm 2. 를 증명할 때 사용됩니다.

Thm 2. 는 i state 와 j state 가 communicate한 관계를 가질 때, j 가 recurrent 하다면 i 또한 recurrent 하다는 정리입니다.

​

예시를 통해 알아보겠습니다.

​

우리는 {0,1,2} , {3,4}, {5} class로 묶을 수 있습니다.

그리고 각 class는 다음과 같이 정의됩니다.

{0,1,2} : period는 1이고, positive recurrent

{3,4} : period는 2이고, transient

{5} : period는 1이고, positive recurrent 입니다.

​