<center> <img src = "https://i.imgsafe.org/ec/ecf15e9926.jpeg" /></center>
[1]

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

지난 포스팅 [수학이야기 #5-1](https://steemit.com/kr/@mathsolver/3-1) 에서는 1차원 (수직선) 상의 원점에서 시작하여 무작위 행보를 하는 물체에 대해 다루어보았다. 그러나 우리가 사는 3차원 세상에서의 술에 취한 사람은 땅 위를 걸어다니므로, 2차원 상의 무작위 행보로 보는 것이 타당하다. 따라서 이번 포스팅에서는 <img src="http://latex.codecogs.com/gif.latex?\mathbb{R}^1" title="\mathbb{R}^1" /> 이 아닌 고차원 상에서의 Random Walk에 대해 다루어보겠다.

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

<img src="http://latex.codecogs.com/gif.latex?d" title="d" /> 차원 좌표 평면 상 원점 <img src="http://latex.codecogs.com/gif.latex?O(0,0, ...,0)" title="O(0,0)" align = "center"/> 에서 시작하여 각 좌표축 상의 + 또는 - 방향으로 동일 확률 <img src="http://latex.codecogs.com/gif.latex?1/(2d)" title="1/(2d)" align = "center"/> 을 가지고 격자점들 위에서 운동하는 물체를 생각해보자.

1. 초기 좌표: <img src="http://latex.codecogs.com/gif.latex?X_0&space;=&space;(0,&space;0, ..., 0)" title="X_0 = (0, 0)" align ="center"/>

2. <img src="http://latex.codecogs.com/gif.latex?n" title="n" /> 단계 이후의 좌표를 <img src="http://latex.codecogs.com/gif.latex?X_n" title="X_n" align = "center"/> 이라 놓으면, 다음과 같은 도식에 따라 <img src="http://latex.codecogs.com/gif.latex?X_{n&plus;1}" title="X_{n+1}" align = "center"/> 이 결정됨을 알 수 있다.

예를 들어서 <img src="http://latex.codecogs.com/gif.latex?d=2" title="d=2" /> 차원의 경우에는 다음과 같다.

<center> <img src = "https://i.imgsafe.org/e2/e2d72e9372.png" /></center>

지난 포스팅의 Section 2에서 다루었듯이 우리가 관심있는 점들은 <img src="http://latex.codecogs.com/gif.latex?X_n&space;=&space;(0,&space;0)\&space;(n&space;>0)" title="X_n = (0, 0)\ (n >0)" align = "center"/> 을 만족하는 점들이다. 이들의 성질은 다음과 같이 정리해 볼 수 있다.

---
__성질 1.__  <img src="http://latex.codecogs.com/gif.latex?X_n&space;=&space;0" title="X_n = 0" align = "center"/>를 가정하고, <img src="http://latex.codecogs.com/gif.latex?d" title="d" /> 개의 좌표축들 중 <img src="http://latex.codecogs.com/gif.latex?i" title="i" /> 번째 좌표축의 + 방향으로 움직인 횟수를 <img src="http://latex.codecogs.com/gif.latex?x_i" title="x_i" />, - 방향으로 움직이는 것을 <img src="http://latex.codecogs.com/gif.latex?y_i" title="y_i" /> 로 놓으면,

<center> <img src="http://latex.codecogs.com/gif.latex?\sum_{i=1}^d&space;(x_i&space;&plus;&space;y_i)&space;=&space;n" title="\sum_{i=1}^d (x_i + y_i) = n" /> </center>

이고

<center> <img src="http://latex.codecogs.com/gif.latex?x_1&space;=&space;y_1,\&space;x_2&space;=&space;y_2,\&space;...,\&space;x_d&space;=&space;y_d" title="x_1 = y_1,\ x_2 = y_2,\ ...,\ x_d = y_d" /> </center>

이므로

<center> <img src="http://latex.codecogs.com/gif.latex?n&space;=&space;2&space;\sum_{i=1}^n&space;x_i&space;\implies&space;2&space;|&space;n" title="n = 2 \sum_{i=1}^n x_i \implies 2 | n" /> </center>

<img src="http://latex.codecogs.com/gif.latex?n" title="n" /> 은 짝수이다. 편의상 <img src="http://latex.codecogs.com/gif.latex?n&space;=&space;2m" title="n = 2m" /> 으로 놓자.

__성질 2.__ 두 개의 변수
<center> <img src="http://latex.codecogs.com/gif.latex?u_{2m}^d&space;:=&space;\Pr&space;\left(&space;X_{2m}&space;=&space;0&space;\right)" title="u_{2m} := \Pr \left( X_{2m} = 0 \right)" /> </center>

<center> <img src="http://latex.codecogs.com/gif.latex?f_{2m}^d&space;:=&space;\Pr&space;\left(&space;X_{2m}&space;=&space;0&space;\text{&space;and&space;}&space;X_{2k}&space;\neq&space;0&space;\text{&space;for&space;all&space;}0<&space;k&space;<&space;n\right)" title="f_{2m} := \Pr \left( X_{2m} = 0 \text{ and } X_{2k} \neq 0 \text{ for all }0< k < n\right)" /> </center>

를 정의하자. 즉, <img src="http://latex.codecogs.com/gif.latex?u_{2m}^d" title="u_{2m}" /> 은 단순히 <img src="http://latex.codecogs.com/gif.latex?X_{2m}&space;=&space;0" title="X_{2m} = 0" align ="center"/> 일 확률이고, <img src="http://latex.codecogs.com/gif.latex?f_{2m}^d" title="f_{2m}" align = "center"/> 은 <img src="http://latex.codecogs.com/gif.latex?2m" title="2m" /> 번째 움직임에서 __처음으로__ 원점을 찍을 확률이다. 수학적 귀납법에 의해 <img src="http://latex.codecogs.com/gif.latex?m&space;\geq&space;1" title="m \geq 1" /> 일 경우

<center>  <img src="http://latex.codecogs.com/gif.latex?u_{2m}^d&space;=&space;u_0^d&space;f_{2m}^d&space;&plus;&space;u_2^d&space;f_{2m-2}^d&space;&plus;&space;...&space;&plus;&space;u_{2m-2}^d&space;f_2^d&space;&plus;&space;u_{2m}^d&space;f_0^d" title="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" /> </center>

이 성립함을 알 수 있다. 편의상 <img src="http://latex.codecogs.com/gif.latex?u_0^d&space;=&space;1,&space;f_0^d&space;=&space;0" title="u_0^d = 1, f_0^d = 0" align = "center"/> 로 놓자.


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

### 2-1. 귀찮은 계산들...
[1차원](https://steemit.com/kr/@mathsolver/3-1) 에서의 경우와 마찬가지로 성질 2에서의 수열 관계식을 풀려면 생성함수를 이용하는 것이 가장 편리하다.

<center> <img src="http://latex.codecogs.com/gif.latex?\tilde{f}_{m}^d&space;=&space;f_{2m}^d" title="\tilde{f}_{m}^d = f_{2m}^d" /> </center>

그리고

<center> <img src="http://latex.codecogs.com/gif.latex?\tilde{u}_{m}^d&space;=&space;u_{2m}^d" title="\tilde{u}_{m}^d = u_{2m}^d" /> </center>

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

<center> <img src="http://latex.codecogs.com/gif.latex?\tilde{U}^d(x)&space;=&space;\sum_{m=0}^{\infty}&space;\tilde{u}_m^d&space;x^m,\&space;\tilde{F}^d(x)&space;=&space;\sum_{m=0}^{\infty}&space;\tilde{f}_m^dx^m" title="\tilde{U}(x) = \sum_{m=0}^{\infty} \tilde{u}_m^d x^m,\ \tilde{F}(x) = \sum_{m=0}^{\infty} \tilde{f}_m^dx^m" /></center>

를 살펴보면

<center> <img src="http://latex.codecogs.com/gif.latex?\begin{align*}&space;\tilde{U}^d(x)&space;&=&space;1&space;&plus;&space;\sum_{m=1}^{\infty}&space;\tilde{u}_m^d&space;x^m&space;\\&space;&=&space;1&space;&plus;&space;\sum_{m=1}^{\infty}&space;u_{2m}^d&space;x^m&space;\\&space;&=&space;1&space;&plus;&space;\sum_{m=1}^{\infty}&space;(u_{2m}^d&space;f_0^d&space;&plus;&space;...&space;&plus;&space;u_0^d&space;f_{2m}^d&space;)x^m&space;\\&space;&=&space;1&space;&plus;&space;\sum_{m=1}^{\infty}&space;(\tilde{u}_m^d&space;\tilde{f}_0^d&space;&plus;&space;...&space;&plus;&space;\tilde{u}_0^d&space;\tilde{f}_m^d)&space;x^m\\&space;&=&space;1&space;&plus;&space;\left(&space;\sum_{m=0}^{\infty}&space;\tilde{u}_m^d&space;x^m&space;\right&space;)&space;\left(&space;\sum_{m=0}^{\infty}&space;\tilde{f}_m^d&space;x^m&space;\right)\\&space;&=&space;1&space;&plus;&space;\tilde{F}^d(x)\tilde{U}^d(x)&space;\end{align*}" title="\begin{align*} \tilde{U}(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}(x)\tilde{U}(x) \end{align*}" /> </center>

임을 알 수 있다.

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

술에 취한 사람이 집으로 돌아오는 것은 다시말하면, 모든 짝수 <img src="http://latex.codecogs.com/gif.latex?2m" title="2m" /> 에 대해 <img src="http://latex.codecogs.com/gif.latex?f_{2m}^d" title="f_{2m}^d" align = "center" />의 합이 1이 됨을 의미한다. (각각의 <img src="http://latex.codecogs.com/gif.latex?f_{2m}^d" title="f_{2m}^d" align = "center"/> 는 확률을 의미하므로)

<center> <img src="http://latex.codecogs.com/gif.latex?\sum_{m=0}^{\infty}&space;f_{2m}^d&space;=&space;1&space;?" title="\sum_{m=0}^{\infty} f_{2m}^d = 1 ?" /> </center>

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

<center> <img src="http://latex.codecogs.com/gif.latex?\lim_{x&space;\rightarrow&space;1^-}&space;\tilde{F}^d&space;(x)" title="\lim_{x \rightarrow 1^-} \tilde{F}^d (x)" /> </center>

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

<center> <img src="http://latex.codecogs.com/gif.latex?\lim_{x&space;\rightarrow&space;1^-}&space;\tilde{F}^d(x)&space;=&space;\lim_{x&space;\rightarrow&space;1^-}&space;\frac{\tilde{U}^d(x)&space;-&space;1}{\tilde{U}^d(x)}" title="\lim_{x \rightarrow 1^-} \tilde{F}^d(x) = \lim_{x \rightarrow 1^-} \frac{\tilde{U}^d(x) - 1}{\tilde{U}^d(x)}" /> </center>

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

<center> <img src="http://latex.codecogs.com/gif.latex?\lim_{x&space;\rightarrow&space;1^-}&space;\tilde{U}^d(x)&space;=&space;\sum_{m=1}^{\infty}&space;u_{2m}^d" title="\lim_{x \rightarrow 1^-} \tilde{U}^d(x) = \sum_{m=1}^{\infty} u_{2m}^d" /> </center>

만을 조사하면 된다.

## 3. 결과

### 3-1. 1차원
[지난 번 포스팅](https://steemit.com/kr/@mathsolver/3-1)에서, <img src="http://latex.codecogs.com/gif.latex?d=1" title="d=1" align = "center"/> , 즉 1차원의 경우

<center> <img src="http://latex.codecogs.com/gif.latex?u_{2m}^d&space;=&space;{2m&space;\choose&space;m}2^{-2m}" title="u_{2m}^d = {2m \choose m}2^{-2m}" /> </center>

임을 보였다. 이 때에는 직접 <img src="http://latex.codecogs.com/gif.latex?f_{2m}&space;=&space;\frac{u_{2m}}{2m-1}\&space;(m&space;\geq&space;1)" title="f_{2m} = \frac{u_{2m}}{2m-1}\ (m \geq 1)" align = "center"/> 임을 이용하여 문제에 대한 답이 YES 임을 보였다.

### 3-2. 2차원
이제 <img src="http://latex.codecogs.com/gif.latex?u_{2m}^2" title="u_{2m}^2" align = "center"/> 를 구해보자.  <img src="http://latex.codecogs.com/gif.latex?d" title="d" /> 개의 좌표축들 중 <img src="http://latex.codecogs.com/gif.latex?i" title="i" /> 번째 좌표축의 + 방향으로 움직인 횟수를 <img src="http://latex.codecogs.com/gif.latex?x_i" title="x_i" />, - 방향으로 움직이는 횟수를 <img src="http://latex.codecogs.com/gif.latex?y_i" title="y_i" /> 로 놓으면,

<center> <img src="http://latex.codecogs.com/gif.latex?\begin{cases}&space;x_1&space;&plus;&space;y_1&space;&plus;&space;x_2&space;&plus;&space;y_2&space;=&space;2m&space;\\&space;x_1&space;=&space;y_1&space;\\&space;x_2&space;=&space;y_2&space;\\&space;x_1,&space;y_1,&space;x_2,&space;y_2&space;\in&space;\mathbb{Z}^{\geq&space;0}&space;\end{cases}" title="\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}" /> </center>

를 만족하고  

<center> <img src="http://latex.codecogs.com/gif.latex?\frac{(2m)!}{x_1!y_1!x_2!y_2!}" title="\frac{(2m)!}{x_1!y_1!x_2!y_2!}" /> </center>

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

<center> <img src="http://latex.codecogs.com/gif.latex?\begin{align*}&space;\sum_{x_1&space;&plus;&space;y_1&space;&plus;&space;x_2&space;&plus;&space;y_2&space;=&space;2m}&space;\frac{(2m)!}{x_1!y_1!x_2!y_2!}&space;&=&space;\sum_{x_1&space;&plus;&space;x_2&space;=&space;m}&space;\frac{(2m)!}{x_1!x_1!x_2!x_2!}&space;\\&space;&=&space;\sum_{x_1&space;=&space;0}^{m}&space;\frac{(2m)!}{x_1!(m-x_1)!x_1!(m-x_1)!}\\&space;&=&space;\sum_{x_1&space;=&space;0}^{m}&space;\frac{(2m)!}{m!m!}&space;\left(&space;\frac{m!}{x_1!&space;(m-x_1)!}&space;\right&space;)^2&space;\\&space;&=&space;\sum_{x_1=&space;0}^{m}&space;{2m&space;\choose&space;m}&space;{m&space;\choose&space;x_1}^2&space;\\&space;&=&space;{2m&space;\choose&space;m}&space;\sum_{x_1&space;=&space;0}^{m}&space;{m&space;\choose&space;x_1}^2&space;\\&space;&=&space;{2m&space;\choose&space;m}^2&space;\end{align*}" title="\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*}" /> </center>

가 나온다. 마지막 등식은 [이항정리의 성질](https://en.wikipedia.org/wiki/Binomial_coefficient#math_7)로 부터 유도됐다. 따라서,

<center> <img src="http://latex.codecogs.com/gif.latex?u_{2m}^2&space;=&space;4^{-2m}&space;{2m&space;\choose&space;m}^2&space;" title="u_{2m}^2 = 4^{-2m} {2m \choose m}^2 = (u_{2m}^1)^2" /> </center>

를 만족함을 알 수 있다. <img src="http://latex.codecogs.com/gif.latex?\tilde{F}(1-)" title="\tilde{F}(1-)" align = "center"/> 의 값이 존재하기 위해서는 <img src="http://latex.codecogs.com/gif.latex?\tilde{U}^2(1-)&space;=&space;\infty" title="\tilde{U}(1-) = \infty" align = "center"/> 여야 한다. 그런데 [스털링 근사식](https://en.wikipedia.org/wiki/Binomial_coefficient#Bounds_and_asymptotic_formulas)으로 부터 적당한 자연수 <img src="http://latex.codecogs.com/gif.latex?N,&space;K&space;(>0)" title="N, K (>0)" align = "center" /> 에 대해

<center>  <img src="http://latex.codecogs.com/gif.latex?{2m&space;\choose&space;m}&space;\geq&space;K&space;\frac{4^m}{\sqrt{\pi&space;m}}" title="{2m \choose m} \geq K \frac{4^m}{\sqrt{\pi n}}" /> </center>

이 성립하고, 따라서

<center> <img src="http://latex.codecogs.com/gif.latex?\begin{align*}&space;\tilde{U}^2(1-)&space;=&space;\sum_{m=0}^{\infty}&space;u_{2m}^2&space;&=&space;\sum_{m=0}^{N-1}u_{2m}^2&space;&plus;&space;\sum_{m&space;=&space;N}^{\infty}&space;u_{2m}^2&space;\\&space;&\geq&space;\sum_{m=0}^{N-1}u_{2m}^2&space;&plus;&space;\frac{K^2}{\pi}&space;\sum_{m=N}^{\infty}&space;\frac{1}{m}&space;>&space;\infty&space;\end{align*}" title="\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}{\pi} \sum_{m=N}^{\infty} \frac{1}{m} > \infty \end{align*}" /> </center>

이 성립한다. 즉

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

### 3-3. 3차원 - [3]

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

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

이에 대한 답을 하기 위해서는 <img src="http://latex.codecogs.com/gif.latex?u_{2m}^3" title="u_{2m}^3" align = "center"/> 를 구하여야 한다.

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

<center> <img src="http://latex.codecogs.com/gif.latex?u_{2m}^3&space;=&space;(2\cdot&space;3)^{-2m}&space;{2m&space;\choose&space;m}&space;\sum_{x_1&space;&plus;&space;x_2&space;&plus;&space;x_3&space;=&space;m}&space;\left(&space;\frac{m!}{x_1!x_2!x_3!}&space;\right&space;)^2" title="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" /></center>

[다항정리](https://en.wikipedia.org/wiki/Multinomial_theorem#Sum_of_all_multinomial_coefficients)에 의해

<center> <img src="http://latex.codecogs.com/gif.latex?3^{-m}\sum_{x_1&space;&plus;&space;x_2&space;&plus;&space;x_3&space;=&space;m}&space;\left(&space;\frac{m!}{x_1!x_2!x_3!}&space;\right&space;)^2&space;=1" title="3^{-m}\sum_{x_1 + x_2 + x_3 = m} \left( \frac{m!}{x_1!x_2!x_3!} \right )^2 =1" /></center>

이므로

<center> <img src="http://latex.codecogs.com/gif.latex?\sum_{x_1&space;&plus;&space;x_2&space;&plus;&space;x_3&space;=&space;m}&space;\left(&space;\frac{m!}{x_1!x_2!x_3!}&space;\right&space;)^2&space;\leq&space;\max_{x_1,x_2,&space;x_3}&space;\frac{m!}{x_1!x_2!x_3!}" title="\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!}" /></center>
가 성립한다.

다항정리의 계수가 최대가 되려면, 모든 <img src="http://latex.codecogs.com/gif.latex?x_1,&space;x_2,&space;x_3" title="x_1, x_2, x_3" align = "center"/> 가 균등하게 <img src="http://latex.codecogs.com/gif.latex?m/3" title="m/3" align = "center"/>에 최대한 가까이 위치한 정수여야 한다. 스털링 근사를 적절히 활용하면

<center> <img src="http://latex.codecogs.com/gif.latex?\begin{align*}&space;u_{2m}^3&space;&\leq&space;2^{-2m}3^{-m}&space;{2m&space;\choose&space;m}&space;\frac{m!}{(m/3)!(m/3)!(m/3)!}&space;\\&space;&\sim&space;\frac{1}{\sqrt{\pi&space;m}}&space;3^{-m}&space;\frac{\sqrt{2\pi&space;m}(m/e)^m}{\prod_{i=1}^3&space;\sqrt{2\pi&space;m/3}&space;(m/3e)^{m/3}}&space;\\&space;&\sim&space;K&space;\frac{m^{m-1/2}}{m^{1/2&space;&plus;&space;3/2&space;&plus;&space;m}}&space;=&space;K/m^{3/2}&space;\end{align*}" title="\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*}" /></center>

이고 [<img src="http://latex.codecogs.com/gif.latex?p" title="p" />- 급수 판정법](https://en.wikipedia.org/wiki/Harmonic_series_(mathematics)#P-series) 에 의해 <img src="http://latex.codecogs.com/gif.latex?\tilde{U}(1-)&space;=&space;\sum_{m=0}^{\infty}&space;u_{2m}^3" title="\tilde{U}(1-) = \sum_{m=0}^{\infty} u_{2m}^3" align = "center" /> 은 수렴한다. 즉

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

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

사실, 위의 식에서 <img src="http://latex.codecogs.com/gif.latex?3&space;\rightarrow&space;d" title="3 \rightarrow d" /> 로 바꾸면 <img src="http://latex.codecogs.com/gif.latex?d&space;\geq&space;3" title="d \geq 3" align = "center" /> 에서의 일반화를 시킬 수 있다. 구해보면

<center> <img src="http://latex.codecogs.com/gif.latex?\begin{align*}&space;u_{2m}^d&space;&\leq&space;2^{-2m}d^{-m}&space;{2m&space;\choose&space;m}&space;\frac{m!}{(m/d)!(m/d)!...(m/d)!}&space;\\&space;&\sim&space;\frac{1}{\sqrt{\pi&space;m}}&space;d^{-m}&space;\frac{\sqrt{2\pi&space;m}(m/e)^m}{\prod_{i=1}^d&space;\sqrt{2\pi&space;m/d}&space;(m/de)^{m/d}}&space;\\&space;&\sim&space;K&space;\frac{m^{m&plus;1/2}}{m^{1/2&space;&plus;&space;d/2&space;&plus;&space;m}}&space;=&space;K/n^{d/2}&space;\end{align*}" title="\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*}" /> </center>

가 된다. [<img src="http://latex.codecogs.com/gif.latex?p" title="p" />- 급수 판정법](https://en.wikipedia.org/wiki/Harmonic_series_(mathematics)#P-series) 에 의해 <img src="http://latex.codecogs.com/gif.latex?d/2&space;>&space;1&space;\implies&space;d&space;>&space;2&space;\implies&space;d&space;\geq&space;3" title="d/2 > 1 \implies d > 2 \implies d \geq 3" align = "center"/> 의 경우 <img src="http://latex.codecogs.com/gif.latex?\tilde{U}(1-)&space;=&space;\sum_{m=0}^{\infty}&space;u_{2m}^d" title="\tilde{U}(1-) = \sum_{m=0}^{\infty} u_{2m}^d" align = "center"/> 은 수렴한다.

따라서 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;
```
<center> <img src = "https://i.imgsafe.org/e8/e8b35a8d50.png" /> </center>

<center> <img src ="https://i.imgsafe.org/e8/e8b35a653b.png" /></center>


## 5. 결론

1. 1차원 (수직선) 과 2차원 (좌표평면)에서 무작위 행보 운동을 하는 물체는 언젠가는 시작점 (원점)으로 회귀한다.

2. 3차원 이상에서의 무작위 행보는 회귀를 담보할 수 없다

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. 추신
다음 이야기 부터는 좀 더 쉽고 재밌는 주제로 써보겠습니다.