[Algorithms] Markov Chain(마코프 연쇄)

Table of Contents

• Introduction

• Markov Chain(마코프 연쇄)이란?

• Markov Chain의 예시

• Reference

 

Introduction

 Markov Chain(마코프 연쇄)은 모든 사건의 결과가 이전 사건의 결과에 영향을 받는 확률론적 모형이다. Markov Process(마코프 과정)으로도 알려져 있으며, 러시아 수학자인 마르코프(Andrei A. Markov, 1856 ~ 1922)가 도입한 확률 모형입니다.

 Markov Chain은 현실에서 통계 모형으로 많은 곳에 활용되고 있으며, 모빌리티 분야의 크루즈 컨트롤에서 활용하고 있으며 공항에서 도착한 고객들의 줄이나 환율 그리고 동물 개체수 등에서 사용하고 있다.

 또한, 확률적 시뮬레이션 방법론 중 MCMC(Markov Chain Monte Carlo: Markov Chain에서 샘플링을 하기 위해 Monte Carlo Method를 사용하여 확률 분포가 반영된 데이터를 샘플링 하는 것)의 기초이기도 하다.

 

 

 

Markov Chain(마코프 연쇄)이란?

Markov Process(마코프 과정)는 마코프 특성(Markov Property)을 만족하는 확률 과정(Stochastic Process)이다. 여기서 마코프 특성이란, 미래의 결과는 과거의 상태에 관계 없이 오롯이 현재 상태에 의해 결정된다는 것이다. 이 특성을 이해하기 위해서는 조금 더 자세한 내용을 이해할 필요가 있다.

Markov Chain의 유형에는 상태 공간(State space)과 시간(연속형, 이산형)에 따라 상세하게 구분하고 있으나, 이해의 편의상 이산 확률 과정을 고려하고자 한다.

 

이산 확률 과정(Discrete-time Stochastic Process)

이때 확률 변수 X가 아래와 같은 식을 만족한 경우 Markov Chain(마코프 연쇄)라고 한다. 이 관계식은 0번째 시점부터 t번째 시점까지의 모든 사건이 존재할 경우, t번째 사건은 t-1번째 사전에만 영향을 받는다는 뜻이다. 즉, 한 상태에서 다른 상태로 전이(Transition)을 하는 동안 과거의모든 전이 확률(Transition Probability)가 필요한 것이 아닌 바로 직전의 확률로 추정할 수 있다.

 

상태 공간(Finite Discrete State Space)

> 상태를 나타내는 공간

   ex) 날씨 상태를 예시로 했을 때  맑음 = 1, 비 = 2라면, State Space = {1, 2}로 정의

 

변이 확률 행렬(Transition Probability Matrix)

> 특정 시점 t의 i번째 상태 공간에서 t+1의 j번째 상태 공간으로 변화를 나타내는 확률

    ex) 오늘 비가 올 때 내일 비가 올 확률 = P(비|비) = P(x^(t+1) = 2|x^(t) = 2)

 

비유동적 확률(Stationary Probability)

변이 확률 함수(Transition Probability Matrix)에 의해 내일의 날씨를 예측 할 수있다. 또한, 내일의 날씨로 모레의 날씨 역시 예측이 가능하다. 이런 과정이 무한히 반복된다면 어느 날의 날씨 확률 분포가 전날과 같아 지는 때가 있다. 이를 Stationary Probability라고 한다.

 

Markov Chain의 예시

Markov Chain을 쉽게 이해하기 위해 날씨에 관한 확률 문제를 소개하곤 한다. 오늘 비가 왔을때 내일 비가 올 확률이 0.7이고, 오늘 맑았다면 내일 비가 올 확률은 0.4이라고 가정하자.

이때, 상태 공간은

변이 확률 함수는 

Reference

1. https://brilliant.org/wiki/markov-chains/ Retrieved April 19, 2020