1.1 Deterministic and Stochastic Models

모델링의 방법은 불확실성(uncertainty)의 여부에 따라 결정론적(deterministic) 방법, 확률론적(stochastic) 방법으로 나뉜다.

1. Deterministic Model

결정론적인 시스템에는 무작위성(randomness)이 없다. 즉, 입력(input)이 주어졌을 때 결과(output)은 반드시 동일하게 나온다. 함수나 미분 방정식은 특히 결정론적인 과정을 설명하기 위해 사용된다.

예를 들어, 박테리아의 수가 단위시간(1분)당 고정된 비율(20%)만큼 증가한다고 하자.

미분 방정식을 풀면, 다음과 같은 지수함수 형태의 해가 나온다.

• (참고) 도출 과정
  $\frac{dy} {dt} = (0.20)y \ \Rightarrow \frac 1 y dy = 0.20dt\\ {}\\ \int\frac 1 y dy = \int 0.20dt \ \Rightarrow \ln|y| = 0.20t+C \\ {}\\ y(t) = e^C\cdot e^{0.20 t} = y_0 e^{(0.20)t}\\ {}$

$\rightarrow$ $~t$분 후의 박테리아의 수에 대해 명확하게 말할 수 있다.

2. Stochastic Model

확률론적인 시스템에는 무작위성(randomness)이 있다. 즉, 결과는 불확실하다. 확률 변수나 확률 분포 등의 개념이 활용된다.

예를 들어, 박테리아의 다음 번식까지의 시간이 rate parameter를 0.20으로 하는 지수 분포를 따른다고 하자. 다음과 같이 나타낼 수 있다.

$\rightarrow$ $~t$분 후의 박테리아의 수에 대해 매번 다르게 말할 수 있다.

$\square$ 만일 $t$ 시점에서의 박테리아 수를 예측하는 것이 목표라면, 결정론적 모델이 더 효율적일 것이다. 그러나, 확률론적 모델은 각 개체에 대한 불확실성이 반영되어 있기 때문에 다음과 같은 다양한 질문에 대한 답을 내릴 수 있다.

1. $t$ 시점에서의 박테리아의 평균 수는?
2. $t$분 후의 박테리아의 수가 특정 임계점을 넘을 확률은?
3. 박테리아의 수가 2배가 되기까지의 시간의 확률 분포는?

3. SIR Model by Reed & Forest (Example 1.2)

SIR(Susceptible-Infected-Removed) 모델은 전염병이 사람 간 접촉을 통해 전파되고, 일정 시간이 지나면 회복 또는 면역력을 확보하여 전파에서 제외된다는 사실을 단순화된 형태로 나타낸다.

• $S$(Susceptible) : 전염 가능성이 있는 인구 수 → $S_t$ : $t$ 시점에 전염 가능성이 있는 인구 수
• $I$(Infected) : 전염된 상태의 인구 수 → $I_t$ : $t$ 시점에 전염된 상태의 인구 수
• $R$(Removed) : 회복한 상태(면역)의 인구 수 → $R_t$ : $t$ 시점에 회복한 상태(면역)의 인구 수
• $z$ : $S$와 $I$인 사람이 만났을 때 전염이 될 확률(고정)
• $p$ : $S$인 사람이 전염된 확률로, $1-(1-z)^{I_t}$
• 보충 설명 $S$인 사람이 $I$인 사람과 있을 때 전염될 확률은 $z$이고, 전염되지 않을 확률은 $1-z$이다. 만약 시점 $t$에 감염자가 $I_t$명 있다면? $S$인 사람이 모든 $I_t$명에게서 단 한 번도 전염되지 않을 확률은 $(1-z) (1-z)\cdots(1-z)=(1-z)^{I_t}$가 된다. 결국, $S$인 사람이 적어도 한 명으로부터 전염될 확률은 $1-(1-z)^{I_t}$이다.
  

시점 $t$에서 $S$인 사람의 수가 $S_t$명일 때, 각 사람마다 감염될 확률 $p$는 동일하고, 독립적으로 일어난다. 이를 동전 던지기에 비유하면, $S_t$개의 동전을 동시에 던졌을 때, 앞면(=감염)이 나올 확률이 $p$인 상황과 동일하다. 따라서, 시점 $t+1$에 감염되는 사람의 수 $I_{t+1}$은 확률적으로 결정이 되며, 다음과 같이 이항 분포를 따른다.

$I_{t+1}$은 위와 같은 분포에서 랜덤 샘플링하여 구할 수 있고, $S_{t+1} = S_t- I_{t+1}$로 구할 수 있다. $S_t$인 사람들은 그 다음 시점에서 계속 전염 가능성이 있는 상태($S_{t+1}$)로 남아있거나, 전염($I_{t+1}$)될 수 있다.
${}$

1.2 Stochastic Processes

1. Stochastic Processes

