일반화된 랜덤워크

일반화된 랜덤워크

Generalized random walk

정의

9989F33B5C467DC819.png 확률과정 $\left\{ X_{n} \right\}$ 의 상태공간이 정수의 집합 $\left\{ \cdots , -2 , -1, 0 , 1 , 2 , \cdots \right\}$ 이고, 상태 $0$ 에서 이라고 하자. 다음 스텝에서 $1$ 만큼 작아질 확률을 $p$, $1$ 만큼 커질 확률이 $(1-p)$ 일 때 $\left\{ X_{n} \right\}$ 을 일반화된 랜덤워크라 한다.

설명

랜덤워크란 확률 과정 중에서도 아주 단순한 예시로써, 보통 좌우로 갈 확률을 똑같이 둔다. 일반화된 랜덤워크란 그 확률을 다르게 두기도 할 뿐이다. 단순하게 생각해봐도 그 좌우로 갈 확률이 같다면 시작 상태 $0$ 을 중심으로 왔다갔다 할 것임을 어렵지 않게 짐작할 수 있다. 하지만 어느 한쪽이 크다면 시간이 갈수록 그 쪽으로 발산해버릴 것이다.

한편 상태공간을 유한하게 제한한 케이스로써 도박군의 파산 문제를 생각해볼 수 있다.

정리

$\displaystyle p = {{1} \over {2}}$ 이면 상태 $0$ 은 리커런트하고, $\displaystyle p \ne {{1} \over {2}}$ 이면 상태 $0$ 은 트랜젼트하다.

증명

$\displaystyle \sum_{n=1}^{\infty} p_{00}^{(n)}= \infty$ 면 $0$ 은 리커런트하고, $\displaystyle \sum_{n=1}^{\infty} p_{00}^{(n)} < \infty$ 면 $0$ 은 트랜젼트하다. 우선 상태 $0$ 에서 홀수번만큼 움직여서 $0$ 으로 돌아올 확률은 확실하게 $0$ 이므로 $$ p_{00}^{ ( 2n - 1 )} = 0 $$ 이다. $2n $ 번만큼 움직여서 $0$ 으로 돌아왔다는 것은 정확히 좌로 $n$ 번, 우로 $n$ 번 움직였다는 의미이므로 $$\displaystyle p_{00}^{ ( 2n )} = \binom{2n}{n} p^{n} (1-p)^{n}$$ 이다. 이제 $$\displaystyle p_{00}^{ ( 2n )} = {{ ( 2n )! } \over { ( n! )^2 }} \left( p ( 1 - p ) \right)^{n}$$

이 발산하는지 수렴하는지 확인하면 충분하다.

스털링 근사: $$\lim_{n \to \infty} {{n!} \over { n^{ n + 1/2} e^{- n} \sqrt{ 2 \pi } }} = 1$$

팩토리얼을 계산하는게 어렵고, $n$ 은 무한대를 상정하므로 스털링 근사를 사용한다. $$ \begin{align*} p_{00}^{ ( 2n )} \approx& {{ (2n)^{2n + 1/2} e^{-2n} \sqrt{ 2 \pi } } \over { \left( n^{n + 1/2} e^{-n} \sqrt{ 2 \pi } \right)^{2} }} \left( p ( 1 - p ) \right)^{n} \\ =& {{ (2n)^{2n } \sqrt{2n} } \over { \left( n^{n } \right)^{2} n \sqrt{ 2 \pi } }} \left( p ( 1 - p ) \right)^{n} \\ =& {{ 4^{n} n^{2n} \sqrt{ 2n } } \over { n^{2n} n \sqrt{ 2 \pi } }} \left( p ( 1 - p ) \right)^{n} \\ =& {{ \left( 4 p ( 1 - p ) \right)^{n} } \over { \sqrt{ \pi n } }} \end{align*} $$


Case 1. $\displaystyle p = {{1} \over {2}}$

p-급수 판정법: $\displaystyle \sum _{ n=1 }^{ \infty }{ 1 \over {n^p} }$ 이 수렴하는 것은 $p>1$과 동치다.

p-판정법에 의해 $\displaystyle \sum_{n=1}^{\infty} {{ \left( 4 p ( 1 - p ) \right)^{n} } \over { \sqrt{ \pi n } }} = {{1} \over { \sqrt{ \pi } }} \sum_{n=1}^{\infty} {{1} \over { \sqrt{n} } }$ 은 발산하고, 상태 $0$ 은 리커런트하다.


Case 2. $\displaystyle p \ne {{1} \over {2}}$

비 판정법: $\displaystyle r = \lim_{n \to \infty} { {|a_{n+1}|} \over {|a_{n}|} }$ 에 대해 $r<1$이면 $\displaystyle \sum _{ n=1 }^{ \infty }{ { a }_{ n }}$은 절대수렴, $r>1$이면 $\displaystyle \sum _{ n=1 }^{ \infty }{ { a }_{ n }}$은 발산한다.

$$\lim_{ n \to \infty } \left| {{ {{ \left( 4 p ( 1 - p ) \right)^{n+1} } \over { \sqrt{ \pi ( n + 1 ) } }} } \over { {{ \left( 4 p ( 1 - p ) \right)^{n} } \over { \sqrt{ \pi n } }} }} \right| = \lim_{n \to \infty } {{ 4 p ( 1 - p ) } \over { \sqrt{ (n+1) / n } }} = 4p (1 - p) < 1$$ 이므로, 비 판정법에 의해 $$\sum_{n=1}^{\infty} {{ \left( 4 p ( 1 - p ) \right)^{n} } \over { \sqrt{ \pi n } }}$$ 은 수렴하고 상태 $0$ 은 트랜젼트하다.

같이보기

댓글