도박꾼의 파산(Gambler's ruin)

가진 돈 $k =$ 닢으로 시작해 목표 $N =$ 닢을 노립니다. 한 판마다 확률 $p =$ 로 한 닢을 따고, $1-p$로 한 닢을 잃습니다. 돈이 0이 되면 파산, N이 되면 목표를 이루고 그만둡니다. 돈의 변화는 양 끝에 벽이 있는 무작위 행보⁠(random walk)⁠입니다. 파스칼과 페르마 사이에서 다루어진 문제로 알려져 있고, 네덜란드의 하위헌스가 1657년, 처음 출판된 확률 책으로 꼽히는 『주사위 놀이의 계산에 관하여』의 마지막 문제로 실었습니다. 다시 하기

같은 게임을 1000번 해 보니 목표에 닿은 비율은 , 이론값은 입니다. 평균⁠(mean)⁠ 판 만에 끝났습니다(이론 판).

공정한 게임. $p = \tfrac12$이면 답은 단순합니다: $P_k = k/N$. 공정한 게임에서는 가진 돈의 기댓값⁠(expected value)⁠이 판마다 그대로이므로, 게임이 끝났을 때의 기댓값도 k입니다. 이렇게 말할 수 있는 것은 게임이 확률 1로 유한한 판 안에 끝나고 돈이 늘 0과 N 사이에 머물기 때문입니다. 멈추는 규칙이 아무것이나 되는 것은 아니어서, 벽이 없이 '1닢 앞설 때까지' 하는 게임이라면 이 논법이 통하지 않습니다. 끝나는 순간의 돈은 N(확률 $P_k$) 아니면 0이니 $N P_k = k$입니다. 첫 판의 결과로 나누어 생각해도(조건부 확률⁠, conditional probability⁠) 같은 답이 나옵니다. $P_k = p\,P_{k+1} + (1-p)\,P_{k-1}$라는 점화식⁠(recurrence relation)⁠이고, $p = \tfrac12$이면 각 값이 양옆의 평균이라 그래프가 직선입니다. 이 식 N−1개를 모으면 연립일차방정식⁠(system of linear equations)⁠이 됩니다.

조금만 불리해도. $p \ne \tfrac12$이면 $P_k = r^k$ 꼴을 넣어 풀 수 있습니다. 비가 $r = (1-p)/p$인 등비수열⁠(geometric progression)⁠이 해가 되고, 두 벽의 조건을 맞추면 위의 공식이 나옵니다. 카지노처럼 $p = 0.49$인 게임에서 50닢을 100닢으로 불릴 확률은 공정할 때의 50%가 아니라 약 12%입니다. 판이 길어질수록 작은 불리함이 큰 수의 법칙⁠(law of large numbers)⁠대로 차곡차곡 쌓이기 때문입니다. 공정한 게임이라도 상대가 한없이 부자라면($N \to \infty$) $k/N \to 0$이라서, 결국 파산할 확률이 1입니다.

얼마나 오래 걸리나. 끝날 때까지의 평균 판 수 $D_k$도 첫 판으로 나누면 $D_k = 1 + \tfrac12(D_{k+1} + D_{k-1})$입니다. 양옆 평균보다 늘 1만큼 큰 수열은 포물선⁠(parabola)⁠이고, 벽에서 0이 되는 포물선은 $k(N-k)$입니다. 50닢으로 100닢을 노리는 공정한 게임은 평균 2500판이 걸립니다.

이어지는 곳. 가진 돈을 상태로 보면 다음 판의 돈은 지금 돈에만 달려 있으니 이 과정은 마르코프 연쇄⁠(Markov chain)⁠이고, 0과 N은 한 번 들어가면 다시 나오지 않는 흡수 상태입니다. "각 값이 양옆의 평균"이라는 조건은 양 끝 온도를 고정한 막대가 열방정식⁠(heat equation)⁠에서 오래 지나 도달하는 직선 온도 분포와 같은 방정식이고, $r^k$를 넣어 푸는 요령은 선형 미분방정식⁠(linear differential equation)⁠에 $e^{\lambda t}$를 넣어 푸는 것과 같은 발상입니다.