확률 과정은 확률 변수들의 모임으로, $\{X_t|t\in I\}$이다. 이때, $I$는 지표 집합(index set)으로 주로 시간을 나타내는 경우가 많다. 그리고 $S$는 상태 공간(state space)으로, 각 확률 변수 $X_t$가 취할 수 있는 값들의 집합이다.

• 지표 집합 (Index set) : $t$가 가질 수 있는 값
  • 이산형 : $I = \{0, 1, 2, \ldots\}$
  • 연속형 : $I = [0, \infty)$
• 상태 공간 (State space) : $X_t$가 가질 수 있는 값
  • 이산형 확률 변수
  • 연속형 확률 변수

1. 이산형 지표 & 이산형 확률 변수의 예 : 모노폴리 → 턴의 수 & 모노폴리의 칸 번호 (1~40)
2. 이산형 지표 & 연속형 확률 변수의 예 : 포화 산소량 → 매 시(hour) 단위 & 농도
3. 연속형 지표 & 이산형 확률 변수의 예 : 도착 과정 → 연속적인 시간 & 메시지의 개수
4. 연속형 지표 & 연속형 확률 변수의 예 : 브라운 운동 → 연속적인 시간 & 입자의 위치

2. Random walk - Gambler’s Ruin

이산형 지표 & 이산형 확률 변수의 예로 “도박꾼의 파산”이 있다. 먼저 도박꾼이 초기 자산 $k$ 달러로 도박을 했다고 가정하자. $p$의 확률(성공)로 $+1$이 되고, $1-p$의 확률(실패)로 $-1$이 된다. 이때 $n(n>k)$ 달러에 도달하거나 $0$ 달러에 도달하면 도박을 종료한다.

• $X_k =1 \text{ with probability } p$
• $X_k=-1 \text{ with probability } 1-p$
• $S_n = k+X_1+X_2+\cdots+X_n \text{ for } n\ge 1, \ S_0 = k$
• $S_0, S_1, S_2, \cdots$는 상태 공간 $\Z$를 가지는 이산 시간 확률 과정이다.
• $S_m$의 값이 $n(n>k)$에 도달하거나 $0$이 되면 종료한다.
  

2.1 Introduction:

💡 Markov Chain의 정의와 transition matrix에 대해 알아보자.

주사위 눈에 따라 현재 상태에서 눈의 수만큼 말이 이동하는 보드 게임(monopoly)을 생각해보자.

랜덤 변수 $X_n$을 위와 같이 정의하자.

위와 같은 상황에서 $X_4 = 10$일 확률은

즉 미래의 상태가 오직 직전의 상태와 관련이 있다는 것을 알 수 있다.

위 보드 게임에서 말의 위치 집합은 랜덤 변수의 집합이므로 확률 과정 중 monopoly이다.

그 중 다음 단계가 오직 현재의 상태와 관련이 있는 성질에 의해 Markov Chian이라 불린다.

Markov Chain
집합 $S$를 상태 공간(state space)이라고 하자. 확률 변수들의 열 $X_0, X_1, X_2, \dots$가 $S$의 원소를 값으로 가지며, 다음과 같은 성질을 만족하면 이를 마코프 체인(Markov chain) 이라고 한다. $P(X_{n+1} = j \mid X_0 = x_0, X_1, \dots, X_{n-1}, X_n = i) = P(X_{n+1} = j \mid X_n = i)$
모든 $x_0, x_1, \dots, x_{n-1}, i, j \in S$ 및 $n \geq 0$ 에 대하여 성립한다.
이 성질을 마코프 성질(Markov property) 이라고 한다.

여기서 Markov Chain은 time-homogeneous 성질을 가진다

Markov Chain is called time-homogeneous if
$P(X_n=j|X_{n-1}=i)=P(X_1=j|X_0=i)\, \forall n \in N$

Markov Chain은 monopoly이므로 state space는 finite개(let k)의 원소를 가진다.

이때 현 상태에서 다음 상태로 가는 경우의 수는 K*K개이고 각 경우의 수의 확률을 행렬로 나타낸 것을 transition-matrix라 한다

각 행은 현 상태 i에서 다음 상태 j=1,…..,k로 갈 때의 확률이므로 P_i1+,,,,+P_ik=1이다.

즉 (one-step)transition matrix면 stochastic matrix이다.

2.2 Markov Chain Cornucopia - examples

💡Markov Chain이 적용되는 상황들을 알아보자.

1. weather

어느 지역의 날씨가 비(r),눈(s),맑음(c) 이 세가지만 있다고 가정했을 때의 transition matrix

Q: 다음날 눈이 올 확률은?

: 적어도 60% 이상

2. i.i.d sequence

Sequence of iid random variables > Markov chain

$state~space= \{1,…k\}$

각 랜덤 변수들은 독립이기 때문에

따라서 모든 현재 상태에 대해서 X_i로 갈 확률이 p_i로 나타나기 때문에 transition matrix를 위와 같이 나타낼 수 있다.

