[25-1 Winter Session 2] Markov Chains for the Long Term

ESC·2025년 6월 2일

25_Winter Stochastic Process

2025-Winter

목록 보기

2/7

3 Markov Chains for the Long Term

1. Graph

1. Directed vs Undirected

Directed graph는 edge가 방향을 가지는 graph이고, Undirected graph는 edge가 방향을 갖지 않는 그래프이다. 쉽게 비교하면 아래와 같이 node를 연결하는 선이 화살표로 표시되면 directed graph, 방향성이 없는 선으로 표시되면 undirected graph로 구분할 수 있다.

2. Adjacency Matrix

Adjacency Matrix의 i행 j열 원소 $A_{ij}$ 는 node i에서 node j로 가는 edge가 있으면 1, 없으면 0으로 나타난다. 이를 바탕으로 아래의 directed graph를 adjacency matrix로 나타내면 다음과 같다.

Undirected graph의 경우, 선에 방향성이 없으므로 두 node i와 j가 연결되어 있을 때 $A_{ij}$ 와 $A_{ji}$ 가 모두 1로 표기되고, 연결되어있지 않다면 모두 0으로 표기된다. 그러므로 undirected graph는 symmetric matrix가 되는 성질을 가진다.

Adjacency Matrix를 n번 거듭제곱한 행렬의 i행 j열 원소 $A_{ij}^n$ 는 n번 이동을 통해 node i에서 출발하여 node j로 도달하는 경우의 수, 혹은 길이가 n인 path의 수로 해석할 수 있다.

$A_{ij}^n$ : the number of connected nodes of i to j with length n

3. Markov Chains

State Space(Node의 집합)을 $\Omega = \{1, …, N\}$ 라고 두자.

위에서 언급한 adjacency matrix에서 확률을 고려하여 원소 $A_{ij}$ 를 node i에서 node j로 갈 확률 $p_{ij}$ 로 둔 행렬을 transition matrix로 볼 수 있다. 즉, transition matrix는 weighted adjacency matrix가 된다.

이러한 adjacency matrix를 n번 거듭제곱한 행렬의 i행 j열 원소 $A_{ij}^n$ 는 n번 이동을 통해 node i에서 출발하여 node j로 도달하는 확률(가중합)으로 해석할 수 있다.

$A_{ij}^n$ : the weighted sum of connected nodes of i to j with length n

3.1 Limiting Distribution

1. Limiting Distribution

1. Definition

정리하면 Markov chain의 limiting distribution는 위와 같은 성질을 가지는 확률분포 $\lambda$ 를 의미한다. 즉, transition을 무한히 반복했을 때 state j에 수렴할 확률(long-term probability)를 나타낸다.

2. Stochastic Matrix

Stochastic Matrix( $\Lambda$ )는 n이 무한으로 갈 때transition matrix $P$ 를 n번 거듭제곱한 matrix다. 따라서 Stochastic Matrix의 모든 행이 확률분포 $\lambda$ 가 됨을 유추할 수 있다.

이를 정리해서 수식으로 나타내면 다음과 같다.

3. Example (Two-state Markov chain)

Two-state Markov chain은 두개의 node로 구성된 directed graph를 다루는 문제다.

위 그림과 같이 directed node가 나타날 경우, stochastic matrix 를 구해보면 다음과 같다.

이를 바탕으로 limiting distribution $\lambda$ 를 구해보면, n을 무한대로 보내 수렴하는 값을 관찰하면 된다. n이 무한대로 갈 경우, $(1-p-q)^n$ 이 0으로 수렴하고 limiting distribution $\lambda$ 는 아래와 같이 나타난다.

이때, 위에서 언급한 바와 같이 stochastic matrix의 모든 행이 limiting distribution으로 나타남을 확인할 수 있다.

3.2 Stationary Distribution

1. Stationary Distribution (정상분포)

1. Definition

$\pi P = \pi$ 를 만족하는 확률분포 $\pi$ 를 stationary distribution이라 한다.

3.1에서 언급한 limiting distribution의 정의에 따라 $\lambda P=\lambda$ 를 만족하므로 limiting distribution은 stationary distribution이다. 하지만 역은 성립하지 않는다.

2. Regular Markov Chains

1. Definition

어떤 n에 대해 transition matrix $P$ 의 n 거듭제곱이 양의 값을 가질 때 이러한 P를 regular하다고 정의한다.

