[1]

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

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

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

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

초기 좌표:
단계 이후의 좌표를 이라 놓으면, 다음과 같은 도식에 따라 이 결정됨을 알 수 있다.

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

지난 포스팅의 Section 2에서 다루었듯이 우리가 관심있는 점들은 을 만족하는 점들이다. 이들의 성질은 다음과 같이 정리해 볼 수 있다.

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

이고

이므로

은 짝수이다. 편의상 으로 놓자.

성질 2. 두 개의 변수

를 정의하자. 즉, 은 단순히 일 확률이고, 은 번째 움직임에서 처음으로 원점을 찍을 확률이다. 수학적 귀납법에 의해 일 경우

이 성립함을 알 수 있다. 편의상 로 놓자.

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

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

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

그리고

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

를 살펴보면

임을 알 수 있다.

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

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

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

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

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

만을 조사하면 된다.

3. 결과

3-1. 1차원

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

임을 보였다. 이 때에는 직접 임을 이용하여 문제에 대한 답이 YES 임을 보였다.

3-2. 2차원

이제 를 구해보자. 개의 좌표축들 중 번째 좌표축의 + 방향으로 움직인 횟수를 , - 방향으로 움직이는 횟수를 로 놓으면,

를 만족하고

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

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

를 만족함을 알 수 있다. 의 값이 존재하기 위해서는 여야 한다. 그런데 스털링 근사식으로 부터 적당한 자연수 에 대해

이 성립하고, 따라서

이 성립한다. 즉

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

3-3. 3차원 - [3]

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

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

이에 대한 답을 하기 위해서는 를 구하여야 한다.

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

다항정리에 의해

이므로

가 성립한다.

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

이고 - 급수 판정법 에 의해 은 수렴한다. 즉

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

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

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

가 된다. - 급수 판정법 에 의해 의 경우 은 수렴한다.

따라서 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;