마르코프 체인이란
을 만족하는 확률변수들의 수열들을 말한다.
위에 식은 MDP(Markov Decision Process)에서 전이 확률(transition probability)을 나타낸다.
Markov definition
마르코프 체인의 정의는 마르코프 성질을 가진 이산 확률과정을 말한다.
A stochastic process, it is a discrete time Markov Chains (DTMC) i,j ∈ Ω
- Ω is discrete
- Indexed by discrete sequence of times
- Countable number of states / [ Ω ⊆ Ζ ] / Omega subset integers
Markov Property
마르코프의 성질은 '특정 상태의 확률은 오직 과거의 상태에 의존한다'라는 것이다.
The probability of Xn+1, given all past values of {Xn} is equal to the probability of Xn+1 given only Xn
즉, The probability of future event depends only on the current value not on past values.
미래의 확률은 과거의 가치에 상관 없이 오직 현재의 가치에 의해서 결정된다.
Markov Chain often assume the process is time-homogeneous
P(Xn+1 = j | Xn = i) is the same for all times n. <- this is called the one-step transition probability.
- Pij = P(Xn+1=j | Xn = i) , i is current state j is state of system 1 step later.
쉽게 설명을 하자면, 오늘 비가 왔으니 내일 비가 올지 안올지 확률적으로 표현 할 수가 있는데
이처럼 연속적인 현상을 단순히 표현할 때 마르코프 체인을 가정하여 사용 가능하다는 것
Three important properties of a Markov Chain:
1. Transient Distribution: Marginal distin of Xn, or fixed n
2. Occupancy Times: Expected amount of time the DTMC spends in a given state
3. Limiting Behavior: what happens as t -> ∞
WHY? 사용하는가?
- we can represent a lot of simple stochastic system as MCs.
ex) biology, inventory system, queueing systems, computer and telecomm, economics, physics, etc.
- DTMCs are often the building block for more complex stochastic models.
종종 단순한 모델이 강력한 효과를 발휘하기 때문에, 실제로 예측을 하려면 엄청나게 복잡한 변수들과
모델링을 거쳐서 엄선해야하는데, 마르코프 체인을 사용함으로써 기회 비용을 크게 줄이면서 이에 근접한
효과를 낼 수 있기 때문
마르코프 체인 계산 방법
마르코프 행렬은 전이행렬을 가지고 있는데
전이행렬의 각 상태의 확률은 일반적으로 행을 취합니다
X(t+1) = P *X(t)
X(0)
X(1) = P*X(0)
X(2) = P*X(1) = P * P * X(0) = P^2 * X(0)
X(t) = P^t * X(0)
X(t) <- 상태행렬 : 모든 성분의 합이 1
P <- 전이행렬(추이 행렬)
마르코프 체인의 성질
전이행렬을 계속 곱해주다 보면 변하지 않는 상태가 오는데 (수렴한다)
시간이 지나면 확률의 일정한 값에 수렴해가고 변하지 않는다. 안정상태 (Steady state)
상태행렬은 어떤 행렬 X로 수렴한다
이 행렬 X는 P를 곱해도 변하지 않는다
즉, PX = X
X 를 안전상태의 확률행렬이라 한다
How to get X?
1. 전이행렬 P를 계속 곱해주기
2. X(t) = p^t * X(0), 대각화로 P^t 계산 후에 X(t)를 구하기 ----- 대각화 공부하기
3. PX = X, X는 연립일차방정식 (P-1)X = 0의 해이다.
마르코프 체인 사용 예시
example 1 : forcasting the Weather
example 2 : Random Walk
example 3 : A Gambler
구글 페이지 랭크 알고리즘 - 마지막에 머무는 페이지의 퍼센트를 확인해서 랭크로 표시.