Markov Process (마코프 체인, 마코프 프로세스)

Markov Property

마코프 특성이란 과거 상태들과 현재 상태가 주어졌을 때 미래 상태는 과거와는 독립적이며 현재 상태에 의해 결정되는 개념입니다. 즉, 현재 상태에서 다음 상태로 전이될 확률은 오직 현재 상태에서만 의존하며 이전 상태나 이전 이벤트의 영향을 전혀 받지 않는 특성입니다. 이처럼 마코프 프로세스는 과거 상태를 반영 또는 기억하지 않기 때문에 Memoryless 프로세스입니다.

Markov Property

t-k 시점부터 t까지 여러 state를 거쳐오면서 다음 시점인 t+1에 가기 위한 확률은 바로 직전 state인 t시간의 state 확률과 같다는 것을 의미합니다.

 

Markov Process

마코프 과정은 이러한 마코프 특성 (Markov Property)를 지니는 이산 시간 확률 과정을 의미합니다. 

이산 시간은 시간을 연속적인게 아닌 상태를 각각 분리할 수 있는 시간으로 보는 것이며 t, t+1, t+2와 같이 Time Interval을 각각 바라봅니다.

마코프 과정에서는 현재 상태가 미래 상태를 예측하는데 모든 정보를 가지고 있기에 현재 상태만 반영하여 다음 state로 나아갑니다. 

Wikipedia - Markov Chain

위 그림은 Markov Chain입니다. A와 E라는 state가 존재하며 각 state에서 다른 단계로 나아가기 위해서 (전이) 확률이 화살표 위에 적혀있습니다. 여기서 특징은 각 state에서 나가는 방향을 가지고 있는 화살표들의 확률 합은 1입니다. 즉 다른 state로 이동할 확률의 합은 1을 유지한 채 state들이 이어져 있는 구조입니다.

 

State Transition Probability Matrix

마코프 과정에서 다음 상태로 나아가는 것을 변이 (Transition)라고 하며 나아갈수있는 확률을 상태 변이 확률 (State Transition Probability)라고 합니다. 이러한 정보들을 이용하여 위의 그림을 행렬 형태로 정리한 것을 State Transition Probability Matrix라고 합니다. 

현재 상태가 최좌측의 열 행렬 A와 E일 때 다음 A와 E로 갈 확률을 보기 쉽게 나타낸 것이며 예를 들어서 A가 흐림, E가 맑음일 때 내일의 날씨는 흐림과 맑음 중 어떤 날씨가 될지를 확률적으로 행렬을 이용하여 알 수 있습니다.  

 

해당 전이 행렬을 이용하여 우리는 다음 state들이 어떤 확률을 가질지 계산할수 있습니다.

예를 들어서 A가 맑음이고 E가 흐림일때, 특정일을 기준으로 80% 확률로 맑았을 때 모레가 맑은 확률은 0.8 x 0.64 + 0.2 * 0.63으로 계산될 수 있습니다.

그리고 이러한 과정을 지속적으로 하게 되어서 충분히 많은 횟수로 P가 곱해 졌을때 어느 순간에 전이 행렬이 변하지 않는 상태가 오게 됩니다. 이러한 상태를 steady state라고 부르며 확률이 직전 상태와 동일하게 수렴하게 되며 이것을 Stationary Distribution이라고 부릅니다.

 

Example

주기적으로 커피를 구매하는 사람이 있을때 아이스 아메리카노 (Ice Americano, IA)를 좋아하는 사람이 있으며 따뜻한 아메리카노 (Warm Americano, WA)를 좋아하는 사람이 있다고 가정하겠습니다. 이때 IA를 좋아하는 사람은 10000명이었으며 WA를 좋아하는 사람은 8000명이라고 해보겠습니다.

이때 확률 전이행렬은 위와 같다고 하겠습니다. 즉 A는 IA이며 E는 WA라고 하겠습니다.

현재/다음상태	A (IA)	E (WA)
A (IA)	0.6	0.4
E (WA)	0.7	0.3

그렇다면 하루가 지나면 아래와 같이 계산이 될 것입니다. 

그렇다면 10일이 지나면 몇명이 IA 또는 WA에 남게 되는지 보겠습니다.

 

coffee_pop = np.array([[0,0],[10000, 8000]])
P = np.array([[0.6, 0.4], [0.7, 0.3]])
n = 10
x = range(0,n)
for i in range(1,n):
    tmp = coffee_pop[i] @ P
    print(tmp)
    coffee_pop = np.append(coffee_pop, [tmp], axis=0)

IA = [i[0] for i in coffee_pop]
IA = np.delete(IA, [0])
WA = [i[1] for i in coffee_pop]
WA = np.delete(WA, [0])
plt.plot(x, IA, label='Ice Americano')
plt.plot(x, WA, label='Warm Americano')
plt.legend()
plt.savefig('compare.png',dpi = 300)

수렴값은 IA같은 경우 11454.54이며, WA는 6545.45입니다. 초기 10000명보다 IA 쪽으로 1450명 정도 증가되었으며 WA는 8000명에서 줄은 결과를 볼 수 있었습니다.