$P^n>0\ for \ some\ n \rightarrow\ P:Regular\ Transition\ Matrix$

2. Limit Theorem for Regular Markov chains

Regular transition matrix $P$ 를 갖는 markov chain이 유일한 양의 정상분포가 되는 limiting distribution을 갖는다는 것은 아래의 식을 만족하는 유일한 양의 벡터 $\pi$ 가 존재함을 의미한다.

반면 stochastic matrix가 regular하지 않은 경우, $P^n$ 에서 0이 나타나는 위치에 $P^{n+1}$ 도 동일하게 0이 나타난다.

또한, stationary distribution을 찾기 위해서는 P가 regular할 때 $\pi P=\pi$ 를 풀어 구할 수 있다.

3. Example (Two-state Markov chain)

3.1에서와 마찬가지로 two-state markov chain의 문제를 해결해보자. 아래와 같이 regular한 P가 주어졌을 때 stationary distribution $\pi$ 를 구하기 위해서는 $\pi P=\pi$ 를 풀어야 한다.

위 식에 대해 $\pi P=\pi$ 를 세워주면

로 나타낼 수 있고 이를 풀면 아래와 같이 stationary distribution이 구해진다.

3.3 Can you Find the Way to State a?

1. Communication Class

Communication이란 Equivalence relation으로, 이는 Reflexive, Symmetric, Transitive의 세가지 성질을 만족하는 관계를 나타낸다.

j is accessible from i는 $P_{ij}^n>0$ 인 n이 존재함을 의미한다

정의를 바탕으로 아래 graph의 communication class를 찾으면 {1}, {2}, {3,4}로 묶을 수 있다

마찬가지로 위의 정의를 바탕으로 아래 graph의 communication class를 찾으면 {a,b,c,d,e,f}, {g}가 된다.

2. Irreducibility (기약성)

기약성은 모든 state가 서로 communicate하는(communication class가 하나인) 경우를 의미한다. 이를 바탕으로 보면 위의 두가지 경우는 모두 두개 이상의 communication class를 가지므로 irreducible하지 않다

3. Recurrent and Transient States

1. Definition

Recurrent state란 최종적으로 자기 자신에게 돌아오는 경우를, transient state란 자기 자신에게 돌아오는 길이 없는 경우를 의미한다

다음과 같이 $f_j$ 를 상태 j에서 시작해서 j로 돌아올 확률로 정의하면 $f_j$ 가 1일 때 Markov chain은 recurrent하고 $f_j<1$ 일 때 Markov chain은 transient하다.

다음과 같이

수식으로 나타내면 아래와 같다

3. Theorem

동일한 communication class에 속한 요소는 모두 recurrent하거나 모두 transient하다.

(Corollary) 유한한 irreducible markov chain에 대해 모든 요소는 recurrent하다.

3.4 Irreducible Markov Chains

💡 Finite irreducible markov chains의 stationary distribution $\pi$는 어떤 특징을 가지고 있을까? $j$ 상태에 도달하기까지 필요한 step의 기댓값과 $\pi_j$를 연결지어 살펴보자.

1. Limit Theorem for Finite Irreducible Markov Chains

*️⃣ **stationary distribution (정상 분포)**

$X_0, X_1, \cdots$ 가 transition matrix $\bm P$ 를 가지는 Markov chain이라고 하자. Stationary distribution은 $\pi$ 의 확률 분포이고, 다음을 만족한다.

\pi = \pi \bm P

즉, $\pi_j=\sum_i \pi_i\bm P_{ij}, \text{ for all } i$ 이다.

$X_0,X_1,\cdots$ 이 finite irreducible Markov chain이라고 가정해보자. 각각의 모든 state j에 대해서, 다음은 $j$ 로 돌아오는 데까지 걸리는 시간의 기댓값이다.

\mu_j = \text{E}(T_j|X_0=j), \ T_j = \min \{ n >0:X_n=j\}

이때, $\mu_j$ 가 finite하다면, unique하고 positive한 stationary distribution $\pi$ 가 존재하며, 모든 $j$ 에 대하여 $\pi _j = \frac{1}{\mu_j}$ 이다. 직관적으로, $\mu_j$ 는 state $j$ 로 되돌아오는 평균 시간이기 때문에, $\mu_j$ step 마다 한 번씩 state $j$ 를 방문한다면, 전체 방문 중에서 state $j$ 를 방문하는 비율은 $\frac 1 {\mu_j}$ 이다. 또한 모든 states $j$ 에 대하여 $\pi_j = \lim_{n\to \infin}\frac 1 n \sum_{m=0}^{n-1}P_{ij}^m$ 이다.

