
일확천금을 노리는 한 도박꾼이 있다고 하죠. 이 도박꾼이 참여한 게임은 아주 간단합니다. 매 판마다 이기면 십만 원을 얻고 지면 십만 원을 잃습니다. 이 도박꾼이 오백만 원의 자본금으로 시작해서 천만 원을 더 벌고 싶다고 합시다. 과연 이 도박꾼이 목표를 이룰 확률은 어떻게 될까요? 반대로 이 도박꾼이 파산하게 될 확률은 또 어떻게 될까요?
이는 도박꾼의 파산(gambler's ruin)이라는 이름으로 많이 연구된 문제입니다. 위 상황을 좀더 일반화하면 다음과 같습니다. 도박꾼이 참여하는 게임에서 매 판마다 도박꾼은
이기는 확률과 지는 확률이 동일한 경우
먼저 도박꾼이 참여한 게임이 완전히 공정한 게임이라고 생각해 봅시다. 즉,
언젠가
반대로 만약
그렇다면 도박꾼이 목표를 이룰 확률과 파산할 확률은 각각 어떻게 될까요? 이는 다음의 정리를 통해서 유추할 수 있습니다. 아래 증명은 엄밀하기 보다는 좀더 직관적으로 기술하였습니다. 그 편이 증명을 이해하는데 더 용이하다고 판단했기 때문입니다. 아래 증명을 기초로 좀더 엄밀한 증명도 충분히 확장 가능하니 필요하시다면 직접 해 보시기 바랍니다.
정리 1. 공정한 게임에서의 획득 금액의 기댓값
임의의
[증명] 수학적 귀납법으로 보이겠습니다. 만약
위 정리를 사용하여 도박꾼이
을 만족할 것입니다. 성공 확률
을 만족하게 됩니다. 이를 정리하면
를 각각 얻을 수 있게 됩니다. 각각이 바로 도박꾼이 성공할 확률과 파산할 확률입니다.
예컨대, 만약 초기 자본금만큼 추가로 벌고자 한다면 (즉,
이기는 확률이 지는 확률보다 낮은 경우
앞에서 살펴본 게임은 도박꾼이 이길 확률과 질 확률이 동일한 공정한 게임이었습니다. 따라서 도박꾼이 원하는 목표를 달성할 확률도 생각보다는 합리적인 수준입니다. 하지만 현실은 그리 녹록치 않죠. 모든 카지노의 도박들은 참여자가 돈을 얻을 확률보다 잃을 확률이 큽니다. 과연 그러한 경우에도 도박꾼이 목표를 이룰 확률이 합리적인 수준일까요?
논의를 간단하게 하기 위해 매 판마다 도박꾼이 이길 확률은
위와 똑같이
이전에 도박꾼이 목표를 이룰 확률과 파산할 확률을 구하기 위해서 정리 1이 필요했습니다. 하지만 현재 상황에서는 그 정리가 성립하지 않습니다. 당장에 첫 번째 판이 끝난 후에는
정리 2. 불공정한 게임에서의 획득 금액의 기댓값
임의의
참고로

여러분은 착오 없으시기 바랍니다.
[증명] 정리 1과 비슷하게 수학적 귀납법으로 증명합니다.
만큼 기여를 하게 됩니다. 따라서
똑같이
여기서 발견할 수 있는 흥미로운 사실은 도박꾼이 성공할 확률이 목표 금액
일반적인 상황
앞의 상황은 도박꾼이 이길 확률이
정리 3. 정리 2의 일반화
매 판마다 도박꾼이 이길 확률이
따라서, 도박꾼이 목표를 달성할 확률과 파산할 확률은 각각
마치며
이것으로 도박꾼의 파산 문제에 대한 정리를 마칩니다. 요즘 확률에 대한 공부를 따로 하고 있는데, 흥미로운 내용이 무진장 많이 있습니다. '학부생 때 이러한 내용을 미리 알았더라면 어땠을까?'라는 생각도 많이 드는 요즘입니다. 포스팅하기 좋은 주제는 가지고 올 수 있도록 하겠습니다. 고맙습니다. :)
참조
[1] Michael Mitzenmacher and Eli Upfal. Probability and computing: Randomization and probabilistic techniques in algorithms and data analysis. Cambridge university press, 2017.
'알고리즘 & 확률 > Basic' 카테고리의 다른 글
랜덤 알고리즘과 알고리즘의 확률적 분석 (Randomized Algorithms & Probabilistic Analysis of Algorithms) (10) | 2020.11.28 |
---|---|
체르노프 부등식 (Chernoff Bounds) (0) | 2020.11.14 |
지연 결정의 원리 (Principle of Deferred Decisions) (2) | 2020.11.11 |
야오의 법칙 (Yao's Principle) (0) | 2019.08.12 |
Arbitrary & Random (0) | 2019.08.11 |