지연 결정의 원리 (Principle of Deferred Decisions)

Photo by Sonja Langford on Unsplash

최근 논문을 읽는 중에 "지연 결정의 원리(principle of deferred decisions)"에 대해 알게 되었습니다. 이해가 잘 되지 않아서 인터넷에서도 열심히 찾아 보았으나 국문은 고사하고 영문으로 된 자료도 찾기 어렵더군요. 그나마 있는 자료들도 대부분 학교 수업 자료여서 제가 원하는 수준으로 상세하게 기술되어 있지 않았습니다. 다행히 교과서를 하나 찾게 되어 이 주제를 좀더 깊이 이해할 수 있었습니다. 이번 시간에는 이 원리에 대해서 한번 정리해 보겠습니다. 참고로 번역은 다음에서 "principle of deferred decisions"를 쳤을 때 나오는 거의 유일한 국문 웹페이지에서의 번역을 그대로 가지고 왔습니다.

---

원리를 이해하기 위해 다음 예제 게임을 함께 생각해 봅시다. 책상 위에는 1부터 10까지 적힌 카드가 잘 섞인 채로 일렬로 놓여 있습니다. 먼저, 맨 마지막 카드를 갖고 와서 카드에 적힌 숫자를 확인합니다. 다음, 해당 카드에 적힌 숫자를 \(x\)라고 했을 때, 이번에는 \(x\)번째 위치한 카드를 갖고 옵니다. 그러고는 또다시 이 카드에 적힌 숫자를 확인하고, 해당 숫자의 위치에 있는 카드를 갖고 옵니다. 이 작업을 반복하다가 언젠가 뽑아야 할 위치에 카드가 없으면 게임을 종료합니다. 이때 만일 우리가 책상 위의 모든 카드를 수거했다면 우리가 이깁니다. 반대로 책상 위에 카드가 한 장이라도 있으면 우리의 패배입니다.

 

다음 애니메이션은 이 게임에서 우리가 승리하는 경우 중 하나를 나타낸 것입니다.

그림 1. 이 게임에서 우리가 승리하는 경우.

반대로 우리가 패배하는 경우는 다음과 같은 상황입니다.

그림 2. 이 게임에서 우리가 패배하는 경우.

만약 책상 위 카드의 배치가 균등한 확률(uniformly at random)로 가능한 모든 경우 중 하나로 결정이 된다고 한다면, 과연 우리가 이 게임에서 승리하는 확률은 얼마가 될까요?

 

한번 직접 계산해 보도록 하죠. 먼저, 카드 배치가 정해지면 동시에 우리의 동작도 결정된다는 사실을 확인하시기 바랍니다. 예를 들어, 카드가 2, 3, 9, 7, 6, 10, 5, 1, 4, 8 순으로 배치가 되었다면, 우리는 분명 처음에 마지막 카드를 갖고 오고, 다음 여덟 번째 카드를 갖고 오고, 다음 첫 번째 카드를 갖고오는 식으로 진행하게 됩니다. 이때, 모든 배치가 균등한 확률로 정해지므로, 우리가 이 게임에서 이기는 확률은 분명 이길 수 있는 배치의 경우의 수를 전체 가능한 배치의 가짓수로 나눈 값이 됩니다.

 

여기서 큰 문제는 우리가 고려해야 하는 경우의 수가 너무 많다는 것입니다. 당장에 가능한 카드 배치의 모든 가짓수는 얼마일까요? 이는 1부터 10까지를 순서 상관하면서 일렬로 배치하는 경우의 수와 동일하므로 \( 10! = 3,628,800\)가 됩니다. 이 경우를 하나씩 모두 따져 본다는 것은 너무 멍청한 일일 것입니다.

 

따라서 처음부터 모든 것을 몽땅 갖고 와서 고려하는 것 말고 다른 방법이 필요합니다. 대신 우리가 매번 선택을 할 때마다 우리가 계속 이길 수 있는 조건이 어떻게 되는지를 분석할 수 있다면 한번에 모든 것을 고려하는 것보다는 수월할 것입니다. 이를 위해서는 다음의 흥미로운 성질을 알 필요가 있습니다.

정리 1. 게임이 종료할 조건

---

게임을 이기든 지든, 게임이 종료하는 순간 마지막에 뽑은 카드는 반드시 10이 적혀있다.

[증명] 게임이 끝나려면 카드가 없거나 이미 카드를 뽑은 위치에 다시 방문해야 합니다. 열 번째 위치를 뺀 나머지 위치의 카드를 뽑기 위해서는 이전에 해당 위치의 숫자의 카드를 뽑았어야 합니다. 그러고 나서 다시 방문하려면 해당 숫자의 카드를 다시 뽑아야 합니다. 하지만 각 숫자는 하나씩 밖에 없으므로 그럴 수 없습니다. 따라서 마지막에 뽑은 카드는 반드시 10입니다. ■

 

위 정리를 통해 우리는 게임에서 이기는 조건을 손쉽게 이끌어낼 수 있습니다.

정리 2. 게임에서 승리할 조건

---

게임에서 이길 필요충분조건은 마지막에 10의 카드를 뽑는 것이다.

