마르코프 체인 (Markov Chain)

내일 날씨를 맞히는 데 지난 한 달의 날씨 기록이 전부 필요할까? 놀랍게도 오늘 날씨 하나만 알면 충분하다고 가정하는 모델이 있다. "미래는 오직 현재 상태에만 의존하고, 과거를 거쳐 온 경로와는 무관하다" — 이 성질을 마르코프 성질(memorylessness)이라 부르고, 이런 확률 모델을 마르코프 체인이라 한다.

1. 날씨로 직접 체험하기

맑음·흐림·비 세 가지 날씨가 있고, 오늘 날씨에 따라 내일 날씨가 될 확률이 다르게 정해져 있다. "한 걸음"을 누르면 흰 점이 현재 상태에서 다음 상태로 확률적으로 이동한다. 여러 번 반복하면 방문 빈도가 특정 비율로 수렴하는 것을 볼 수 있다.

2. 전이 확률 행렬

이 시스템의 규칙은 3×3 행렬 하나로 완전히 표현된다. 행(From)은 오늘 날씨, 열(To)은 내일 날씨다. 각 행의 합은 항상 1이어야 한다 — 오늘이 맑음이면 내일은 반드시 맑음·흐림·비 중 하나이기 때문이다.

3. 시간이 지나면 결국 한 지점으로 — 정상분포

걸음 수를 충분히 늘리면, 시작을 맑음에서 하든 비에서 하든 상관없이 각 날씨의 방문 비율은 같은 값으로 수렴한다. 이를 정상분포(stationary distribution) π라 하고, π = πP(분포에 전이 행렬을 곱해도 그대로 유지됨)를 만족한다. 위 행렬을 직접 풀면 다음과 같다.

4. 왜 "메모리 없음"이 중요한가

만약 내일 날씨가 오늘과 어제 둘 다에 의존한다면 이는 더 이상 (1차) 마르코프 체인이 아니다. 이런 경우엔 "지난 2일"을 하나의 상태로 묶어(예: "맑음→흐림") 상태 집합을 늘리면 다시 1차 마르코프 체인으로 표현할 수 있다 — 실제로 자연어 처리에서 "직전 n개 단어"를 상태로 삼는 n-gram 모델이 정확히 이 방식이다. 즉 "메모리가 없다"는 것은 한계가 아니라, 상태를 어떻게 정의하느냐에 따라 얼마든지 과거를 상태 안에 압축해 넣을 수 있다는 뜻이다.

5. 의사코드

# 한 걸음 시뮬레이션: 현재 상태의 확률 분포에서 다음 상태를 뽑는다
def step(P, state):
    r = random()  # 0 이상 1 미만 균등난수
    cumulative = 0
    for next_state, prob in enumerate(P[state]):
        cumulative += prob
        if r < cumulative:
            return next_state

# 정상분포: 분포 벡터에 P를 계속 곱해 수렴할 때까지 반복(거듭제곱법)
def stationary_distribution(P, iterations=200):
    n = len(P)
    pi = [1/n] * n
    for _ in range(iterations):
        pi = [sum(pi[i] * P[i][j] for i in range(n)) for j in range(n)]
    return pi

6. 어디에 쓰이나