➡️ Irreducibility는 stationary distribution의 존재와 uniqueness를 보장하는 핵심 조건

Example 1 (Earthquake recurrences)

$M_2, M_3,M_4,M_5$ 가 지진 강도를 나타내는 리히터 규모라고 하자. 이때 Markov transition matrix와 stationary distribution은 다음과 같이 주어져있다.

$M_5$ 강도의 지진이 일어났을 때, 또 다른 $M_5$ 강도의 지진이 일어나기까지 얼마나 걸릴까? → $1/\pi_{M_5}=1/0.003=333$

Example 2

*️⃣ $\text{E}(T_j|X_0=j)$를 찾는 방법

$\pi_j$ 의 역수를 취하기 ( $\because\pi_j=\frac 1 {\mu_j}$ )
Law of Total Expectation 활용하기

$e_x=\text{E}(T_a|X_0=x), \text{ for x = a, b, c}$ 라고 하자. 우리는 $a, b, c$ 에서 시작해서 state $a$ 로 가는 기댓값을 구하고 싶다.

$e_a= 1+e_b$
- $a$ 에서는 $b$ 로 갈 수밖에 없음(한 번 이동)
- $b$ 에서 시작해서 $a$ 가 될 때까지의 기댓값
$e_b= \frac 1 2 +\frac 1 2(1+e_c)$
- $\frac 12$ 의 확률로 $a$ 직행
- 또는 $\frac 1 2$ 의 확률로 $c$ 로 이동(한 번 이동) 후, $c$ 에서 시작해서 $a$ 가 될 때까지의 기댓값
$e_c=\frac 1 3 + \frac 1 3(1+e_b) + \frac 1 3(1+e_c)$
- $\frac 1 3$ 의 확률로 $a$ 직행
- 또는 $\frac 1 3$ 의 확률로 $b$ 로 이동(한 번 이동) 후, $b$ 에서 시작해서 $a$ 가 될 때까지의 기댓값
- 또는 $\frac 1 3$ 의 확률로 $c$ 로 이동(한 번 이동) 후, $c$ 에서 시작해서 $a$ 가 될 때까지의 기댓값

⇒ $e_c=\frac 8 3, \ e_b = \frac 73, \ e_a=\frac {10} 3$

R Code

#Simulating an Expected Return Time

P = #전이 확률 행렬 
init = #초기 상태 설정
states = #상태의 이름 정의
markov(init, P, n, states) #Markov chain의 경로를 시뮬레이션, 
#여기서 n은 한 시뮬레이션 안의 step 수

trials = #전체 시뮬레이션 횟수 할당
simlist = numeric(trials) #각 시뮬레이션에서 복귀 시간을 저장할 빈 벡터

for (i in 1:trials) {
	path = markov(init, P, n, states)
		# 생성된 경로에서 상태 a가 두 번째로 나타나는 위치를 찾기
		# 첫 a에서 다음 a(= 두 번째 a)로의 복귀 시간을 구하는 것이 목표이기 때문 
	returntime = which(path == "a")[2] - 1 # index는 1부터 시작, 시간은 0부터 시작
	simlist[i] = returntime }
	
mean(simlist)

3.5 Periodicity

1. Period

transition matrix $\bm P$ 를 가지는 Markov chain에서, state $i$ 의 period를 $d(i)$ 라고 하자. 이때 period는 state $i$ 로 돌아올 수 있는 모든 가능한 단계 수의 최대공약수(GCD)이다.

d(i) = \text {gcd} \{n>0: P_{ii}^n >0\}

$d(i) =1$ 이면, state $i$ 는 비주기적(aperiodic)하다.
state $i$ 로 돌아올 수 없다면, 즉, 모든 $n$ 에 대해 $\bm P_{ii}^n=0$ 이라면 $d(i)=\infin$ 이라고 정의한다.

➡️ state $i$ 에서 다시 $i$ 로 돌아오기 위해서는 $d(i)$ 의 배수 만큼의 step을 거쳐야 한다.

2. Periodicity is a Class Property

같은 communication class의 states들은 모두 같은 period(주기)를 가진다.

proof

