도박꾼의 파산 문제 해설
원문은 [1]. 일본어라 구글번역[2] 돌려서 봤는데 수학이라 그런지 일본어라 그런지 이해하기는 충분하다.
문제풀이의 아이디어는
- 1) 일단 답이 만족해야 하는 성질을 제시하고
- 2) 어떤 식을 답으로 제안하여 1을 만족함을 보이고
- 3) 1의 해가 유일함을 보여서 2에서 제안한 식이 답임을 보인다.
\(P(N, N)=1, P(0, N)=0\)임은 자명하다. (내맘대로 fixed point라고 하겠다)
그리고,
$$\begin{equation}P(m,N) = pP(m+1,N) + qP(m-1,N) \end{equation}$$이다. 왜냐하면,
- 처음 던졌을 때 이겼다면(\(p\)) 현재 가진 돈은 \(m+1\)원이므로 \(P(m+1, N)\)을 만족하면 된다.
- 처음 던졌을 때 졌다면(\(q\)) 현재 가진 돈은 \(m-1\)원이고 \(P(m-1, N\))을 만족하면 된다.
따라서 (1)이 성립한다.
답이 아래와 같다고 치면$$\large \begin{equation} P(m,N) = \frac{1-(q/p)^m}{1-(q/p)^N} \end{equation}$$ 위의 세 조건을 모두 만족한다. 계산해보면 된다.
한편,
P(1,2)를 생각해 보면, P(0,2)와 P(2,2)로 결정되고, 계산하면 나온다. 따라서 P(m, 2)의 가능한 모든 수를 구했다. (m=0,1,2)
P(1,3)을 생각해보면, P(0,3)과 P(2,3)으로 결정되고, P(2,3)은 다시 P(1,3)과 P(3,3)으로 결정된다. 즉, 연립방정식을 얻는다.
모든 수에 대해 아래와 같은 식이다. (검은 점이 fixed point)
따라서 해가 존재하고 유일하다. 그러므로 위에서 구한 해(equation(2))가 답이다.
단, (2)에서 \(\displaystyle p=q=\frac{1}{2}\) 이면, 분모가 0이므로, \(p=q\) 인 경우는 따로 정해주어야 한다. \(\displaystyle P(m,N) = \frac{m}{N} \)이다.
위의 그림을 보면 \(p=q\) 일 때는, 가운데 항이 앞과 뒤 항의 산술평균일테니 \(m/N\)임을 쉽게 알 수 있다.
직관적으로, 이기고 질 확률이 같다면 ‘결국’이길 확률은 승점과 패점의 거리 비율이다.
추가
몇가지 궁금한점이 생겨서 직접 실험해봄.
3원가지고 6원만드는 코드를 짜서 P(3,6)을 직접 구해보았다.
10만번 시행해서 이기는 횟수를 세었고, 이 실험을 계속 반복하면서 평균추이를 보았다.
위 식대로 하면 이론값이 0.072973 나오는데, 약 2천회만 시행해도 정확히 동일한 값으로 수렴한다.
일단 조금 이상하다고 생각하게 된 이유는, P(m,N)이 m으로 시작해서 N이 되는 확률인데 P(N,N)이 1로 정의되는 것이 이상했다.
예를들어 P(N-1, N)을 보면, 하나 없는 상태에서 시작하므로 q*P(N-2, N) + p 가 된다. 여기서 p는 (N-1개를 가진 상태에서) 그냥 이길 확률이다.
P(N,N)의 경우는 그러니까 게임이 성립하지 않는 상태인데(P(0,N)도 마찬가지.) 아마도 저렇게 놓고 풀면 앞뒤가 잘 맞으니 그렇게 정의한 것으로 보인다. 따라서,
(사실 처음 봤을땐 ‘자명’한줄 알고 위에도 그렇게 써놨는데 생각할수록 이상하더라)
실제로 문제를 풀 때는, P(1,N)부터 P(N-1,N)까지를 구해야 하는거 아닌가 싶다. 그러고서 이로부터 P(0,N)과 P(N,N)을 유추할 수 있으면 좋은거고.
다행히 연립방정식을 얻는 과정은 동일해서 위 세 조건을 만족하는 P(m,N)을 구할 수 있다. 대신 계산이 아주아주아주 복잡하다. -_-
예를들어 N=4일 경우, (아래 식에서는 모두 N을 생략. 즉 P(1) = P(1,4)이다) $$ \mathbf{P} = \begin{pmatrix} 0 & p & 0 \\ q & 0 & p \\ 0 & q & 0 \end{pmatrix} \mathbf{P} + \begin{pmatrix} 0 \\ 0 \\ p \end{pmatrix},\, \text{where}\, \mathbf{P} = \begin{pmatrix} P(1) \\ P(2) \\ P(3) \end{pmatrix}, \, \text{so,} \\ \\ \begin{equation}
\begin{pmatrix} -1 & p & 0 \\ q & -1 & p \\ 0 & q & -1 \end{pmatrix} \mathbf{P} = \begin{pmatrix} 0 \\ 0 \\ -p \end{pmatrix}
\end{equation} $$ 실제로 계산해보면 (1)에서 구한 답과 일치한다. \(p+q=1\)임을 이용하면 결국 같은 모양을 이끌어 낼 수 있다. 물론 (3)에서는 \(p=q\) 를 따로 처리해줄 필요가 없다.
P(m, 5)를 (3)과 같이 써보면 왼쪽 행렬은 다음과 같고 이런식으로 일반화 하는 것은 어렵지 않다. $$ \begin{equation} \begin{pmatrix} -1 & p & 0 & 0 \\ q & -1 & p & 0 \\ 0 & q & -1 & p \\ 0 & 0 & q & -1 \end{pmatrix} \end{equation} $$
점화식으로 가능한가 궁금했는데, 뭘 잘못했는지 계산결과가 맞지 않는다. 예를들어 (1)을 다음과 같이 보면,
$$
a_n = a_{n+1} p + a_{n-1} q
$$
따라서,
$$
a_n = C_1 \left( \frac{1 + |1 - 2p|}{2p} \right) ^n + C_2 \left( \frac{1 - |1-2p|}{2p} \right) ^n $$
인데 여기서 \(p = 1/2\)이라면, \(a_n = C_1 + C_2\)가 되어 모든 \(m\)에 대해 P가 동일하다는 말이다. 실제로는 그렇지 않다.(기대되는 결과는 등차수열이다)
어디서 계산이 틀린건지, 점화식을 잘못 푼건지 잘 모르겠다. 무한하지 않은 수열에 대해서 무한하다는 가정을 놓고 점화식을 넣어 그런건가 싶기도 하고.
Tridiagonal matrix 의 역행렬을 간단히 나타낼 수 있으면 (2)를 바로 유도해낼 수 있을것 같기도 한데 아직 모름.