이번 section에서 배우는 내용을 한 마디로 말하면 "정방행렬의 거듭제곱의 극한과 그 활용" 정도가 될 것 같다. 그 중 핵심은 Markov process와 Markov chain인데, 구글의 페이지링크에도 활용되는 등 공학적으로 많은 의의를 가진다고 한다. Markov chain은 이산 확률 과정(Descrete-time Stochastic process)의 한 종류인데, 충분히 많이 반복하면 안정 상태에 도달한다. 이게 무슨 소리인지 이해하기 위해서는 먼저 행렬의 거듭제곱의 극한, 전이 행렬(transition matrix or stochastic matrix) 그리고 확률 벡터(probability vector)에 대해 이해해야 한다.
이번 Section에서 가장 먼저 나오는 정의는 행렬의 수렴과 극한이다. 더 정확히는 복소수 체의 원소들을 성분으로 가지는 정방행렬을 거듭제곱했을 때 그 수열이 수렴하는지, 수렴한다면 그 극한은 어떻게 되는지를 배운다.
정의. \(L, A_1, A_2, \dots \)가 복소수 성분을 가지는 n x p 행렬이라고 하자. 만약 모든 1<=i<=n , 1<=j<=p 에 대하여 \( \lim_{m \to \infty}(A_m)_{ij} = L_{ij} \) 이면 수열 \(A_1, A_2, \dots \) 는 n x p 행렬 L로 수렴(converge)한다고 하고, L은 수열의 극한이라고 한다.
정리 5.12.
따름정리.
정리 5.13.
정리 5.14.
책에 나온 예제를 보자. 어떤 도시와 그 근교가 있다고 하자. 인구가 도시와 근교 사이에서 움직이는데, 그 확률이 일정하다고 하자. 그렇다면 현재 인구 상태에서 n년 후 인구 상태를 알아낼 수 있지 않을까? 아래에서 소개되는 Markov chain을 이용하면 이를 구할 수 있다.
Markov Chain(마르코프 체인)이란?
마르코프 체인에 대해 이해하려면 먼저 transition matrix와 probability vector에 대해 알아야 한다. transition matrix, 혹은 stochastic matrix는 1) 0이 아닌 성분들을 가지고 2) 한 열의 성분의 합이 1인 정방행렬을 말한다. 어떤 임의의 n x n transition matrix M 에 대하여 각 행과 열은 n개의 "state(상태)"에 해당하고,
위에서 나온 도시-근교 문제는, 책의 표현에 따르면 시간이 지남에 따라 변하는 여러 가지 고정된 상태 중의 하나로 정의되는 집합의 원소를 다루는 과정을 보여주는 예시이다. 번역이 참 내가 한 거라서 거지같은데, 아무튼 이런 과정을 stochastic process 라고 부른다. 그리고 그 중에서 대상의 상태가 바뀌는 것이 오직 두 상태에만 의존한다면 이를 Markov process라고 부른다. 또한 가능한 상태의 수가 유한한 Markov process를 Markov chain이라고 한다.
또 다른 예시로, 어떤 대학에서
정리 5.20.
(a)
(b)
(c)
(d)
(e)
정의. 정리 5.20(e)에서 나온 벡터 v는 어떤 regular transition matrix A의 fixed probability vector 혹은 stationary vector라고 한다.
Absorbing Markov Chain이란?
댓글 없음:
댓글 쓰기