같은 communication class에 있는 $i$ 와 $j$ 를 가정하자.
$\begin{aligned} &\exists\,r, s \in \mathbb{N}\ \textnormal{such that}\ \bm P_{ij}^r > 0,\ \bm P_{ji}^s > 0 \quad (\textnormal{because } i, j \textnormal{ communicate})\\ &\implies\ \bm P_{ij}^r \,\bm P_{ji}^s > 0,\\ &\implies\ \bm P_{ii}^{\,r+s} \;=\; \sum_k \bm P_{ik}^r\,\bm P_{ki}^s \;\ge\; \bm P_{ij}^r\,\bm P_{ji}^s \;>\; 0. \end{aligned}$
✅ $r$ 번 만에 $i \rightarrow j$ 로 가고, 거기서 $s$ 번 만에 $j \rightarrow i$ 로 돌아온다면, 전체 $r+s$ 단계 후에, $i$ 에서 $i$ 로 돌아올 수 있게 된다. 그리고 모든 $k$ 에 대한 확률값의 합과 그것의 일부인 $j$ 에 댄 확률값은 위와 같은 부등식 관계가 성립한다.

⇒ $r+s$ 는 $d(i)$ 를 약수로 가진다.

다음으로, $\bm P_{jj}^n>0$ 을 만족하는 $n$ 이 존재한다고 가정하자.
$\bm P_{ii}^{r+s+n} \ge \bm P_{ij}^r\bm P_{jj}^n \bm P_{ji}^s >0$
✅ $r$ 번 만에 $i\rightarrow j$ 로 가고, 거기서 $n$ 번 만에 $j\rightarrow j$ 로 돌아오고, $s$ 번 만에 $j\rightarrow i$ 로 돌아온다면, 전체 $r+n+s$ 단계 후에 $i$ 에서 $i$ 로 돌아올 수 있게 된다.

⇒ $r+n+s$ 는 $d(i)$ 를 약수로 가진다.

$d(i)$ 는 $r+s$ 와 $r+s+n$ 모두 나눌 수 있으므로, $n$ 도 나눌 수 있어야 한다. 그러므로, $d(i)$ 는 $\{n>0:\bm P_{jj}^n>0\}$ 집합의 공약수이다. 그런데 이때 위의 period 정의에 따라, 동일한 집합의 “최대” 공약수는 $d(j)$ 이다. 따라서, $d(i)\le d(j)$ 이다. $i,j$ 를 뒤바꿔서 같은 논리를 적용하면 $d(j) \le d(i)$ 도 성립하므로 $d(i)=d(j)$ 이다.

Example

communication class와 주기는 다음과 같다.

$\{a\} : 1$
$\{b, c, d,e,f\} : 2$
$\{g\}=+\infin$
$\{h, i\}= 2$
$\{j,k,l\}=1$

3. Periodic, Aperiodic Markov Chain

periodic : irreducible & 모든 states가 1보다 큰 period(주기)를 가지는 경우
aperiodic : irreducible & 모든 states가 1인 period(주기)를 가지는 경우

3.6 Ergodic Markov Chains

1. Ergodic Markov Chains

Markov chain이 1) irreducible, 2) aperiodic, 3) 모든 state들이 유한한 횟수 안에 돌아올 수 있을 때(→ finite) Ergodic Markov Chain이라고 부른다.

2. Fundamental Limit Theorem for Ergodic Markov Chains

$X_0, X_1,\cdots$ 를 Ergodic Markov chain이라고 하자. unique, positive stationary distribution $\pi$ 가 존재한다. 이때 $\pi$ 는 chain의 극한 분포이다. 즉, 다음을 만족한다.

\pi_j = \lim_{n\rightarrow \infin}\bm P_{ij}^n \text{ for all } i, j

Example 1

$\bm \pi= (x_1,x_2,\cdots,x_n)$ 를 stationary distribution이라고 하자. 이때, $x_1=1$ 이다. 정의와 위의 transition matrix에 의해 다음과 같이 정리할 수 있다.

x_j=\sum_{i=1}^n x_i \bm P_{ij}=x_{j-1}\bm P_{j-1}, \text { for } j =1,2,\cdots, n

$x_2=x_1=1$ 이며, 다음과 같이 $x_j$ 를 정리할 수 있다.

