마르코프 체인이란? 식당 메뉴 예시로 보는 상태 전이와 마르코프 성질, 정상분포의 원리

핵심 메시지

• 마르코프 체인은 여러 '상태'와 그 사이를 잇는 확률(전이)로 이뤄진 모델로, 통계·생물학·경제학·물리학·머신러닝 등에서 두루 쓰인다.
• 핵심인 '마르코프 성질'은 다음 상태가 오직 현재 상태에만 달려 있고, 그 이전의 과정은 따지지 않는다는 것이다.
• 각 상태에서 나가는 화살표 확률의 합은 항상 1이며, 무작위 행보를 길게 반복하면 상태 확률이 일정한 값으로 수렴한다.
• 이 수렴값을 '정상분포(평형 상태)'라 부르며, 전이 행렬의 고윳값 1에 해당하는 좌고유벡터를 풀어 직접 구할 수 있다.

쉽게 이해하기

마르코프 체인은 통계학부터 생물학, 경제학, 물리학, 그리고 머신러닝까지 폭넓게 쓰이는 개념이다. 이름은 어렵게 들리지만 발상은 의외로 단순하다. 햄버거·피자·핫도그 세 가지만 파는 식당을 떠올려 보자. 이 식당은 하루에 한 메뉴만 내고, 그날 무엇을 낼지는 어제 무엇을 냈는지에 따라 정해진다. 예컨대 오늘이 햄버거 날이면 내일 피자가 나올 확률이 60%인 식이다.

이때 각 메뉴를 '상태'라 하고, 한 상태에서 다른 상태로 가는 화살표를 '전이'라 한다. 가능한 모든 전이를 화살표로 그린 그림이 바로 마르코프 체인이다. 가장 중요한 성질은 '마르코프 성질'로, 다음 상태의 확률이 오직 현재 상태에만 의존하고 그 전의 모든 단계는 무시된다는 점이다. 첫날 피자, 둘째 날 햄버거, 셋째 날 피자였더라도 넷째 날 핫도그가 나올 확률은 오직 셋째 날(피자)만 보면 된다.

두 번째 성질은 어떤 상태에서 나가는 화살표 확률을 모두 더하면 1이 된다는 것이다. 확률이 의미를 가지려면 반드시 합이 1이어야 하기 때문이다. 이제 햄버거 날에서 출발해 무작위로 열흘을 따라가 보면, 각 메뉴가 나온 횟수를 전체 일수로 나눠 상태의 확률 분포를 구할 수 있다. 다만 며칠만 보면 이 값은 들쭉날쭉하다.

관심은 '장기적으로' 무슨 일이 벌어지는가다. 이 확률들이 고정된 값으로 수렴할까. 10만 번을 시뮬레이션하면 확률은 일정한 값으로 모이는데, 이 분포를 '정상분포(stationary distribution)' 또는 평형 상태라 한다. 시간이 지나도 더는 바뀌지 않는 분포라는 뜻이다.

시뮬레이션은 직관적이지만 효율이 떨어지고 다른 정상분포가 있는지 알기 어렵다. 더 나은 방법은 선형대수다. 마르코프 체인은 방향 그래프이므로 전이 행렬 A로 표현할 수 있고, 상태 확률 분포는 행벡터 파이(π)로 나타낸다. 정상분포라면 π에 A를 곱해도 다시 π가 나와야 하므로 πA = π가 성립한다. 이는 고윳값이 1인 좌고유벡터 식과 같고, 여기에 '원소의 합이 1'이라는 조건을 더해 풀면 정상분포를 얻는다. 이 식당의 경우 햄버거 약 35%, 피자 약 21%, 핫도그 약 46%로, 앞선 시뮬레이션 결과와 거의 일치해 서로를 검증해 준다.

주요 인사이트

• 마르코프 체인의 힘은 '기억하지 않음'에 있다. 과거 전체가 아니라 현재 상태만 보면 되기 때문에, 복잡한 실제 문제를 다룰 때 계산이 훨씬 단순해진다.
• 무작위 행보의 짧은 구간은 흔들리지만 길게 보면 안정된다. 충분히 반복하면 상태 확률이 정상분포라는 고정된 값으로 수렴한다.
• 시뮬레이션과 선형대수는 같은 답에 이른다. 10만 번 무작위 행보의 결과와, 고윳값 1의 좌고유벡터를 푼 결과가 거의 일치해 서로를 뒷받침한다.
• 정상분포가 하나뿐인지도 확인할 수 있다. 고윳값이 1인 고유벡터가 여럿 존재하는지 보면 되며, 이는 마르코프 체인을 분석하는 우아한 도구가 된다.

자주 묻는 질문