주머니 속의 공들에 관한 재귀적 확률 문제

이번 포스팅에서는 주머니 속의 공들에 관한 재귀적 확률 문제를 하나 풀어 보겠싑니다.

문제의 상황은 다음과 같습니다.

주머니 속에 $m$개의 빨간공 $n$개의 파란공이 들어 있습니다. 두 명의 사람이 번갈아 가면서 공을 뽑습니다.(여기서 뽑은 공은 다시 집어 넣지 않습니다.) 이 때 첫 번째로 빨간공을 뽑는 사람이 게임에 승리합니다. 이 상황에서 처음 공을 뽑기 시작한 사람이 게임에 승리하는 확률을 계산 하시오.

문제 풀이

이 문제는 상황은 단순하지만 확률 모델링을 하기 상당히 까다로운 형태의 문제입니다. 이 확률 문제를 해결 하는 가장 간단한 방법은 재귀적인 접근 입니다.

즉, 빨간공과 파란공의 갯수를 기준으로 확률 모델을 최종적으로 설계 해야 합니다.

먼저 처음 공을 뽑기 시작한 사람이 승리하는 확률을 전체 확률 법칙을 통해서 표현 해 보면 다음과 같습니다.

먼저 처음 공을 뽑기 시작한 사람이 승리하는 사건을 첫 번째 사람의 승리라고 약식으로 표기 하겠습니다. 그리하면

$P\left(\text{첫 번째 사람의 승리}\right)=P\left (\text{첫 번째 사람의 승리}|\text{빨간공} \right)P\left(\text{빨간공} \right) + P\left (\text{첫 번째 사람의 승리}|\text{파란공} \right)P\left(\text{파란공} \right)$

으로 표현 할 수 있습니다.

위의 전체 확률 법칙으로 구성 된 확률식을 분석 해 보겠습니다.

• 빨간공을 뽑는 사건과 파란공을 뽑는 사건은 partition 입니다.
• 첫 번째 사람이 빨간공을 뽑았다면 그 즉시 게임에서 승리합니다.
• 첫 번째 사람이 파란공을 뽑았다면 두 번째 사람이 빨간공을 뽑아서 승리하면 안됩니다.
• 바꿔 말해서 $P\left (\text{첫 번째 사람의 승리}|\text{파란공} \right)$의 확률은 두 번째 사람이 빨간공을 뽑고 승리할 확률을 전체 확률 1에서 빼줘야 합니다.

그런데 아직은 위에서 정의된 확률식을 계산 할 수가 없습니다. 모델을 조금 더 구체화 해야 확률을 계산 할 수 있습니다.

위의 전체 확률 법칙을 자세히 들여 보면 결국에 우리가 주어진 정보 중에서 확률 모델을 구체화 시킬 수 있는 정보는 빨간공과 파란공의 갯수 입니다.

빨간 공과 검은 공의 정보를 이용해서 확률식을 다시 한번 정의 해 보겠습니다.

$P\left(\text{첫 번째 사람의 승리}\right)$는 결국에 각각 빨간공과 파란공의 갯수에 달려 있습니다. 그러므로

$P\left(\text{첫 번째 사람의 승리}\right) = P\left(\text{첫 번째 사람의 승리 if} \; i \text{개의 빨간공}, \; j \text{개의 파란공}\right)$ 으로 표현 가능합니다.

결국에는

$P(i,j) = P\left(\text{첫 번째 사람의 승리 if} \; i \text{개의 빨간공}, \; j \text{개의 파란공}\right)$ 입니다.

그런데 우리는 $m$개와 $n$개의 경우에 대한 확률을 구해야 하므로 우리가 구해야 확률은

$P(m,n)$입니다.

자 이제 위에서 정의한 전체 확률 법칙 확률식을 $m$과 $n$의 정보를 이용해서 확률식을 구체화 하겠습니다. 구체화 한 식은 다음과 같습니다.

위의 식에서 $P(m,n)$ 항목을 분석 해 보겠습니다.

• $\frac{m}{m+n}:=$ 첫 번째 사람이 전체 공들 중에서 빨간공을 뽑는 확률입니다.
• $1:=$ 첫 번째 사람이 빨간공을 뽑는 조건이라면 게임에서 무조건 승리하므로 확률은 $1$ 입니다.
• $\frac{n}{m+n}:=$ 첫 번째 사람이 전체 공들 중에서 파란공을 뽑는 확률입니다.
• $(1-P(m,n-1)):=$ 전체 확률 $1$에서 두 번째 사람이 $n-1$개의 공들 중에서 빨간공을 뽑고 승리 하는 확률입니다. 바꿔 말해서 첫 번째 사람이 첫 번째로 파란공을 뽑고도 게임에서 승리하는 확률입니다.

위의 확률 모델에 대한 재귀 조건을 확인 해 보겠습니다.