\begin{aligned} x_j &= x_{j-1}\left(\frac{j-2}{j-1}\right) = x_{j-2}\left(\frac{j-3}{j-2}\right)\left(\frac{j-2}{j-1}\right)\\ &= x_{j-2}\left(\frac{j-3}{j-1}\right) = \cdots = x_2\left(\frac{1}{j-1}\right) = \frac{1}{j-1},\\ &\quad \textnormal{for } j = 3, \dots, n. \end{aligned}

그러므로, stationary distribution은 다음과 같다. (전체 확률의 합이 1이 되도록 정리하면 도출 가능)

\pi_j =\begin{cases} \frac 1 c , & \text{for } j =1 \\ \frac 1 {c(j-1)} , & \text{for } j =2,\cdots, n \end{cases}\\ \text{ where } c= 1+\sum_{k=1}^{n-1} 1/k

Example 2 (PageRank)

💡 time reversibility에 대해 알아보자

Def)\,\,Time\,\,Reversibility \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\\Marcov\,\,Chain\,\,with\,\,stationary \,\,distribution\,\,\pi\,\,is\,\,reversible\,\,\\ if\,\,MC\,\,satisfies\,\,\,\pi_{i}P_{ij}=\pi_jP_{ji} \,\, \forall i,j

Time reversible의 의미:

충분히 큰 n에 대해 stationary distribution에 도달했을 때 체인의 방향을 거꾸로 돌려도 확률이 동일하다는 의미

조금 더 general하게 본다면

P(X_0=i_0,...,X_n=i_n)=P(X_0=i_n,...,X_n=i_0)

pf) \\ P(X_0=i_0,...,X_n=i_n)=P(X_n=i_n|X_0=i_0,...,X{n-1}=i_{n-1})P(X_0=i_0,...,X_{n-1}=i_{n-1}) \\ = P(X_n=i_n|X_{n-1}=i_{n-1})P(X_{n-1}=i_{n-1}|X_0=i_0,...,X_{n-2}=i_{n-2})P(X_0=i_0,...,X_{n-2}=i_{n-2}) \\ =P(X_n=i_n|X_{n-1})P(X_{n-1}=i_{n-1}|X_{n-2}=i_{n-2})...P(X_1=i_1|X_{0}=i_0)P(X_0=i_0) \\ = P(X_n=i_0|X_{n-1}=i_{1})P(X_{n-1}=i_{1}|X_0=i_n,...,X_{n-2}=i_{2})P(X_0=i_n,...,X_{n-2}=i_{2}) \\

만약 stationary distribution이 uniform하다면 P_ij=P_ji이므로 대칭 행렬이 됨

앞서 봤던 것처럼 모든 MC는 directed Graph에서의 random walk로 표현가능

하지만 reversible하다면 양쪽 edge가 모두 가능해야 하므로 undirected, weighted graph로 표현 가능

각 노드의 확률 분포의 존재를 Time-Reversible이 보장해줌

reversible일\,\, 때 \,\, pi_{i}P_{ij}=\pi_jP_{ji}를 \,\, 만족하는 \,\, \pi가\,\, stationary \,\, distribution

💡 absorbing chain에 대해 알아보자

Def) Absorbing \,\,Chain \\ State\,\,i\,\,is\,\,an\,\,absorbing\,\,state\,\,if\,\,P_{ii}=1.\,\, \\ A \,\,Markov\,\,Chain\,\,is\,\,called\,\,an\,\,absorbing\,\,chain\,\,if\,\,it\,\,has\,\,at\,\,least\,\,one\,\,absorbing\,\,state

absorbing의 의미)

absorbing state에 도달만 한다면 평생 그 state에 머물기 때문

absorbing state는 시간이 지나도 같은 곳에 머무르므로 recurrent

absorbing state와 연결된 state들은 transient

그 외는 둘 다 가능

가정: absorbing이 아닌 상태는 전부 transient

MC를 state를 absorbing state와 그렇지 않은 state(Q)로 나누어 transition matrix로 나타내면

위과 같이 나타낼 수 있다.

time이 n일 때의 확률 분포는 위와 같이 나타낼 수 있다.

여기서 Q는 시간이 충분이 많이 지나면 벗어나게 되므로 n이 충분히 크면 각 component에 값이 0으로 수렴한다. 즉,

\lim_{n \to \infty}\,Q^n=0

lemma) \sum_{n \in N} Q^{n-1} = (I-Q)^{-1} \\pf)\,\,\,\, (I+,..,+Q^{n-1})(I-Q)=I-Q^n \\ as\,\,{n \to \infty} \,\,\,\, Q^n\to 0 \,\, thus \sum_{n \in N} Q^{n-1} \to (I-Q)^{-1}

