Markov Chains

○Markov Chains

 ▷미래 상태의 조건부 확률 분포가 과거 상태와는 독립적으로 현재 상태에 의해서만 결정된다.

 

 ▷State Space (I)

  ▷상태들의 집합. 

 

 ▷Stochastic Process (X_n = i)

  ▷n번 이후의 상태가 i일 확률.

 

 ▷Markov Stochastic Process

  ▷미래의 상태 X_n+1이 현재의 상태 X_n에만 영향을 받는 Stochastic process

  ▷Time homogeneous

  ▷P_i,j = 현재 상태가 i일때, 다음 상태가 j일 확률

 

 ▷Transition Matrix

  ▷Pi,j들을 Transition Matrix로 표현한 것.

 

 ◎어제와 오늘이 내일의 날씨에 영향을 줄때

  ▷O : 비가 옴, X: 비가 오지 않음

  ▶확률들

   ▷O,O -> O : 0.7

   ▷X,O -> O : 0.5

   ▷O,X -> O : 0.4

   ▷X,X -> O : 0.2

 

  ▷과거 상태 또한 영향을 주기 때문에, Markov Chain으로 바로 만들 수 없다.

  ▷2일의 날씨를 하나의 상태로 묶는다.

  ▷0: (O,O), 1: (X,O), 2:(O,X), 3:(X,X)

 

 ◎Random Walk Model

  ▷상태 : 정수집합

  ▷확률 : +1 -> p, -1 -> 1-p

  ▶Gambling Model

   ▷상태 : 자연수 집합

   ▷0 또는 N일때 상태를 전이하지 않는다.

 

 

○State Classification

 ▶Accessible (i → j)

  ▷P_i,j⁽ⁿ⁾ > 0인 경우 (어떤 0이상의 n에 대해서)

  ▷i에서 j로 접근가능함.

 

 ▶Communication (i ↔ j)

  ▷2개의 상태 i, j에 대해 i → j, j → i인경우 (서로 accessible한 경우)

  ▶equivalent relation이다.

   ▷Reflective: i ↔ i

   ▷Symmetric: i ↔ j => j ↔ i

   ▷Transitive: i ↔ j, j ↔ k => i ↔ k

 

 ▶Irreducible

  ▷Communicative한 상태들은 같은 Class에 있음.

  ▷Markov chain에서 class가 오직 하나인 경우, irreducible함.

 

 ▶Recurrent (재귀적) vs Transient (일시적)

  ▶Recurrent: 언젠가 제자리를 다시 지날수 있는 State

   ▷i가 Recurrent하다면, i과 Commucative한 다른 State도 Recurrent하다.

   ▷f_i,j = 1이면 recurrent하다.

 

   ▶Positive Recurrent, Null Recurrent

    ▷N_j: 돌아가는데 걸리는 최소 transition, m_j: N_j의 Expectation 일 때

    ▷m_j < ∞이면 positive recurrent, m_j = ∞이면 null recurrent

    ▷i가 Positive Recurrent하다면, i과 Commucative한 다른 State도 Positive Recurrent하다.

 

  ▷Transient: 한 번 지난 이후에는 다시 지나지 않는 State

  ※Periodic(주기적): 주기적으로 돌아오는 State