1. 정의

• 마르코프 체인은 유한한 상태 집합 S 위에서 "현재 상태"만을 보고 다음 상태로 전이될 확률을 모델링한 확률 과정이다.
• 기억 상실(Memoryless) 성질: 미래 상태는 오직 현재 상태에만 의존하며, 그 이전의 경로(history)는 전혀 영향을 주지 않는다.

2. 구성 요소

1. 상태 집합

$$ S = \{s_1, s_2, \dots, s_n\} $$

1. 전이 확률

$$ P_{ij} = P(X_{t+1} = s_j \mid X_t = s_i) $$

– 모든 i에 대해: $\sum_{j}P_{ij}=1$

1. 초기 분포 $\pi^{(0)}$

$$ \pi_i^{(0)} = P(X_0 = s_i) $$

3. 1차(First-order) 마르코프 성질

“다음 상태는 오직 바로 이전 상태만 보고 결정된다”는 성질이다.

$$ P(X_{t+1} = s_j \mid X_t = s_i,\;X_{t-1},\dots,X_0) = P(X_{t+1} = s_j \mid X_t = s_i) $$

예시 코퍼스

ABACABA

문자열 길이 7, 상태 집합 S={A,B,C}

(1) 바이그램 카운트