랜덤 워크 문제 풀이

랜덤 워크(Random Walk)란 임의의 확률에 따라 어떤 행동을 하는지에 대한 알고리즘?을 의미한다.

예를 들어 계단에서 친구와 가위바위보를 해서 이긴 사람은 올라가고 지면 내려가는 것도 랜덤워크이고

동전 뒤집기를 해서 앞면이 나오면 승점을 가져가고 지면 못가져가는 놀이 등 나름 익숙한 알고리즘이다.

 

어려운 알고리즘은 아니고 나름 local optima문제도 해결할 순 있지만 더 좋은 풀이가 많아서 많이 사용될 것 같진 않다.

 

그럼 간단한 문제를 풀어보자

 

Consider a random walk on a path with vertices numbered 1, 2, . . . , n from
left to right. At each step, we flip a coin to decide which direction to walk, moving
one step left or one step right with equal probability. The random walk ends when
we fall off one end of the path, either by moving left from vertex 1 or by moving
right from vertex n. Prove that the probability that the walk ends by falling off the
right end of the path is exactly 1/(n + 1) if we start at vertex 1. (Use recursion)

요약해보자면 아래 그림에서

사람이 앞, 뒤로 갈 확률은 각 1/2이고 0번 위치에 가면 낭떠러지이고 n+1위치에 가면 목표도착인 것이다. 이때 목표지점에 도착할 확률이 1/(n+1)임을 증명하는 것이 문제이다. 여기서 재귀를 사용하라고 한 점도 잊지말자. 따라서 풀이도 수학적 귀납법을 이용할 것이다.

---

P(k)를 k번째 위치에서 목표지점에 도착할 확률이라 정의하겠다.

먼저 1번 위치에서는 오른쪽으로만 갈 수 있으므로 아래식이 성립한다.

P(1) = 1/2 * P(2)

 

2번 위치에선 양쪽으로 움직일 수 있으므로 위 식을 이용해서 한번 더 표현하면

 

P(1) = 1/2 * P(2)

= 1/2 ( 1/2*P(1) + 1/2*P(3) )

= 1/4*P(1) + 1/4*P(3)

so, P(1) = 1/3 * P(3)

 

p1,p2,p3의 관계를 이용하여 일반화해보자

 

n=k일 때, P(1) = 1/(k-1)*P(k-1) = 1/k*P(k)라고 가정하자

1/k*P(k) = 1/k( 1/2*P(k-1) + 1/2*P(k+1)) = 1/(k-1)*P(k-1)

 

가운데, 오른쪽 식을 정리하면

 

1/(k-1) * P(k-1) = 1/(k+1) * P(k+1)

∴ P(1) = 1/(k+1) * P(k+1)

 

k=n일 때 p(n+1)=1이므로 결국 문제에서 원하는 데로 나왔다.