[1]

술 취한 새는 둥지로 돌아올 수 있을까? - 고차원에서의 무작위 행보 이론 (Random Walk)

지난 포스팅 수학이야기 #5-1 에서는 1차원 (수직선) 상의 원점에서 시작하여 무작위 행보를 하는 물체에 대해 다루어보았다. 그러나 우리가 사는 3차원 세상에서의 술에 취한 사람은 땅 위를 걸어다니므로, 2차원 상의 무작위 행보로 보는 것이 타당하다. 따라서 이번 포스팅에서는 $\mathbb{R}^1$ 이 아닌 고차원 상에서의 Random Walk에 대해 다루어보겠다.

1. 고차원 상 Random Walk의 수학적 모델링

$d$ 차원 좌표 평면 상 원점 $O(0,0, ...,0)$ 에서 시작하여 각 좌표축 상의 + 또는 - 방향으로 동일 확률 $1/(2d)$ 을 가지고 격자점들 위에서 운동하는 물체를 생각해보자.

초기 좌표: $X_0 = (0, 0, ..., 0)$
$n$ 단계 이후의 좌표를 $X_n$ 이라 놓으면, 다음과 같은 도식에 따라 $X_{n+1}$ 이 결정됨을 알 수 있다.

예를 들어서 $d=2$ 차원의 경우에는 다음과 같다.

지난 포스팅의 Section 2에서 다루었듯이 우리가 관심있는 점들은 $X_n = (0, 0)\ (n >0)$ 을 만족하는 점들이다. 이들의 성질은 다음과 같이 정리해 볼 수 있다.

성질 1. $X_n = 0$ 를 가정하고, $d$ 개의 좌표축들 중 $i$ 번째 좌표축의 + 방향으로 움직인 횟수를 $x_i$ , - 방향으로 움직이는 것을 $y_i$ 로 놓으면,

$\sum_{i=1}^d (x_i + y_i) = n$

이고

$x_1 = y_1,\ x_2 = y_2,\ ...,\ x_d = y_d$

이므로

$n = 2 \sum_{i=1}^n x_i \implies 2 | n$

$n$ 은 짝수이다. 편의상 $n = 2m$ 으로 놓자.

성질 2. 두 개의 변수

$u_{2m}^d := \Pr \left( X_{2m} = 0 \right)$

$f_{2m}^d := \Pr \left( X_{2m} = 0 \text{ and } X_{2k} \neq 0 \text{ for all }0< k < n\right)$

를 정의하자. 즉, $u_{2m}^d$ 은 단순히 $X_{2m} = 0$ 일 확률이고, $f_{2m}^d$ 은 $2m$ 번째 움직임에서 처음으로 원점을 찍을 확률이다. 수학적 귀납법에 의해 $m \geq 1$ 일 경우

$u_{2m}^d = u_0^d f_{2m}^d + u_2^d f_{2m-2}^d + ... + u_{2m-2}^d f_2^d + u_{2m}^d f_0^d$

이 성립함을 알 수 있다. 편의상 $u_0^d = 1, f_0^d = 0$ 로 놓자.

2. 생성함수 (Generating Function) 을 이용하여 분석하기 - [2]

2-1. 귀찮은 계산들...

1차원 에서의 경우와 마찬가지로 성질 2에서의 수열 관계식을 풀려면 생성함수를 이용하는 것이 가장 편리하다.

$\tilde{f}_{m}^d = f_{2m}^d$

그리고

$\tilde{u}_{m}^d = u_{2m}^d$

로 재정의한 뒤, 각각의 생성함수

$\tilde{U}^d(x) = \sum_{m=0}^{\infty} \tilde{u}_m^d x^m,\ \tilde{F}^d(x) = \sum_{m=0}^{\infty} \tilde{f}_m^dx^m$

를 살펴보면