3. Gambler’s ruin

도박꾼이 초기 자산 k달러에서 도박 (p의 확률로 +1, 1-p의 확률로 -1)

n달러 또는 0달러에 도달할 시 게임이 끝남

ex) n=6이고 p=1/3인 경우

4.Random walk on a graph

Def:
Degree of vertex $v$, denoted $deg(v)$, is the number of neighbors of $v$.

위 행렬은 위 상황에서의 transition matrix이다.

5.Lazy librarian-최적의 책 나열 알고리즘

책의 인기 정도를 대출될 확률로 생각하자. k권의 책에 대해

초기에 책이 왼쪽부터 index순으로 나열되어 있다. 사서는 반납된 도서를 왼쪽에 계속 넣는다.

이때 시간이 지날수록 동선이 최소화되는 나열에 수렴하게 된다.
${}\\$

2.3 Basic Computations

1. Markov chain에서의 probability distribution

probability distribution은 확률 벡터의 형태로 나타내고 $\alpha, \lambda, \pi$ 등으로 표기한다.

$\alpha = (\alpha_1, \alpha_2, … , \alpha_k)$가 $X_i$의 분포 $\rightarrow$ $P(X_i = j) = \alpha_j$ for all $j$

cf) probability vector란? 더해서 1인 음이 아닌 수들로 구성된 행백터

초깃값($X_0$=j)과 Markov chain의 transition matrix가 주어진 경우

초기 분포는 j번째 원소만 1인 (0, … , 0, 1, 0, … , 0)으로 볼 수 있고, transition matrix를 적용하여 n step 이후의 값 $X_n$의 확률 분포를 구할 수 있다(정확한 값을 구할 수는 없음)

2. n-step Transition Matrix

$X_0, X_1, …$ 가 transition matrix $P$를 가지는 Markov chain이라고 할 때, $P^n$은 n-step transition matrix가 된다.

For $n≥0, P_{ij}^n = P(X_n=j|X_0=i)$ for all $i, j$

즉, transition matrix $P$를 n번 거듭제곱하면 n-step 후로 전이시키는 transition matrix를 구할 수 있다.

Ex) 6-step transition matrix

Q : 각 원소가 가지는 의미는?

A : $P^6$의 i행 j열 원소를 $P_{ij}^6$라고 하면, $P_{ij}^6$는 $X_0=i$에서 6번의 step을 거쳐 $X_6=j$가 될 확률을 의미한다.

3. Chapman-Kolmogorov Relationship

For $m, n ≥ 0$, $P_{ij}^{m+n}=\Sigma_kP_{ik}^mP_{kj}^n$

위 식을 정리해보면

와 같다.

이는, m+n번의 step을 거쳐 확률변수가 i에서 j로 전이할 확률이 모든 k에 대해 (m번의 step을 거쳐 확률변수가 i에서 k로 전이할 확률)*(n번의 step을 거쳐 확률변수가 k에서 j로 전이할 확률)을 합한 것과 같음을 의미한다. 여기서 k는 확률변수 X가 가질 수 있는 값을 나타낸다.

4. Distribution of $X_n$

초기 분포($X_0$의 분포)를 $\alpha$로 두자. 이때, $X_n$의 분포는 아래와 같이 구할 수 있다.

즉, $X_n$이 상태 $j$를 가질 확률이 $\alpha P^n$의 $j$번째 열에 나타나므로 $X_n$의 분포 = $\alpha P^n$이다.

ex) weather

Q : 오늘 비가 왔을 때 이틀 뒤의 날씨 분포

A: 오늘 비가 왔으므로 $X_0=r$이라고 둘 수 있다. 이틀 뒤의 날씨는 $P^2$의 1번째 행(r)을 통해 확인할 수 있다. 오늘 비가 왔을 때 이틀 뒤 비(r)가 올 확률은 0.12, 눈(s)이 올 확률은 0.72, 구름(c)이 낄 확률은 0.16이다.

5. Markov Property

Markov chain의 기본 성질인 이전 시점에만 영향을 받고, 그 전과는 독립이라는 성질을 확장하면 다음과 같이 나타낼 수 있다.

Let $X_0, X_1, \ldots$ be a Markov chain. Then for all $m < n$,

$X_{n+1}$을 예측할 때, 값을 알고 있는 가장 최근의 과거가 $n-m$번째 전이가 일어난 상황이라면 (즉, $X_{n-m}=i$ 임을 알고 있음) $X_{n+1}=j$일 확률은 n-m 이전의 상황은 고려하지 않고, $X_{n-m}$에만 의존하여 $P_{ij}^{m+1}$이 전이행렬이 된다.

Reference

Dobrow, Robert P. Introduction to Stochastic Processes with R. 1st ed. Wiley, 2016.

이미지 출처: University of Oxford, Mathematical Institute. 사용 목적: 비영리·교육적 목적