도박꾼의 파산 문제
문제
도박꾼의 파산 문제는 랜덤워크의 일종으로 두 명의 플레이어가 한정된 돈을 걸고 둘 중 하나가 파산할 때까지 반복하는 게임을 상정한다.
당신이 플레이어 중 하나라고 한다면, 위 도식과 같이 당신이 이길 확률이 $p$ 고 질 확률이 $(1-p)$ 라고 할 수 있다. 상태 $0$ 은 당신이 파산한 경우고, 상태 $N$ 은 당신이 상대의 돈을 모두 딴 경우로 더 이상 게임을 반복하지 않는다. 이는 $0$ 과 $N$ 에서 자기 자신으로 가는 확률이 $1$ 이라는 것으로 표현되어있다. $i$ 는 게임을 시작할 때 당신의 소지금이라고 볼 수 있겠다.
기본적으로 $\displaystyle p \ne {{1} \over {2}}$ 이거나 $\displaystyle i \ne {{N} \over {2}}$ 이라면 게임은 공평하지 않다. 이 게임은 한 명이 파산을 할 때까지 끝나지 않으며, 수식적으로 관심을 가질만한 질문은 ‘당신이 $i$ 만큼의 돈을 가지고 시작했을 때 상대를 파산시키고 이길 확률이 얼마나 되는가’다. 다만 그 이전에 ‘왜 이렇게 불공평하고 극단적인 게임을 하는가’라는 질문을 할 수 있다.
하지만 이것은 어디까지나 도박꾼의 파산 문제를 게임으로만 보았을 때 할 수 있는 질문이고, 현실 속에선 오히려 공평한 싸움을 찾아보는 게 더 어렵다. 이는 자본이 많은 대기업과 법의 보호를 받는 소상공인의 대결로 볼 수도 있고, 같은 자원을 생산하는 국가끼리의 총력전으로 볼 수도 있다. 불리한 싸움이라도 해야할 때가 있으며, 이 때의 승산이 궁금한 것은 당연한 일이다.
다시 수식으로 돌아와서, 우리의 관심사는 ‘초기자본이 $i$ 이고 승률이 $p$ 일 때, 상대방을 파산시키고 모든 돈을 가져올 확률’ $P_{i}$ 를 계산하는 것이다. 편의상 ‘상대방을 파산하고 모든 돈을 가져오는 상황’을 ‘우승’이라 부르겠다.
풀이
$P_{i}$ 의 정의에서 $P_{0} = 0$ 이고 $P_{N} = 1$ 이다.
Part 1.
$P_{ i }$ 는 $p$ 의 확률로 첫번째 게임에서 승리하고 $( i+1 )$ 에서 새로운 시작을 해서 우승할 확률과 $(1-p)$ 의 확률로 첫번째 게임에서 패배하고 $( i-1 )$ 에서 새로운 시작을 해서 우승할 확률을 더한 것으로 볼 수 있다. 수식으로는 $P_{ i } = p P_{ i + 1 } + (1 - p ) P_{ i - 1 }$ 이 된다. 여기서 좌변을 $p$ 와 $(1-p)$ 로 찢어내면 $$P_{ i } = (p + 1 - p ) P_{i} = p P_{i} + (1 - p) P_{i}$$ 이므로 $$ \begin{align*} & P_{ i } =& p P_{ i + 1 } + (1 - p ) P_{ i - 1 } \\ \implies& p P_{i} + (1 - p) P_{i} &= p P_{ i + 1 } + (1 - p ) P_{ i - 1 } \\ \implies& p \left( P_{i+1} - P_{i} \right) =& (1 - p) \left( P_{i} - P_{i-1} \right) \\ \implies& \left( P_{i+1} - P_{i} \right) =& {{1-p} \over {p}} \left( P_{i} - P_{i-1} \right) \end{align*} $$
재귀적으로 풀어내면 $\displaystyle P_{i} - P_{i-1} = \left( {{1-p} \over {p}} \right)^{i-1} \left( P_{1} - P_{0} \right)$ 인데, $P_{0} = 0$ 이므로 $$\displaystyle P_{i} - P_{i-1} = \left( {{1-p} \over {p}} \right)^{i-1} P_{1}$$
Part 2.
$$P_{1} - P_{0} = \left( {{1-p} \over {p}} \right)^{0} P_{1} \\ P_{2} - P_{1} = \left( {{1-p} \over {p}} \right)^{1} P_{1} \\ P_{3} - P_{2} = \left( {{1-p} \over {p}} \right)^{2} P_{1} \\ P_{i} - P_{i-1} = \left( {{1-p} \over {p}} \right)^{i-1} P_{1} $$
위의 식들을 각 변끼리 더하면 좌변은 $$( P_{1} - P_{0} ) + ( P_{2} - P_{1} ) + \cdots + ( P_{i} - P_{i-1} ) = P_{i} - P_{0} = P_{i}$$ 우변은 $$\displaystyle \sum_{k=1}^{i} \left( {{1-p} \over {p}} \right)^{k-1} P_{1} = {{ 1 - \left( {{1-p} \over {p}} \right)^{i} } \over {1 - \left( {{1-p} \over {p}} \right) }} P_{1}$$ 정리하면 $$\displaystyle P_{i} = {{ 1 - \left( {{1-p} \over {p}} \right)^{i} } \over {1 - \left( {{1-p} \over {p}} \right) }} P_{1}$$
Part 3.
$P_{N} = 1$ 이므로 $$ 1 = P_{N} = {{ 1 - \left( {{1-p} \over {p}} \right)^{N} } \over {1 - \left( {{1-p} \over {p}} \right) }} P_{1} $$ 따라서 $$ P_{1} = {{1 - \left( {{1-p} \over {p}} \right) } \over { 1 - \left( {{1-p} \over {p}} \right)^{N} }} $$ 위의 Part 2.에서 얻은 식에 $P_{1}$ 을 대입함으로써 $$ P_{i} = {{ 1 - \left( {{1-p} \over {p}} \right)^{i} } \over {1 - \left( {{1-p} \over {p}} \right) }} \cdot {{1 - \left( {{1-p} \over {p}} \right) } \over { 1 - \left( {{1-p} \over {p}} \right)^{N} }} = {{ 1 - \left( {{1-p} \over {p}} \right)^{i} } \over {1 - \left( {{1-p} \over {p}} \right)^{N} }} $$ 을 얻는다.
■