도박꾼의 파산문제(The Gambler's Ruin Problem)

문제

두사람 A와 B가 동전 하나를 계속 던지는 게임을 한다. 동전을 던질 때마다 앞면이 나오면, A가 B로부터 1원을 받는 반면, 뒷면이 나오면 A가 B에게 1원을 준다. 그들 중 한사람이 돈이 없어질 때까지 이 게임을 계속한다. 동전을 계속 던지는 시행들이 독립이고 각 시행에서 앞면이 나올 확률이 p이면, A가 i원, B가 (N-i)원을 가지고 시작하여 A가 모든 돈을 다 딸 확률은 얼마인가?

풀이1

E를 A가 i원, B가 N-i원을 가지고 시작하여 "A가 모든 돈을 다 딸 사건"이라고 하고, 이 확률은 A가 최초에 가진 돈과 관계 있기 때문에 Pi=P(E)라 하자. P(E)는 처음 동전을 던져 나타난 결과를 조건으로 하여 다음과 같이 나타낼 수 있다. 

여기서 H는 처음 던진 동전이 앞면일 사건이다. 만일 처음 동전을 던져 앞면이 나왔다면, 최초의 게임 후에는 A는 i+1원, B는 N-(i+1)원을 가지게 된다. 계속되는 시행들은 앞면이 나올 확률이 p로 동일하고 독립이므로, 첫 게임 이후에 A가 모든 돈을 딸 확률은 이러한 게임에서 A가 최초에 i+1원, B가 N-(i+1)원을 가지고 시작하여 A가 모든 돈을 딸 확률과 같다. 그러므로, q=1-p라 하면 다음 식을 얻는다.

명백한 조건들 P0=0, PN=1을 사용하여 위 식을 풀 때, p+q=1이므로 이 식은 다음과 같다. (좌항에 p+q를 곱한다)

P0=0이므로, 위 식으로부터 첫번째 단계를 유도할 수 있다., 그리고 최초 i-1개 항을 더하여 두번째 단계를 유도하며, PN=1이라는 사실로 세번째 단계를 유도할 수 있다.

Qi를 A가 i원, B가 N-i원으로 게임을 시작하여 B가 모든 돈을 딸 확률이라 하자. 그러면 이들의 대칭성에 의해 p와 q, 그리고 i와 N-i를 바꾸면 첫번째 단계를 유도할 수 있으며, q=1/2은 p=1/2와 같기 때문에, q가 1/2이 아닐경우 다음과 같이 두번째 단계를 유도할 수 있다. 

위 결과는  p=q=1/2일 때에도 역시 성립되므로 Pi+Qi=1이다. 말하자면, 이 식은 A나 B둘중 어느 한사람이 모든 돈을 다 따서 게임이 끝날 확률이 1이라는 것이다. 즉, A가 항상 1원과 N-1원사이의 돈을 가지고 게임을 무한히 계속할 확률은 0이라는 것이다.이 도박 게임의 가능한 결과는 2가지가 아니라 3가지이므로 주의해야 한다. A가 모든 돈을 다 따거나, B가 모든 돈을 다 따거나, 아니면 우승자 없이 영원히 계속되는 것이다. 방금 세번째 경우가 발생할 확률이 0임을 보였다.

위 결과의 수칙적인 예로, A가 원, B가 10원의 돈을 가지고 게임을 시작했다면, p=1/2일 때, A가 이길 확률은 1/3인 반면, p가 0.6일 때는 약 0.87이다. 

또한 위의 결과를 무한히 반복하여 생각한다면, 아래의 결과를 얻을 수 있다.

위 수식을 해석하자면 다음과 같다. 

1) B의 돈이 엄청나게 많은 경우(예를 들면, 카지노에서 도박을 하는경우), A의 승률이 B와 같거나 또는 모자란다면, A는 언젠가는 반드시 빈털터리가 된다(A가 얼마를 갖고 시작하든 관계없이 유한한 액수를 갖고 시작한다면)

2) A의 승률이 1/2보다 크면, 많은 돈을 갖고 시작할수록 유리하다. 예를 들어 p=0.51, q=0.49인 경우에, A가 처음 갖고 시작하는 액수 i가 10원인 경우와 100원인 경우를 비교하면, A가 빈털터리가 될 확률은 각각 (0.49/0.51)^10=0.67, (0.49/0.51)^100=0.018이다. 

풀이2

차등방정식에 대한 풀이는 미분방정식의 풀이와 비슷하다. 

<생략>

풀이3

마르코프 모델을 사용하여 게임의 진행을 나타낼 수 있다. 그래프상에 A가 가질 수 있는 돈의 액수를 나타내는 n+1개의 상태가 나타나있다. 즉, A가 k원을 가지고 있는 경우 상태는 k에 있게 되는 것이다. 1~(n-1)까지의 상태는 transient state이며, (게임의 종료를 의미하는) 0과 n상태는 absorbing state이다. Pj를 j원을 가진 상태에서 시작하여 n원을 갖게 될 확률이라 가정해보자, 이 경우, P0=0, Pn=1임을 알 수 있다. 

만약 A가 1원을 가진 상태에서 q의 확률로 '1원을 잃어' 바로 파산할 경우와, p의 확률로 '1원을 얻어' 2원을 가지게 될 경우를 생각해볼 수 있다(이때 결국 n원을 갖게 될 확률은 P2가 된다). 따라서 P1=pP2이다. 이와 비슷하게, 만약 (n-1)원을 가지고 있을 때, p의 확률로 n원을 가지게 되어 이기게 되거나, 혹은 q의 확률로 (n-2)원을 가지게 되는 경우를 생각해 볼 수 있는데, 이때 (n-2)원을 가지고 있는 상태에서 n원을 가지게 될 확률은 P(n-2)이므로 P(n-1)은 1원을 얻어 n원을 갖게될 확률과 1원을 잃어 (n-2)원을 가진 상태에서 결국 n원을 가지게 될 확률의 합, 즉 P(n-1)=p+qP(n-2)이다. 즉 다음과 같이 나타낼 수 있다.

따라서 다음과 같이 Pj를 나타낼 수 있다,

참고로 위 식 중간에 아래의 과정이 생략되어 있다.

위의 식을 예를들어 설명해보자. A가 13원, B가 87원을 가지고 있을 때, 만약 공정하게(양면이 나올 확률이 각각 1/2일 경우) 동전 던지기 게임을 진행한다면(즉 ρ=1), 이 게임에서 A가 이길 확률은 13/(13+87)=0.13인 것이다. 1번 풀이와 마찬가지로, 만약 B의 돈이 엄청나게 많은 경우(lim n->∞) A가 이길 확률은 0으로 수렴한다(결국 무조건 돈을 잃게 된다)는 결론을 낼 수 있다.

출처 : 확률의 입문, The Gambler's Ruin