$\begin{align*} \tilde{U}^d(x) &= 1 + \sum_{m=1}^{\infty} \tilde{u}_m^d x^m \\ &= 1 + \sum_{m=1}^{\infty} u_{2m}^d x^m \\ &= 1 + \sum_{m=1}^{\infty} (u_{2m}^d f_0^d + ... + u_0^d f_{2m}^d )x^m \\ &= 1 + \sum_{m=1}^{\infty} (\tilde{u}_m^d \tilde{f}_0^d + ... + \tilde{u}_0^d \tilde{f}_m^d) x^m\\ &= 1 + \left( \sum_{m=0}^{\infty} \tilde{u}_m^d x^m \right ) \left( \sum_{m=0}^{\infty} \tilde{f}_m^d x^m \right)\\ &= 1 + \tilde{F}^d(x)\tilde{U}^d(x) \end{align*}$

임을 알 수 있다.

2-2. 문제상황을 대입시키기.

술에 취한 사람이 집으로 돌아오는 것은 다시말하면, 모든 짝수 $2m$ 에 대해 $f_{2m}^d$ 의 합이 1이 됨을 의미한다. (각각의 $f_{2m}^d$ 는 확률을 의미하므로)

$\sum_{m=0}^{\infty} f_{2m}^d = 1 ?$

이는 다시 쓰면, 생성함수의 극한

$\lim_{x \rightarrow 1^-} \tilde{F}^d (x)$

을 조사하는 것과 동치이다. 앞서 구한 등식을 대입하여 보면,

$\lim_{x \rightarrow 1^-} \tilde{F}^d(x) = \lim_{x \rightarrow 1^-} \frac{\tilde{U}^d(x) - 1}{\tilde{U}^d(x)}$

이므로, 우리는 다음의 극한,

$\lim_{x \rightarrow 1^-} \tilde{U}^d(x) = \sum_{m=1}^{\infty} u_{2m}^d$

만을 조사하면 된다.

3. 결과

3-1. 1차원

지난 번 포스팅에서, $d=1$ , 즉 1차원의 경우

$u_{2m}^d = {2m \choose m}2^{-2m}$

임을 보였다. 이 때에는 직접 $f_{2m} = \frac{u_{2m}}{2m-1}\ (m \geq 1)$ 임을 이용하여 문제에 대한 답이 YES 임을 보였다.

3-2. 2차원

이제 $u_{2m}^2$ 를 구해보자. $d$ 개의 좌표축들 중 $i$ 번째 좌표축의 + 방향으로 움직인 횟수를 $x_i$ , - 방향으로 움직이는 횟수를 $y_i$ 로 놓으면,

$\begin{cases} x_1 + y_1 + x_2 + y_2 = 2m \\ x_1 = y_1 \\ x_2 = y_2 \\ x_1, y_1, x_2, y_2 \in \mathbb{Z}^{\geq 0} \end{cases}$

를 만족하고

$\frac{(2m)!}{x_1!y_1!x_2!y_2!}$

가지의 서로 다른 경로의 수가 존재하므로 총 경로의 수는

$\begin{align*} \sum_{x_1 + y_1 + x_2 + y_2 = 2m} \frac{(2m)!}{x_1!y_1!x_2!y_2!} &= \sum_{x_1 + x_2 = m} \frac{(2m)!}{x_1!x_1!x_2!x_2!} \\ &= \sum_{x_1 = 0}^{m} \frac{(2m)!}{x_1!(m-x_1)!x_1!(m-x_1)!}\\ &= \sum_{x_1 = 0}^{m} \frac{(2m)!}{m!m!} \left( \frac{m!}{x_1! (m-x_1)!} \right )^2 \\ &= \sum_{x_1= 0}^{m} {2m \choose m} {m \choose x_1}^2 \\ &= {2m \choose m} \sum_{x_1 = 0}^{m} {m \choose x_1}^2 \\ &= {2m \choose m}^2 \end{align*}$

가 나온다. 마지막 등식은 이항정리의 성질로 부터 유도됐다. 따라서,

$u_{2m}^2 = 4^{-2m} {2m \choose m}^2$

