[수학 이야기 #3-1] 술에 취한 사람은 집에 들어갈 수 있을까? 무작위 행보 (random walk) [1편]
[1]
술에 취한 사람이 돌아오는 이유? [1편]
우스갯소리로 하는 말이지만, 이것을 수학적으로 분석해서 어느정도 (?) 맞는 말 임을 보일 수 있다.
1. 무작위 행보 (Random Walk)란 ? - [2]
어떠한 물체가 유클리드 공간 상 원점 에서 시작해서, 다음과 같은 규칙으로 움직인다 생각해보자. 번째 단계에서의 물체의 위치를 라 하면,
Step 1. (시작점)
Step 2. 단위 벡터
에 대해,
일 확률이 모든 에 대해
로 동일하게 주어짐.
예를 들어서
차원이라면, 수직선 위 원점에서 시작하여 오른쪽 또는 왼쪽으로 (각각 확률 1/2을 부여) 움직이는 운동을 말한다.
차원 이라면, 원점에서 시작하여 동, 서, 남, 북 으로 (각각 확률 1/4을 부여) 움직이는 운동을 말한다.
마지막으로 차원 이라면, 원점에서 시작하여 동, 서, 남, 북, 상, 하 방향 으로 (각각 확률 1/6을 부여) 움직이는 운동을 말한다.
즉 원점에서 시작한 운동은 항상 좌표들이 정수인 격자점 만을 거친다고 보는 것이다. 그렇다면 이 모델이 술 취한 사람이 다시 집으로 돌아오는 것과 무슨 연관이 있을까?
2. 1차원에서의 무작위 행보
일단 가장 간단한 1차원에서의 Random Walk를 살펴보자. 다음은 까지 Python을 이용하여 Random Walk를 구현한 뒤, 각 단계에서의 좌표값을 조사한 예시이다.
import matplotlib.pyplot as plt
import numpy as np
def random_walk_1D(n):
elements = [1, -1]
probabilities = [0.5, 0.5]
x = [0]
for i in range(1, n + 1):
y = np.random.choice(elements, 1, p = probabilities)
x.append(x[i-1] + y)
return x
#----------------------#
n = 100
N = [i for i in range(n+1)]
plt.plot(N, random_walk_1D(n))
plt.grid(axis = 'y')
plt.xlabel('n')
plt.ylabel('$X_n$')
plt.show()
술에 취한 사람이 집으로 돌아온다는 것은 Random Walk를 시행하는 도중 이 되는 상황을 의미하므로, 이 발생하는 상황에 대한 조사를 시행하면 될 것이다.
2-1. 언제 원점으로 돌아오는가?
번의 시행 중 오른쪽으로 간 횟수를 , 왼쪽으로 간 횟수를 로 놓자. 만약 라면, 다음을 만족해야 한다.
따라서 이 짝수일 때만 이 될 수 있다.
2-2. 일 확률은?
이제 짝수 이 주어졌다고 가정하고, 일 확률 을 구해보자. 이는 바로 위 Section 2-1에서 알 수 있듯이
이므로 으로 놓는다면
이 나온다. (편의상 로 놓자.)
2-3. 처음으로 원점을 찍는 경우? - [3]
Section 2-1의 예시로 돌아가보자. 그래프를 보면 100번의 시행에서 원점으로 되돌아 가는 상황은 정확히 (초기값을 제외하면) 7번 나왔다.
술에 취한 사람이 집을 잘 찾아가놓고 6번이나 다시 집을 나온다?
우스꽝스러운 상황이 아닐 수 없다.
집을 한번 들어가면 그걸로 끝이지 다시 집을 나온 뒤 되돌아감을 반복하는 상황은 우리가 원하던 바가 아니다. 따라서 새로운 변수를 정의해야한다. (짝수)에 대해, 다음과 같이 정의한다.
즉 보다 작은 경우 원점으로 되돌아가는 일이 없어야 한다. 편의 상 로 놓고, 와 간의 관계를 알아보자.
은 원점에서 시작해 를 만족하는 모든 Random Walk 경로의 수를 뜻한다. 이러한 경로들은 처음으로 원점을 찍는 위치 에 의해 분할 (partition) 된다. 에서 처음으로 원점을 찍는 경로의 수는 정의에 의해
를 만족한다.
를 모두 합하면,
3. 생성함수를 이용하여 분석하기
3-1. 생성함수와 이항정리
우리가 2-2에서 정의한 과 2-3에서 정의한 을 수열
로 본다면, 이들의 생성함수는 다음과 같다.
다항식의 코시곱을 떠올려보면 Section 2-3에서 나온 식을 적용해볼 수 있다.
따라서 을 만족한다. 이므로 이항정리 (Binomial Theorem) - [4] 에 의해
이 성립한다. 따라서
이다. 함수식에서 직접 계산을 통해
임을 알 수 있다.
3-2. 결과
다시 돌아가서 우리의 원래 문제로 가보자. 술에 취한 사람이 집에 들어오면 다시 나가는 경우를 배제하였으므로,
술에 취한 사람이 반드시 집으로 다시 돌아오는가?
에 대한 답은 확률의 무한 합
을 증명하는 것과 동치이다! 먼저, 이고 부분합들은 을 상한으로 가지니 (bounded above by 1) 수렴함은 분명하다. 스털링 근사 [5] 에 의해 충분히 큰 자연수 와 상수 에 대해
이 성립하므로
무한합은 수렴한다.
따라서, 생성함수의 극한에 대입하면
이 나온다!
4. 결론
무작위 행보 (random walk) 이론을 대입해서 나온 결론은 다음과 같다. 원점에 위치한 집을 나온 상태에서 술에 취한 사람이 언젠가 다시 집으로 돌아갈 확률은 1차원 의 경우 1이다. 즉 언젠가는 반드시 집으로 돌아간다. 물론 이를 왜곡해서 해석하면 안된다.
가령, 우리가 random walk의 시행 횟수를 정해놓았을 경우, 그 시행의 횟수 내에서 반드시 원점으로 돌아감을 보장하지는 않는다. 시행의 횟수가 유한하지 않고, 무한히 늘릴 경우 (즉 ) 에만 해당함에 주의하자. 물론 현실에서는 계속 돌아다니다 보면 동사하거나 누군가가 집으로 데려다 주겠지만 어쨌든 이렇다는 거다 ㅋㅋ.
5. 다음?
현실에서의 술에 취한 사람은 땅 위를 걸어다니므로 2차원에서의 무작위 행보를 분석해야 한다. 다음 이야기 에서는 2차원에서의 무작위 행보를 분석하여, 실제로 이 경우에도 반드시 집에 들어갈 수 있음을 보이겠다.
6. 출처/인용
[1] http://mathsurvey.org/the-mathematics-of-the-drunken-walk.html (사진)
[2] https://services.math.duke.edu/~rtd/PTE/PTE4_1.pdf (page 163 - 164)
[3] http://www.dartmouth.edu/~chance/teaching_aids/books_articles/probability_book/Chapter12.pdf
[4] https://en.wikipedia.org/wiki/Binomial_theorem#Newton's_generalized_binomial_theorem
[5] https://en.wikipedia.org/wiki/Binomial_coefficient#Bounds_and_asymptotic_formulas
나만 이해 못 하는거 아니라고 해주세요
이제부터 쉬운주제로 바꿔보려구요. 재밌는거 찾아서 올려보겠습니다..
헉 이런 내용인줄 몰랐네요. 수알못은 웁니다.😭
수알못은 웁니다.
근데.. 집에서 술먹고 나가는 경우이군요.
밖에서 술먹으면.. 반드시 그 술집을 가게 될텐데.. 그 술집은 돈 많이 벌겠네요.. ^^
태풍이 오고 있습니다!
ㅋㅋㅋㅋ 어렵네요
이해 못하지만 술취해도 집에 들어가는건 맞아요 - 나도 집에는 잘가니까ㅎ