Markov chain

qkrdbwls191·2022년 3월 22일
0

마르코프 체인(Markov Chain)에 관해 알아보는 시간을 갖겠습니다.

마르코프 체인이란?

정의

마르코프 체인을 설명해주는 여러 매체들에서는 주로 '날씨'를 이용해서 마르코프 체인을 설명합니다.
예를 들어 오늘의 날씨가 비가 내리는 날씨이고, 내일 날씨가 비가 내릴지 내리지 않을지 확률로 나타낼 수 있습니다.
이를 좀 어렵게 말하면

마르코프 체인'마르코프 성질'을 가진 '이산시간 확률과정' 입니다.

각각을 풀어서 설명하면

마르코프 성질 - 과거와 현재 상태가 주어졌을 때의 미래 상태의 조건부 확률 분포가 과거 상태와는 독립적으로 현재 상태에 의해서만 결정됨

이산시간 확률과정 - 이산적인 시간의 변화에 따라 확률이 변화하는 과정

이라고 설명될 수 있습니다.

1차 마르코프 체인의 그림을 보시면 위의 개념들이 좀 더 쉽게 이해가 되실겁니다. 즉 미래의 상태를 결정하는 요소가 오로지 현재의 상태라는 개념입니다(글에서는 1차 마르코프 체인만 다루고 있습니다!).

전이(transition)와 상태전이확률(State transition probability)

그러면 어떤 상태에서 다음 단계의 상태로 변화하는 것(전이, transition)에 대한 확률도 정의할 수 있는데, 이를 상태전이확률(State transition probability)이라고 합니다.

상태전이확률은 아래와 같은 수식으로 나타낼 수 있습니다.

위 식은 상태 Vi에서 Vj로 이동할 확률과 확률의 기본적인 정의에 대해 나타내고 있습니다.

또한 상태 A,B,C가 있고 각각의 상태 전이 확률이 정의되어 있다고 가정할 때, 상태 전이도(State transition diagram)도 나타낼 수 있습니다. 아래의 그림입니다.

이 그림을 바탕으로 전이확률의 행렬을 나타낼 수 있는데

이와 같은 전이확률행렬로 표현할 수 있습니다.

안정상태(Steady state)와 정적분포(Stationary distribution)

현재 상태를 알고 있고 전이확률행렬을 알고 있다면, 다음 단계의 상태도 알 수 있을 것입니다. 마찬가지로 다음 단계의 상태를 구했고 전이확률행렬은 이미 알고 있으니 그 다음 단계의 상태도 알 수 있을 것입니다. 이를 식으로 나타내면

Pij는 상태 i에서 j로 가는 상태전이확률이고 n의 의미는 n번째 상태라고 생각하시면 됩니다.
n이 어마어마한 숫자로 커지게 되면

다음과 같은 수식이 성립하게 되는데 이때 π는 각 상태의 확률분포이고 P는 전이행렬입니다. 이 상태에서 다음 상태를 알기 위해 전이행렬을 더 곱한다해도 같은 값을 유지하는데, 이를 안정 상태(Steady state) 이때의 확률분포를 정적분포(Stationary distribution)이라 합니다.

참고자료 및 이미지 출처

"마르코프 체인에 관하여" - https://www.puzzledata.com/blog190423/
"[강화학습]마코프 프로세스(=마코프 체인) 제대로 이해하기" - https://bskyvision.com/573
"마르코프 연쇄" - https://ko.wikipedia.org/wiki/%EB%A7%88%EB%A5%B4%EC%BD%94%ED%94%84_%EC%97%B0%EC%87%84
"Markov Chain" - https://sites.google.com/site/machlearnwiki/RBM/markov-chain
"Markov Chains: Stationary Distribution" - https://towardsdatascience.com/markov-chains-stationary-distribution-bedd67140112
"마르코프 체인 | 고급수학2 | 행렬 세특" - https://www.youtube.com/watch?v=Yh62wN2kMkA

0개의 댓글