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

Photo by Michał Parzuchowski on Unsplash

일확천금을 노리는 한 도박꾼이 있다고 하죠. 이 도박꾼이 참여한 게임은 아주 간단합니다. 매 판마다 이기면 십만 원을 얻고 지면 십만 원을 잃습니다. 이 도박꾼이 오백만 원의 자본금으로 시작해서 천만 원을 더 벌고 싶다고 합시다. 과연 이 도박꾼이 목표를 이룰 확률은 어떻게 될까요? 반대로 이 도박꾼이 파산하게 될 확률은 또 어떻게 될까요?

 

이는 도박꾼의 파산(gambler's ruin)이라는 이름으로 많이 연구된 문제입니다. 위 상황을 좀더 일반화하면 다음과 같습니다. 도박꾼이 참여하는 게임에서 매 판마다 도박꾼은 \(p\)의 확률로 이기며, \(1 - p\)의 확률로 집니다. 단위를 간소화하기 위해 도박꾼이 이기면 1원을 얻고, 지면 1원을 잃는다고 합시다. 도박꾼은 처음에 \(L\)원의 자본금을 갖고 있으며, 도박꾼의 목표는 추가로 \(U\)원을 따는 것입니다. 여기서 문제는 도박꾼이 \(L\)원의 자본금을 모두 소진하기 전에 \(U\)원을 추가로 획득할 확률과 목표를 달성하기 전에 모든 자본금을 소진하는 확률을 각각 구하는 것입니다.

이기는 확률과 지는 확률이 동일한 경우

먼저 도박꾼이 참여한 게임이 완전히 공정한 게임이라고 생각해 봅시다. 즉, \(p = 1/2\)인 상황입니다. \(t\) 번째 판이 끝난 후 추가로 획득한 금액을 \(M_t\)라고 하겠습니다. 만약 \( M_t < 0 \)이라면 이는 초기 자본금을 \(M_t\)만큼 까먹었다는 뜻입니다. 게임이 시작할 때는 얻거나 잃은 돈이 없으므로 \(M_0 = 0\)으로 정의하겠습니다.

 

언젠가 \(t\) 번째 판이 끝난 후 \(M_t = m\)의 금액을 획득한 상태라고 하겠습니다. 만약 \(m\)이 \( -L < m < U \)를 만족한다면, 우리는 다음 \(t + 1\) 번째 판을 진행할 것입니다. 게임은 공정하므로, \(1/2\)의 확률로 1원을 획득하여 \(M_{t + 1} = m + 1\)이 되고, 나머지 \(1/2\)의 확률로는 1원을 잃어 \( M_{t + 1} = m - 1 \)이 될 것입니다. 다시 말해, 임의의 \(t \geq 0\)에 대해, \( -L < m < U \)인 경우에는 \[ Pr[M_{t + 1} = m + 1 \mid M_t = m] = Pr[M_{t + 1} = m - 1 \mid M_t = m] = 1/2 \tag{1} \]을 만족합니다.

 

반대로 만약 \(m = U\)였다면 도박꾼이 자신의 목표를 달성한 것이므로 더 이상 새로운 판을 시작하지 않습니다. 하지만 아래에서는 마치 \(t + 1\) 번째 판을 진행하되 아무 금액도 얻거나 잃지 않는다고 가정하겠습니다. 즉, 임의의 \(t \geq 0\)에 대해, \[ Pr[M_{t + 1} = U \mid M_t = U] = 1 \]을 만족한다고 하겠습니다. 비슷한 이치로, 만약 \(m = -L\)이었다면 도박꾼은 파산하여 더 이상 새로운 판을 진행할 수 없는 상태이지만, 마치 새로운 판을 진행하였지만 아무 금액도 얻거나 잃지 않는다고 하겠습니다. 다시 말해, \[ Pr[M_{t + 1} = -L \mid M_t = -L] = 1 \]도 만족합니다.

 

그렇다면 도박꾼이 목표를 이룰 확률과 파산할 확률은 각각 어떻게 될까요? 이는 다음의 정리를 통해서 유추할 수 있습니다. 아래 증명은 엄밀하기 보다는 좀더 직관적으로 기술하였습니다. 그 편이 증명을 이해하는데 더 용이하다고 판단했기 때문입니다. 아래 증명을 기초로 좀더 엄밀한 증명도 충분히 확장 가능하니 필요하시다면 직접 해 보시기 바랍니다.

정리 1. 공정한 게임에서의 획득 금액의 기댓값

---

임의의 \(t \geq 0\)에 대해, \(\mathbb{E}[M_t] = 0\)이다.

[증명] 수학적 귀납법으로 보이겠습니다. 만약 \(t = 0\)이라면 1의 확률로 \(M_0 = 0\)이라고 정의했으므로 정리의 명제가 성립합니다. 따라서 어떤 \(t\)에 대해 \(\mathbb{E}[M_t] = 0\)을 만족한다고 가정하겠습니다. 이때 \(\mathbb{E}[M_{t + 1}] = 0\)을 곧바로 보이는 대신 \( \mathbb{E}[M_{t + 1}] = \mathbb{E}[M_t] \)임을 보이도록 하겠습니다. \(\mathbb{E}[M_t] = \sum_{m = -L}^U Pr[M_t = m] \cdot m \)에서 합의 각 항 \(Pr[M_t = m] \cdot m\)이 다음 판에서 \(\mathbb{E}[M_{t + 1}]\)에 어떻게 영향을 미치는지를 생각해 봅시다. 만약 \(m = -L\)이거나 \(m = U\)였으면 다음 판에도 그대로 이므로 변화가 없습니다. 따라서 \( -L < m < U \)인 경우만 따져보면 됩니다. 각각 절반의 확률로 다음 판에 \(m + 1\)과 \(m - 1\)이 되므로 다음 판의 기댓값에 \[ Pr[M_t = m] \cdot \left[ Pr[M_{t + 1} = m + 1 \mid M_t = m] \cdot (m + 1) + Pr[M_{t + 1} = m - 1 \mid M_t = m] \cdot (m - 1) \right] \]의 기여를 하게 됩니다. 식 1에 의해 위 식은 \( Pr[M_t = m] \cdot m \)과 동일하다는 것을 알 수 있습니다. 따라서 \( \mathbb{E}[M_t] \)의 각 항과 동일한 값이 매번 \( \mathbb{E}[M_{t + 1}] \)에 더해지는 격이므로 두 기댓값은 동일합니다. ■

 

위 정리를 사용하여 도박꾼이 \(U\)원을 획득하는데 성공할 확률과 파산할 확률을 구해 보겠습니다. 도박꾼은 성공하거나 파산할 때까지 계속 게임을 진행할 것이고, 한번 성공하거나 파산한 경우에는 계속 그 상태를 유지하므로 "무한히 많은" 판을 진행하고 나면 "거의 확실하게" 성공을 했거나 파산을 했을 것입니다. 즉,

\[ \lim_{t \to \infty} Pr[M_t = -L] + Pr[M_t = U] = 1\]

을 만족할 것입니다. 성공 확률 \( \lim_{t \to \infty} Pr[M_t = U] = q\)라고 합시다. 그러면 정리 1에 의해

\[ \lim_{t \to \infty} \mathbb{E}[M_t] = (1 - q) \cdot (-L) + q \cdot U = 0 \]

을 만족하게 됩니다. 이를 정리하면

\[ q = \frac{L}{L + U}, \quad 1 - q = \frac{U}{L + U} \]

를 각각 얻을 수 있게 됩니다. 각각이 바로 도박꾼이 성공할 확률과 파산할 확률입니다.

 

예컨대, 만약 초기 자본금만큼 추가로 벌고자 한다면 (즉, \(U = L\)) 도박꾼이 성공할 확률은 절반이 됩니다. 만약 초기 자본금의 두 배를 추가로 벌고자 한다면 (즉, \(U = 2L\)) 도박꾼이 성공할 확률은 \(1/3\)이 되는 것이죠.

이기는 확률이 지는 확률보다 낮은 경우

앞에서 살펴본 게임은 도박꾼이 이길 확률과 질 확률이 동일한 공정한 게임이었습니다. 따라서 도박꾼이 원하는 목표를 달성할 확률도 생각보다는 합리적인 수준입니다. 하지만 현실은 그리 녹록치 않죠. 모든 카지노의 도박들은 참여자가 돈을 얻을 확률보다 잃을 확률이 큽니다. 과연 그러한 경우에도 도박꾼이 목표를 이룰 확률이 합리적인 수준일까요?

 

논의를 간단하게 하기 위해 매 판마다 도박꾼이 이길 확률은 \(1/3\), 질 확률은 \(2/3\)이라고 가정하겠습니다. 이를 임의의 \(p > 1/2\)에 대해서 확장하는 것은 마지막에 간단히 다루겠습니다.

 

위와 똑같이 \(t\) 번째 판이 끝난 후 추가로 얻은 금액을 \(M_t\)라고 하겠습니다. 똑같이 \(M_0 = 0\)으로 정의하겠습니다. 그러면 위와 같이 현재 판의 결과에 따른 다음 판의 결과에 대한 확률을 다음과 같이 나타낼 수 있습니다. 임의의 \(t\)에 대해, 만약 \( -L < m < U \)라면, \[ Pr[M_{t + 1} = m + 1 \mid M_t = m] = 1/3, \quad Pr[M_{t + 1} = m - 1 \mid M_t = m] = 2/3; \] 만약 \( m = -L, U \)라면, \[ Pr[M_{t + 1} = m \mid M_t = m] = 1 \]이 됩니다.

 

이전에 도박꾼이 목표를 이룰 확률과 파산할 확률을 구하기 위해서 정리 1이 필요했습니다. 하지만 현재 상황에서는 그 정리가 성립하지 않습니다. 당장에 첫 번째 판이 끝난 후에는 \(M_t = -1\)이 될 확률이 \(2/3\), \(M_t = 1\)이 될 확률이 \(1/3\)이므로 \( \mathbb{E}[M_t] = -1/3 \)입니다. 이는 \(M_t\)가 증가할 확률보다 감소할 확률이 더 크기 때문에 발생하죠. 따라서 정리 1과 같이 매 판에 걸쳐 어떤 등식을 유도하기 위해서는 감소했을 때의 기여가 증가했을 때의 기여보다 더 작아야 하겠습니다. 흥미롭게도 우리는 아래 정리를 통해 이를 얻을 수 있습니다.

정리 2. 불공정한 게임에서의 획득 금액의 기댓값

---

임의의 \(t \geq 0\)에 대해, \( \mathbb{E}[2^{M_t}] = 1 \)이다.

참고로 \( \mathbb{E}[2^{M_t}] \neq 2^{\mathbb{E}[M_t]} \)입니다. 처음에는 이 식의 우변으로 해석해서 정리 2가 틀린 줄 알았습니다.

여러분은 착오 없으시기 바랍니다. 

[증명] 정리 1과 비슷하게 수학적 귀납법으로 증명합니다. \(t = 0\)일 때는 자명하게 성립합니다. 어떤 임의의 \(t\)에 대해서 정리의 명제가 성립한다고 합시다. 정리 1의 증명에서와 같이 \( \mathbb{E}[2^{M_t}] = \sum_{m = -L}^U Pr[M_t = m] \cdot 2^m \)의 각 항이 다음 판의 기댓값 \(\mathbb{E}[2^{M_{t + 1}}]\)에 어떻게 기여하는지를 따져 봅시다. 만약 \(m = -L, U\)인 경우에는 동일합니다. 만약 \( -L < m < U \)인 경우에는 \( \mathbb{E}[2^{M_{t + 1}}] \)에 \[ \begin{array}{l} Pr[M_t = m] \cdot \left[ Pr[M_{t + 1} = m + 1 \mid M_t = m] 2^{m + 1} + Pr[M_{t + 1} = m - 1 \mid M_t = m] 2^{m - 1} \right] \\ = Pr[M_t = m] \cdot \left[ \frac{1}{3} 2^{m + 1} + \frac{2}{3} 2^{m - 1} \right] \\ = Pr[M_t = m] \cdot 2^m \end{array} \]

만큼 기여를 하게 됩니다. 따라서 \( \mathbb{E}[2^{M_{t + 1}}] = \mathbb{E}[2^{M_t}] = 1 \)이 성립합니다. ■

 

똑같이 \( q = \lim_{t \to \infty} Pr[M_t = U] \)라고 하겠습니다. 그러면 정리 2에 의해 \[ \lim_{t \to \infty} \mathbb{E}[2^{M_t}] = (1 - q) \cdot 2^{-L} + q \cdot 2^U = 1 \]을 만족하게 되며, 이를 정리하면 \[ q = \frac{1 - 2^{-L}}{2^U - 2^{-L}}, \quad 1-q = \frac{2^U - 1}{2^U - 2^{-L}} \]이 각각 도박꾼이 목표를 달성할 확률과 파산할 확률이 되겠습니다.

 

여기서 발견할 수 있는 흥미로운 사실은 도박꾼이 성공할 확률이 목표 금액 \(U\)에 지수적으로 감소한다는 점입니다. 따라서 목표가 높아질수록 그 목표를 성취할 확률이 기하급수적으로 어려워진다는 뜻이죠. 반면 파산할 확률은 그만큼 기하급수적으로 증가합니다.

일반적인 상황

앞의 상황은 도박꾼이 이길 확률이 \(p = 1/3\)인 경우에 대한 분석이었습니다만, 사실 이 분석은 임의의 \(p < 1/2\)에 대해 다음과 같이 확장됩니다. 증명은 생략합니다.

정리 3. 정리 2의 일반화

---

매 판마다 도박꾼이 이길 확률이 \(p < 1/2\)라고 하자. 임의의 \(t\)에 대해, \[ \mathbb{E}\left[ \left( \frac{1-p}{p} \right)^{M_t} \right] = 1 \]이 성립한다.

따라서, 도박꾼이 목표를 달성할 확률과 파산할 확률은 각각 \[ q = \frac{1 - (\frac{1-p}{p})^{-L}}{(\frac{1-p}{p})^U - (\frac{1-p}{p})^{-L}}, \quad q = \frac{(\frac{1-p}{p})^{U} - 1}{(\frac{1-p}{p})^U - (\frac{1-p}{p})^{-L}} \]이 됩니다.

마치며

이것으로 도박꾼의 파산 문제에 대한 정리를 마칩니다. 요즘 확률에 대한 공부를 따로 하고 있는데, 흥미로운 내용이 무진장 많이 있습니다. '학부생 때 이러한 내용을 미리 알았더라면 어땠을까?'라는 생각도 많이 드는 요즘입니다. 포스팅하기 좋은 주제는 가지고 올 수 있도록 하겠습니다. 고맙습니다. :)

참조

[1] Michael Mitzenmacher and Eli Upfal. Probability and computing: Randomization and probabilistic techniques in algorithms and data analysis. Cambridge university press, 2017.