를 만족함을 알 수 있다. $\tilde{F}(1-)$ 의 값이 존재하기 위해서는 $\tilde{U}^2(1-) = \infty$ 여야 한다. 그런데 스털링 근사식으로 부터 적당한 자연수 $N, K (>0)$ 에 대해

${2m \choose m} \geq K \frac{4^m}{\sqrt{\pi m}}$

이 성립하고, 따라서

$\begin{align*} \tilde{U}^2(1-) = \sum_{m=0}^{\infty} u_{2m}^2 &= \sum_{m=0}^{N-1}u_{2m}^2 + \sum_{m = N}^{\infty} u_{2m}^2 \\ &\geq \sum_{m=0}^{N-1}u_{2m}^2 + \frac{K^2}{\pi} \sum_{m=N}^{\infty} \frac{1}{m} > \infty \end{align*}$

이 성립한다. 즉

2차원의 경우에도, 무작위 행보는 언제간 반드시 돌아옴을 알 수 있다.

3-3. 3차원 - [3]

이제 마지막으로 3차원을 살펴보자. 물론 인간은 날아다닐 수 없으므로, 3차원에서의 무작위 행보는 사람에게 해당되지 않는다. 적절한 예시를 찾아보면, 날아다니는 새 정도? 를 들 수 있다. 그럼 과연

술에 취한 새는 무작위 비행 중 언젠가 둥지로 돌아올 수 있을까?

이에 대한 답을 하기 위해서는 $u_{2m}^3$ 를 구하여야 한다.

위와 똑같은 방법으로 구해보면, 다음을 얻는다

$u_{2m}^3 = (2\cdot 3)^{-2m} {2m \choose m} \sum_{x_1 + x_2 + x_3 = m} \left( \frac{m!}{x_1!x_2!x_3!} \right )^2$

다항정리에 의해

$3^{-m}\sum_{x_1 + x_2 + x_3 = m} \left( \frac{m!}{x_1!x_2!x_3!} \right )^2 =1$

이므로

$\sum_{x_1 + x_2 + x_3 = m} \left( \frac{m!}{x_1!x_2!x_3!} \right )^2 \leq \max_{x_1,x_2, x_3} \frac{m!}{x_1!x_2!x_3!}$
가 성립한다.

다항정리의 계수가 최대가 되려면, 모든 $x_1, x_2, x_3$ 가 균등하게 $m/3$ 에 최대한 가까이 위치한 정수여야 한다. 스털링 근사를 적절히 활용하면

$\begin{align*} u_{2m}^3 &\leq 2^{-2m}3^{-m} {2m \choose m} \frac{m!}{(m/3)!(m/3)!(m/3)!} \\ &\sim \frac{1}{\sqrt{\pi m}} 3^{-m} \frac{\sqrt{2\pi m}(m/e)^m}{\prod_{i=1}^3 \sqrt{2\pi m/3} (m/3e)^{m/3}} \\ &\sim K \frac{m^{m-1/2}}{m^{1/2 + 3/2 + m}} = K/m^{3/2} \end{align*}$

이고 $p$ - 급수 판정법 에 의해 $\tilde{U}(1-) = \sum_{m=0}^{\infty} u_{2m}^3$ 은 수렴한다. 즉

술에 취한 새는 무작위 비행 중 언젠가는 둥지로 돌아온다고 확정지을 수 없다.

3-4. 3차원 이상의 고차원

사실, 위의 식에서 $3 \rightarrow d$ 로 바꾸면 $d \geq 3$ 에서의 일반화를 시킬 수 있다. 구해보면

$\begin{align*} u_{2m}^d &\leq 2^{-2m}d^{-m} {2m \choose m} \frac{m!}{(m/d)!(m/d)!...(m/d)!} \\ &\sim \frac{1}{\sqrt{\pi m}} d^{-m} \frac{\sqrt{2\pi m}(m/e)^m}{\prod_{i=1}^d \sqrt{2\pi m/d} (m/de)^{m/d}} \\ &\sim K \frac{m^{m+1/2}}{m^{1/2 + d/2 + m}} = K/n^{d/2} \end{align*}$

