마코프체인의 일종인 랜덤워크에 대해서 파해쳐보자.
랜덤워크
마코프체인 중 주기가 2가지 밖에 없는 것을 랜덤워크라고 한다.
여기서는 1차원, 이산형 랜덤워크에 대해서 다뤄본다.
랜덤워크의 특징
- 정상 마코프과정이다.
- 즉, 계수과정이자, 이산형 확률과정이다.
X_t \in S. \kern{10pt}
S = \text{(상태공간)} =
\{0,~1,~2, \cdots, N\}
- N은 상태공간(추이도식에서 노드)의 갯수.
- 이제 두 가지 예시를 보면서 특정상태에서의 확률, 평균, 분산을 보자.
랜덤워크: 특정상태의 확률 1
추이함수 & 초기함수
다음과 같이 그림(=추이도식)을 그렸다고 치자.
이때의 추이함수는 다음과 같다.
\begin{align*}
&P(0,~0) = \frac{1}{3} \\[10pt]
&P(x,~x+1) = \frac{1}{3}~
I(x < N) \\[10pt]
&P(x,~x-1) = \frac{2}{3}~
I(0 < x) \\[10pt]
&P(N,~N) = \frac{2}{3}
\end{align*}
또한 랜덤워크의 초기함수는 다음과 같다.
P(X_0 = x) = \phi(x) = \dfrac{1}{N+1}
특정상태의 확률 구하기
인제 특정상태가 특정숫자일 확률을 계산해보자.
위와 같은 추이도식이 주어질 때, P(X_1 = x)은 얼마인가?
조건부확률로 계산
\begin{align*}
&P(X_1 = x) =
\sum_{y}~P(X_0 = y, X_1 = x) \\
&=\sum_{y}~P(X_0 = y)
~P(X_1 = x~|~X_0 = y) \\
&=\sum_{y}~\frac{1}{N+1}
~P(X_1 = x~|~X_0 = y) \\
\end{align*}
인제 P(X_1 = x~|~X_0 = y)의 값을 계산해 보자.
x값과 y값에 따라 다음과 같은 경우의 수가 있다.
- X_0 = 0이고, X_1 = 0인 경우
- X_0 = 0이고, X_1 = 1인 경우
- X_0 = x이고, X_1 = x+1인 경우 (x가 0이나 N이 아닌 경우)
- X_0 = x이고, X_1 = x-1인 경우 (x가 0이나 N이 아닌 경우)
- X_0 = N이고, X_1 = N인 경우
- X_0 = N이고, X_1 = N-1인 경우
\begin{align}
P(X_0 = 0~|~X_1 = x) &=
\dfrac{1}{3}~I(x=0)\\[10pt]
P(X_0 = 0~|~X_1 = x) &=
\dfrac{2}{3}~I(x=1) \\[10pt]
P(X_0 = a~|~X_1 = x) &=
\dfrac{2}{3}~I(x=a+1) \\[10pt]
P(X_0 = a~|~X_1 = x) &=
\dfrac{1}{3}~I(x=a-1) \\[10pt]
P(X_0 = N~|~X_1 = x) &=
\dfrac{2}{3}~I(x=N) \\[10pt]
P(X_0 = N~|~X_1 = x) &=
\dfrac{1}{3}~I(x=N-1) \\[10pt]
\end{align}
(3), (4)는 결국 x가 1 \sim N-1의 상황이므로, I(x \in \{1, \cdots N\})로 합칠 수 있다.
인제 이것을 정리해보면 다음과 같다.
P(X_1 = x) = \small\frac{1}{N+1}~
\bigg\{
I(x \in \{1, \cdots N\}) +
\dfrac{2}{3}~I(x=0~or~N) +
\dfrac{1}{3}~I(x=1~or~N-1)
\bigg\}
추이도식으로 계산
좀 더 쉽게 추이도식으로 P(X_1 = x)를 구할 수도 있다.
\small
\begin{align*}
P(X_1 = 0) &=
P(X_0 = 0~|~X_1 = 0)
+ P(X_0 = 1~|~X_1 = 0)
= \dfrac{2}{3}
\\[10pt]
P(X_1 = 1) &=
P(X_0 = 0~|~X_1 = 1) +
P(X_0 = 2~|~X_1 = 1) = 1\\[10pt]
\vdots \\[10pt]
P(X_1 = N-1) &=
P(X_0 = N-2~|~X_1 = N-1) +
P(X_0 = N~|~X_1 = N-1) = 1\\[10pt]
P(X_1 = N) &=
P(X_0 = N~|~X_1 = N)
+ P(X_0 = N-1~|~X_1 = N)
= \dfrac{4}{3}
\\[15pt]
P(X_1 = x) &= \dfrac{1}{N+1}
\bigg\{
\dfrac{2}{3}~I(x=0) +
I(x \in \{1, \cdots N-1\}) +
\dfrac{4}{3}~I(x=N)
\bigg\}
\end{align*}
첫번째 상태의 기댓값
이제 어떠한 점에서 시작을 하건, 특정상태가 평균적으로 가실 수 있는 값을 생각해보자.
즉, 랜덤워크 속 특정상태의 기댓값을 구해보자. 가령, E(X_1)은 얼마인가?
\begin{align*}
&E(X_1) = \sum_{x=0}^{N}~x \cdot P(X_1 = x) \\[15pt]
&= \sum_{x=1}^{N-1}~x \cdot P(X_1 = x) + N \cdot P(X_1 = N) \\[15pt]
&= \dfrac{1}{N+1} \cdot
\sum_{x=1}^{N-1}~x
+ N \cdot \dfrac{1}{N+1}
\cdot \dfrac{4}{3}
\\[15pt]
&= \dfrac{N(3N+5)}{6(N+1)}
\end{align*}
랜덤워크: 특정상태의 확률 2
추이함수 & 초기함수
다음과 같이 그림(=추이도식)을 그렸다고 치자.
이때 추이함수는 다음과 같다.
\begin{align*}
P(X_{t+1} = x+1~|~X_{t} = x) &=
p \\[10pt]
P(X_{t-1} = x-1~|~X_{t} = x) &=
1-p \\[10pt]
P(X_{t-1} = x~|~X_{t} = x) &=
(1-p)~I(x=0) + p~I(x=3)
\end{align*}
또한 초기함수는 다음과 같다.
\phi(x) = P(X_0 = x). \kern{10pt}
X_0\sim bernoulli(p)
상태 1개의 적률
이러한 상황에서, E(X_1)는 얼마인가?
우선 E(X_1) = E\big(E(X_1|X_0)\big)으로 고쳐쓸 수 있다.
\begin{align*}
&E(X_1|X_0 = 0) =
\sum_{y} y \cdot p(X_1 = y|X_0 = 0)
\\[15pt]
&= 0 + 1 \cdot P(X_1 = 1|X_0 = 0)
= p
\\[20pt]
&E(X_1|X_0 = 1) =
\sum_{y} y \cdot p(X_1 = y|X_0 = 0)
\\[15pt]
&= 0 + 2 \cdot P(X_1 = 2|X_0 = 0)
= 2p
\\
\end{align*}
따라서 E(X_1)은 다음과 같다.
\begin{align*}
&E(X_1) = E\big(E(X_1|X_0)\big)
\\[5pt]
&= E\big(p \cdot I(X_0 = 0) +
2p \cdot I(X_0 = 1)\big)
\\[5pt]
&= p~E\big(I(X_0 = 0)\big) +
2p~E\big(I(X_0 = 1)\big)
\end{align*}
지시함수 I(X_0 = x)의 기댓값은 p(X_0 = x)로 생각. 왜? 클릭
\therefore E(X_1) = p \cdot (1-p) + 2p \cdot p = p(1+p)
이어서 Var({X_1})도 구해보자. 그에 앞서 E({X_1}^2)를 구해야 한다.
\begin{align*}
E({X_1}^2) &=
E \Big[ E({X_1}^2~|~X_0 = 0) + E({X_1}^2~|~X_0 = 1) \Big] \\[10pt]
&= E\Big[~p \cdot I(X_0 = 0) +
4p \cdot I(X_0 = 1)~\Big] \\[10pt]
&= p(1+3p)
\end{align*}
Var(X_1) = p(1+3p)- \big[p(1+p)\big]^2 = p(1+2p-2p^2-p^3)
상태 2개의 적률
이제 상태 2개의 공분산도 생각해보자.
Cov(X_0,~X_1)은 얼마인가? 그 전에, E(X_0X_1)를 구해보자.
E(X_0X_1)은 E\big(X_0~E(X_1|X_0)\big)로 고칠 수 있다.
\begin{align*}
&E\big(X_0~E(X_1|X_0)\big) =
E\Big(X_0 \cdot p \cdot I(X_0 = 0) + X_0 \cdot 2p \cdot I(X_0 = 1) \Big) \\[10pt]
&=p \cdot E(X_0 \cdot I(X_0 = 0)) +
2p \cdot E(X_0 \cdot I(X_0 = 1))
\\[10pt]
&= 2p^2
\\[20pt]
&Cov(X_0,~X_1) =
2p^2 - p \cdot p~(1+p)
=p^2~(1-p) > 0
\end{align*}
이걸 통해 X_0과 X_1은 양의 상관관계임을 알 수 있다.
상태 3개의 적률
E(X_0X_1X_2)는 얼마인가?
- 우선적으로 E(X_0X_1X_2) = E(X_0~E(X_1X_2~|~X_0))으로 바꿀 수 있다.
- E(X_1X_2~|~X_0)을 계산하는데, 마코프과정의 성질을 이용한다.
E(X_1X_2~|~X_0) =
E[E(X_1,~X_2~|~X_0,~X_1)] = E[X_1~E(X_2~|~X_1)]
E(X_2~|~X_1)은 다음과 같이 계산한다. (주어진 추이함수를 이용)
E(X_2~|~X_1 = x) = \sum_a~a\cdot P(X_2=a~|~X_1 = x)
- x = 0일 때
P(X_2=a~|~X_1 = 0)
- x = 1 아니면 2일때
(x-1)~P(X_2=x-1~|~X_1 = x) +
(x+1)~P(X_2=x+1~|~X_1 = x)
- x = 3일 때
2P(X_2=a~|~X_1 = b) +
3P(X_2=a~|~X_1 = b)
이를 정리하면 다음과 같다.
\begin{align*}
&= \begin{cases}
p &I(x=0)\\
(x-1)(1-p) + (x+1)p &I(x=1~or~2)\\
2(1-p) + 3p &I(x=3)\\
\end{cases} \\[30pt]
&= \begin{cases}
p &I(x=0)\\
x + 2p - 1 &I(x=1~or~2)\\
2 + p &I(x=3)\\
\end{cases}
\end{align*}
위의 케이스에서 p만 분리해보자. 이 경우 p는 상태공간 어디에서든 적용된다.
\begin{align*}
E(X_2~|~X_1 = x) &= p +
(x+p-1)~I(x = 1~or~2) + 2~I(x = 3) \\[5pt]
E(X_2~|~X_1) &= p +
(X_1+p-1)~I(X_1 = 1~or~2) +
2~I(X_1 = 3)
\end{align*}
- 다시 E(X_1X_2~|~X_0) = E[X_1~E(X_2~|~X_1)]를 계산해보자.
\begin{align*}
&E(X_1X_2~|~X_0) = E[X_1~E(X_2~|~X_1)]
\\[10pt]
&= E\big[ X_1 \cdot p +
X_1 \cdot(X_1+p-1)~I(X_1 = 1,~2) + X_1 \cdot 2~I(X_1 = 3)
\big]
\end{align*}
식을 세 파트로 나눠서 계산해보자.
첫 번째 파트는 다음과 같이 계산할 수 있다.
E\big[ X_1 \cdot p] =
p \cdot E(X_1) =
p \cdot p(1+p)
두 번째 파트는 다음과 같이 계산할 수 있다. 지시함수 테크닉을 사용
물론, P(X_1 = 1)과 P(X_1 = 2)는 따로 계산해야 한다.
\begin{align*}
&E\big[X_1 \cdot(X_1+p-1)
~I(X_1 = 1~or~2)\big] \\[5pt]
&= 1 \cdot p \cdot P(X_1 = 1) +
2(1 + p) \cdot P(X_1 = 2) \\[5pt]
&= 1 \cdot p \cdot p(1+p) +
2p^2(1+p)
\end{align*}
마지막 파트는 다음과 같이 계산할 수 있다. 지시함수 테크닉을 사용
\begin{align*}
&E \big[X_1 \cdot 2
~I(X_1 = 3) \big] =
2 \cdot E[X_1 \cdot I(X_1 = 3)]
\\[5pt]
&=2 \cdot\sum_y~y~I(y = 3)~P(X_1 = y)
\\[5pt]
&=2 \cdot 3 \cdot P(X_1 = 3)
\\[5pt]
&=0
\end{align*}
그래서 E(X_1X_2~|~X_0)는 다음과 같다.
\begin{align*}
E(X_1X_2~|~X_0) &= p^2(1+p) + p^2(1-p) +2p^2(1-p)
\\[5pt]
&=2p^2(2+p)
\end{align*}
결과적으로, E(X_0X_1X_2)는 다음과 같다.
\begin{align*}
E(X_0X_1X_2) &= E(X_0~E(X_1X_2~|~X_0))
\\[5pt]
&=p \cdot 2p^2(2+p)
\\[5pt]
&= 2p^3(2+p)
\end{align*}
랜덤워크: 무한번째 상태의 확률
무한번째 상태의 확률은 추이행렬로 구하는 것이 편하다.
추이함수 & 초기함수
추이함수들의 묶음을 행렬로 표현.
\bold{\underline{P}}=
\begin{bmatrix}
1-p & p \\[5pt]
q & 1-q \\
\end{bmatrix}
초기함수도 벡터로 표현할 수 있다.
{\underline{\phi}_0}^t =
\begin{bmatrix}
P(X_0 = 0) & P(X_0 = 1)
\end{bmatrix}
추이행렬의 n승
해당 행렬을 고유값 분해하면 다음과 같다.
\begin{bmatrix}
1-p & p \\[5pt]
q & 1-q \\
\end{bmatrix}^n
=
\begin{bmatrix}
1 & p \\[5pt]
1 & -q \\
\end{bmatrix}
\begin{bmatrix}
1 & 0 \\[5pt]
0 & 0 \\
\end{bmatrix}^n
\cdot \dfrac{1}{p+q}
\begin{bmatrix}
q & p \\[5pt]
1 & -1 \\
\end{bmatrix}
n \to \infty 했을 때 그 값은 다음과 같다.
\begin{bmatrix}
1-p & p \\[5pt]
q & 1-q \\
\end{bmatrix}^\infty
=
\dfrac{1}{p+q}
\begin{bmatrix}
q & p \\[5pt]
q & p \\
\end{bmatrix}
이 상태에서 초기함수 x 추이행렬을 하면 무한번째 상태의 확률이 나온다.
{\underline{\phi}_t}^\infty =
\begin{bmatrix}
P(X_0 = 0) & P(X_0 = 1)
\end{bmatrix} \cdot
\dfrac{1}{p+q}
\begin{bmatrix}
q & p \\[5pt]
q & p \\
\end{bmatrix}
이때의 확률은 초기확률함수와 아무 상관이 없다.
- 즉, 먼 미래의 분포는 초기확률함수에 의존하지 않는다.