이 정보를 토대로 우리가 게임에서 이길 확률을 구해보도록 하겠습니다. 모든 배치가 균등한 확률로 정해지므로, 우리가 처음에 뽑는 마지막 카드의 숫자도 1부터 10까지 중 균등한 확률로 하나가 적혀있을 것입니다. 이때 10을 뽑았다면 정리 2에 의해서 바로 게임에서 질 것이므로 이기기 위해서는 10을 뺀 나머지 숫자 중 하나가 적힌 카드를 뽑아야 합니다. 이 확률은 정확히 \( \frac{9}{10} \)이 되겠죠.

 

처음 뽑은 카드가 10이 아니라는 전제 아래, 해당 카드에 적힌 숫자의 위치의 카드를 뽑으러 가겠습니다. 똑같이 정리 2에 의해 우리가 이기기 위해서는 해당 카드에 10이 적혀있으면 안됩니다. 모든 배치가 균등한 확률로 정해지므로, 10이 아니라는 전제가 있는 경우에도 처음에 뽑힌 숫자를 뺀 나머지 숫자들이 해당 위치에 균등한 확률로 존재할 것입니다. 따라서, 첫 번째에 10의 카드를 뽑지 않았을 때, 두 번째 단계에서 10이 적힌 카드를 뽑지 않을 확률은 \( \frac{8}{9} \)가 되겠습니다.

 

위 작업을 계속 반복하면 우리는 \( i \) 번째 단계까지 10을 뽑지 않았을 때 \( i + 1 \) 번째 단계에서 10의 카드를 뽑지 않을 확률이 정확히 \( \frac{9 - i}{10 - i} \)가 된다는 것을 알 수 있습니다. 따라서 우리가 게임에서 이길 조건인 마지막에 10이 적힌 카드를 뽑을 확률은

\[ \frac{9}{10} \times \frac{8}{9} \times \cdots \times \frac{1}{2} = \frac{1}{10} \]

이 됩니다.

정리 3. 게임에서 이기는 확률

---

카드의 배치가 균등한 확률로 결정되는 상황에서 우리가 게임에서 이기는 확률은 \( \frac{1}{10} \)이다.

---

위 예제에서 게임에서 이길 확률을 구하기 위해서 처음부터 모든 경우의 수를 고려하지 않는다는 것에 주목하시기 바랍니다. 대신 게임이 진행되는 동안 우리가 각 상황에 맞는 조건부 확률(conditional probability)을 그때그때 계산함으로써 최종적으로 게임에서 이기는 확률을 구하였습니다. 이렇게 확률 시행으로 결정되는 정보를 모조리 올려 놓고 계산하기 보다 확률 시행이 필요한 순간에만 적절한 작업을 적용하는 기법을 지연 결정의 원리라고 한다고 합니다.

 

사실 교과서나 여타의 수업 자료에는 위 예제가 실려 있지는 않습니다. 거기서 소개하는 게임은 "클락 솔리테어(clock solitaire)"라고 불리는 게임입니다. 게임의 진행은 다음과 같습니다. 먼저 트럼프 카드를 잘 섞은 후 4장씩 총 13 묶음으로 나누어 일렬로 둡니다. 각 묶음은 처음부터 A, 2, 3, 4, 5, 6, 7, 8, 9, 10, J, Q, K의 이름을 갖습니다. 게임 참가자는 맨 처음 K 묶음의 카드를 한 장 뽑습니다. 그 후, 카드에 적힌 숫자/글자에 맞추어 해당 묶음의 카드를 뽑습니다. 이 작업을 계속 반복하다가 언젠가 어떤 묶음의 카드를 뽑아야 하는데 묶음에 남은 카드가 없는 경우에 게임을 끝냅니다. 이때 카드를 모두 수거했다면 참가자의 승리이고, 그렇지 않다면 참가자의 패배입니다. 여기서 질문은 트럼프 카드가 균등한 확률로 섞일 때 참가자가 이기는 확률을 구하는 것입니다.

 

클락 솔리테어는 위에서 분석한 숫자 카드 게임과 매우 흡사하죠. 사실 위 숫자 카드 게임은 제가 연구실 동료에게 클락 솔리테어의 분석에 대해서 설명했을 때, 연구실 동료가 그 문제를 좀더 단순한 형태로 표현한 것입니다. 약간만 달라졌을 뿐인데, 문제를 이해하기에 훨씬 수월해지는 효과가 있더군요. 연구실 동료의 천재성에 다시 한 번 감탄하고 갑니다. 여하튼 위 분석을 약간만 확장하면 클락 솔리테어를 이기는 확률이 정확히 \( \frac{1}{13} \)이 된다는 것을 확인할 수 있습니다.

 

이 내용을 공부하면서 발견한 교과서가 확률 알고리즘(randomized algorithm)을 자세히 다루는 것 같아 보입니다. 학부 때든 대학원 코스워크 중일 때든 확률 알고리즘을 공부할 기회가 잘 없었는데, 좋은 교과서를 발견하여 기쁘군요. 다행히 학교 도서관에 비치되어 있는 것을 확인했습니다. 내일 당장 빌리러 가야겠군요.

 

궁금하신 점이 있으시거나 글 내용에 오류가 있는 경우에는 알려주시기 바랍니다. 고맙습니다. :)

참조

[1] Rajeev Motwani and Prabhakar Raghavan. Randomized algorithms. Cambridge university press, 1995.