가 된다. $p$ - 급수 판정법 에 의해 $d/2 > 1 \implies d > 2 \implies d \geq 3$ 의 경우 $\tilde{U}(1-) = \sum_{m=0}^{\infty} u_{2m}^d$ 은 수렴한다.

따라서 3차원 이상의 Random Walk는 반드시 회귀를 보장하지는 않는다.

4. 예시

MATLAB을 이용하여 2, 3차원 Random walk를 나타내보면 다음과 같다.

%% 2D & 3D Random Walk
M = 10000;
X = [0 0 0]';
p = [1/6 1/6 1/6 1/6 1/6 1/6];

for i = 2 : 1 : M+1
    x = randsample([1 2 3 4 5 6], 1, true, p);
    if x == 1
        X = [X, X(:,i-1) + [1 0 0]'];
    elseif x == 2
        X = [X, X(:,i-1) + [-1 0 0]'];
    elseif x == 3
        X = [X, X(:,i-1) + [0 1 0]'];
    elseif x == 4
        X = [X, X(:,i-1) + [0 -1 0]'];
    elseif x == 5
        X = [X, X(:,i-1) + [0 0 1]'];
    else
        X = [X, X(:,i-1) + [0 0 -1]'];
    end
end

plot(X(1, :), X(2,:));
grid on;
figure;
plot3(X(1,:), X(2,:), X(3,:));
grid on;

5. 결론

1차원 (수직선) 과 2차원 (좌표평면)에서 무작위 행보 운동을 하는 물체는 언젠가는 시작점 (원점)으로 회귀한다.
3차원 이상에서의 무작위 행보는 회귀를 담보할 수 없다
술에 취한 사람은 집에 돌아오지만 술에 취한 새는 둥지로 돌아가지 못할 수 있다.

6. 출처/인용

[1] https://www.gizmodo.com.au/2012/05/lost-pet-parakeet-found-its-way-home-by-telling-the-police-its-home-address/ (사진)

[2] https://www.dartmouth.edu/~chance/teaching_aids/books_articles/probability_book/Chapter12.pdf

[3] https://services.math.duke.edu/~rtd/PTE/PTE4_1.pdf

7. 추신

다음 이야기 부터는 좀 더 쉽고 재밌는 주제로 써보겠습니다.

Sort:

Trending

[-]

sleeprince (59) 7 years ago (edited)

골 때리는데 재밌네요ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ 막연히 고차원에서도 까짓거 언젠가 돌아오겠지 생각했는데, d ≥ 3 에서 u_2m가 수렴하는군요. 어쩐지 새가 좀 더 지구 자기장을 잘 느끼고 방향을 잘 찾는다 했더니, 수학적인 이유가 있었네요ㅎㅎㅎ

$0.00

mathsolver (53) 7 years ago

읽어주셔서 감사합니다 !

wakeprince (54) 7 years ago (edited)

확실한 컨셉이 있으시네요ㅋㅋㅋ 여행 다녀오시기 전 @beoped님도 이렇게 수식이 난무하는 포스팅을 종종 하셨는데, 자주 찾아뵙겠습니다.

beoped (69) 7 years ago (edited)

와우! 제가 등장했군요! 여행 후 요새는 다시 우주에 빠져 있어서 ㅋㅋㅋ
수학 포스팅도 한번 준비해 봐야겠군요;;

@mathsolver 님 금융 수학 포스팅도 종종 올려주세요! ㅎㅎ [쉽고 재미있는 주제는 아니네요;; ㅋㅋㅋㅋ] 예전에 한참 블랙숄즈모형 같은거 PDE 풀고 모델링하고 했었는데.. Financial Engineering 보고 떠올랐네요 ㅎㅎ

virus707 (76) 7 years ago

이오스 계정이 없다면 마나마인에서 만든 계정생성툴을 사용해보는건 어떨까요?
https://steemit.com/kr/@virus707/2uepul

[수학 이야기 #3 - 2] 술에 취한 새는 둥지로 들어갈 수 있을까? - Random Walk [마지막편]