즉 n이 충분히 클 때 P^n은 위와 같다.

ps.

F=(I-Q)^-1은 Fundmental Matrix이다. 어떤 정보를 담고 있길래 Fundmental이라 불릴까?

F_{ij}: i에서 \,\, 출발했을\,\, 때,\,\, j에 \,\,방문하는\,\, 총\,\, 횟수의\,\, 기대값

(FR)_{ij}: 언젠가 \,\,j에\,\, 흡수될 \,\,확률

F_i: i에서\,\, 출발했을\,\, 떄,\,\, 어딘가로\,\, 흡수될\,\, 때까지 \,\,소요된\,\, 횟수의 \,\,기댓값

Strong Markov Propert

Strong\,\ Markov\,\ Property: \\ Let X_0,X_1,.. be\,\,a\,\,Markov\,\,chain\,\,with\,\,transition\,\,matrix\,\,P.Let\,\,S\,\,be\,\,a\,\,stopping\,\,time.\,\, \\Then,\,\,X_S,X_{S+1},...is\,\,a\,\,Markov\,\,chain\,\,with\,\,transition\,\,matrix\,\,P

증명 p135-136

여기서 stopping time S란?

-Random Variable

\,\,\,\,present\,\, time이 \,\, t이고 \,\, X_0,...,X_s를\,\, 알 \,\,때\\\,\,t시점에서\,\,event\{S=s\}인지\,\, 아닌지\,\,X_0,...,X_s를 가지고 판단될 수 있는 것

First hitting time: S를 ‘특정 State i에 처음으로 도달하는 시점’으로 정의

e.g. \,\,T_i=min\{{n \geq}0 :X_n=i \}

처음으로 비가 온 날 T_r부터의 과정 X_Tr, X_Tr+1 도 동일한 MC

First return time: X_0=i일 때, S를 ‘i에 처음으로 되돌아오는 시점’으로 정의

e.g.)\,\, T^+_i=min\{n\geq1:X_n=i\}

0번째 날에 비가 왔다는 전제가 추가된 것 i에서 시작해서 i로 되돌아 왔으므로 이를 MC regenerate itself라 함

ps) last visit to state i 를 RV로 정의 한다면 이는 stopping time일까?

X_0,…,X_s만으로 결정되지 않기 때문에 stopping time이 아니다.

STRONG의 의미는 무엇일까?

고정된 시점 n부터 관찰한 X_n, X_n+1,…이 같은 전이행렬 P를 가지는 MC임은 자명

STRONG이 주장하는 것은 Random한 시간 t에 대해서도 X_t, X_t+1,…도 같은 전이행렬 P를 가지는 MC라는 것

즉 random한 시간에서도 성립하므로 ‘강한’ 성질

ESC

@Yonsei University

이전 포스트

[25-1 Winter Session 1] Introduction + Markov Chain: First Step

다음 포스트

[25-1 Winter Session 2] Markov Chains for the Long Term

2025-Winter

3 Markov Chains for the Long Term

1. Graph

1. Directed vs Undirected

2. Adjacency Matrix

3. Markov Chains

3.1 Limiting Distribution

1. Limiting Distribution

1. Definition

2. Stochastic Matrix

3. Example (Two-state Markov chain)

3.2 Stationary Distribution

1. Stationary Distribution (정상분포)

1. Definition

2. Regular Markov Chains

1. Definition

2. Limit Theorem for Regular Markov chains

3. Example (Two-state Markov chain)

3.3 Can you Find the Way to State a?

1. Communication Class

2. Irreducibility (기약성)

3. Recurrent and Transient States

1. Definition

3. Theorem

3.4 Irreducible Markov Chains

1. Limit Theorem for Finite Irreducible Markov Chains

Example 1 (Earthquake recurrences)

Example 2

R Code

3.5 Periodicity

1. Period

2. Periodicity is a Class Property

Example

3. Periodic, Aperiodic Markov Chain

3.6 Ergodic Markov Chains

1. Ergodic Markov Chains

2. Fundamental Limit Theorem for Ergodic Markov Chains

Example 1

Example 2 (PageRank)

Time reversible의 의미:

[25-1 Winter Session 1] Introduction + Markov Chain: First Step

[25-1 Winter Session 3] Branching Processes

0개의 댓글