Markov property

기초 개념

Stochastic process는 과거의 모든 상태가 미래에 어떻게 영향을 미치는지 모른다. Markov property는 미래는 오직 현재의 상태만 영향을 받고 과거의 모든 영향을 미치지 않는다는 것이다. 이는 다음과 같이 표현 할 수 있다.

$$ P(S_{t+1}= s' | S_t= s) = P(S_{t+1}=s' | S_0 =s_0,S_1=s_1,...S_t= s)$$

 

Stochastic process에서 나온 예시는 오직 오늘 먹은 음식이 내일 먹을 점심에 영향을 미친다면 Markov property라고 할 수 있다. 또는 과거에 먹은 점심의 영향력이 매우 작아 무시할 수 있다면 Markov property을 유지한다.

Markov property를 유지하는 상태를 Markov process(or Markov chain)이라고 한다.

 

예시

위키피디아의 예시는 다음과 같다.

빨간 공 2개와 파란 공 1개가 들어있는 상자가 있고 뽑고 다시 상자에 넣지 않으면 2번째 뽑았을 때가 과거의 모든 미래의 영향을 내포하고 있기에 Markov property가 없다고 볼 수있다. 하지만 상자에 다시 넣으면 Markov property를 가진다 할 수 있다.

일반적으로 드는 예는 브라운 운동으로 미소 입자가 무게가 적어 관성의 영향보다 충돌의 영향이 매우 커 관성을 무시할 수 있는 경우로 입자 운동의 진행 상태가 과거의 영향이 무시할 정도로 적고 현재 충돌과 같은 상황만이 영향을 줄 때 같은 상황으로 예를 든다.

 

의의

Reinforcement Learning(RL)에서 과거의 상태를 모두 계산해야 한다면 기억해야할 메모리, 계산량 등 모든 측면에서 불가능의 영역에 가깝기에 Markov property를 가지고 있어야 다음 상태을 위한 액션과 점수를 얻을 수 있다.