logo

도박꾼의 파산 문제 📂확률론

도박꾼의 파산 문제

문제

20190213\_101451.png

도박꾼의 파산 문제는 랜덤워크의 일종으로 두 명의 플레이어가 한정된 돈을 걸고 둘 중 하나가 파산할 때까지 반복하는 게임을 상정한다.

당신이 플레이어 중 하나라고 한다면, 위 도식과 같이 당신이 이길 확률이 pp 고 질 확률이 (1−p)(1-p) 라고 할 수 있다. 상태 00 은 당신이 파산한 경우고, 상태 NN 은 당신이 상대의 돈을 모두 딴 경우로 더 이상 게임을 반복하지 않는다. 이는 00 과 NN 에서 자기 자신으로 가는 확률이 11 이라는 것으로 표현되어있다. ii 는 게임을 시작할 때 당신의 소지금이라고 볼 수 있겠다.

기본적으로 p≠12\displaystyle p \ne {{1} \over {2}} 이거나 i≠N2\displaystyle i \ne {{N} \over {2}} 이라면 게임은 공평하지 않다. 이 게임은 한 명이 파산을 할 때까지 끝나지 않으며, 수식적으로 관심을 가질만한 질문은 ‘당신이 ii 만큼의 돈을 가지고 시작했을 때 상대를 파산시키고 이길 확률이 얼마나 되는가’다. 다만 그 이전에 ‘왜 이렇게 불공평하고 극단적인 게임을 하는가’라는 질문을 할 수 있다.

하지만 이것은 어디까지나 도박꾼의 파산 문제를 게임으로만 보았을 때 할 수 있는 질문이고, 현실 속에선 오히려 공평한 싸움을 찾아보는 게 더 어렵다. 이는 자본이 많은 대기업과 법의 보호를 받는 소상공인의 대결로 볼 수도 있고, 같은 자원을 생산하는 국가끼리의 총력전으로 볼 수도 있다. 불리한 싸움이라도 해야할 때가 있으며, 이 때의 승산이 궁금한 것은 당연한 일이다.

다시 수식으로 돌아와서, 우리의 관심사는 ‘초기자본이 ii 이고 승률이 pp 일 때, 상대방을 파산시키고 모든 돈을 가져올 확률’ PiP_{i} 를 계산하는 것이다. 편의상 ‘상대방을 파산하고 모든 돈을 가져오는 상황’을 ‘우승’이라 부르겠다.

풀이

PiP_{i} 의 정의에서 P0=0P_{0} = 0 이고 PN=1P_{N} = 1 이다.

Part 1.

PiP_{ i } 는 pp 의 확률로 첫번째 게임에서 승리하고 (i+1)( i+1 ) 에서 새로운 시작을 해서 우승할 확률과 (1−p)(1-p) 의 확률로 첫번째 게임에서 패배하고 (i−1)( i-1 ) 에서 새로운 시작을 해서 우승할 확률을 더한 것으로 볼 수 있다. 수식으로는 Pi=pPi+1+(1−p)Pi−1P_{ i } = p P_{ i + 1 } + (1 - p ) P_{ i - 1 } 이 된다. 여기서 좌변을 pp 와 (1−p)(1-p) 로 찢어내면 Pi=(p+1−p)Pi=pPi+(1−p)PiP_{ i } = (p + 1 - p ) P_{i} = p P_{i} + (1 - p) P_{i} 이므로 Pi=pPi+1+(1−p)Pi−1  ⟹  pPi+(1−p)Pi=pPi+1+(1−p)Pi−1  ⟹  p(Pi+1−Pi)=(1−p)(Pi−Pi−1)  ⟹  (Pi+1−Pi)=1−pp(Pi−Pi−1) \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*}

재귀적으로 풀어내면 Pi−Pi−1=(1−pp)i−1(P1−P0)\displaystyle P_{i} - P_{i-1} = \left( {{1-p} \over {p}} \right)^{i-1} \left( P_{1} - P_{0} \right) 인데, P0=0P_{0} = 0 이므로 Pi−Pi−1=(1−pp)i−1P1\displaystyle P_{i} - P_{i-1} = \left( {{1-p} \over {p}} \right)^{i-1} P_{1}

Part 2.

P1−P0=(1−pp)0P1P2−P1=(1−pp)1P1P3−P2=(1−pp)2P1Pi−Pi−1=(1−pp)i−1P1P_{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}

위의 식들을 각 변끼리 더하면 좌변은 (P1−P0)+(P2−P1)+⋯+(Pi−Pi−1)=Pi−P0=Pi( P_{1} - P_{0} ) + ( P_{2} - P_{1} ) + \cdots + ( P_{i} - P_{i-1} ) = P_{i} - P_{0} = P_{i} 우변은 ∑k=1i(1−pp)k−1P1=1−(1−pp)i1−(1−pp)P1\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} 정리하면 Pi=1−(1−pp)i1−(1−pp)P1\displaystyle P_{i} = {{ 1 - \left( {{1-p} \over {p}} \right)^{i} } \over {1 - \left( {{1-p} \over {p}} \right) }} P_{1}

Part 3.

PN=1P_{N} = 1 이므로 1=PN=1−(1−pp)N1−(1−pp)P1 1 = P_{N} = {{ 1 - \left( {{1-p} \over {p}} \right)^{N} } \over {1 - \left( {{1-p} \over {p}} \right) }} P_{1} 따라서 P1=1−(1−pp)1−(1−pp)N P_{1} = {{1 - \left( {{1-p} \over {p}} \right) } \over { 1 - \left( {{1-p} \over {p}} \right)^{N} }} 위의 Part 2.에서 얻은 식에 P1P_{1} 을 대입함으로써 Pi=1−(1−pp)i1−(1−pp)⋅1−(1−pp)1−(1−pp)N=1−(1−pp)i1−(1−pp)N 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} }} 을 얻는다.

■