[Loop Strategy] Peter Bro Miltersen - 100명의 죄수 문제

서론

요즘 들어 다시 생각해보면, 죄수의 딜레마서부터 죄수들은 항상 많은 문제에 처한다. 🤣 가상의 상황임에도 불구하고 이러한 문제들은 많은 시사점을 남겨주고, 심지어는 세상의 발전에 중요한 역할을 하기도 한다.

다양한 문제 중에서 내가 가장 좋아하는 내용은 불규칙한 상황에서 특정한 규칙을 찾아내는 것인데, 우연히 유튜브 영상을 보게 되면서 이건 언젠가 실무에 사용할 수 있을 것 같아 블로그에 기재한다. 또한, 자세한 내용은 유튜브를 참고하면 되기 때문에 핵심만 정리하여 추후에 참고할 때 빠르게 참고할 수 있도록 이 글을 작성해본다.

유튜브 : https://youtu.be/PE4vLbyOgw0 

문제정의

1. 100명의 죄수들은 1~100까지의 번호를 가지고 있음
2. 1~100까지의 적힌 종이가 방 안에 들어있는 100개의 상자 안에 랜덤하게 들어가 있음
3. 각 죄수는 방에 들어가 50개의 상자를 열 수 있음
4. 50개를 열어 본 뒤 방을 떠나고, 방을 나온 사람은 소통 불가
5. 100명의 죄수들이 모두 자신의 번호를 찾는다면 석방, 한 명이라도 못찾으면 모두 처형
6. 죄수가 방에 들어가기 전까지 전략 회의 가능

+ 나무위키 문제설명

결론

결과적으로 승리 확률을 높이기 위해서는 자신의 번호에 해당하는 박스를 열고, 그 박스에 들어있는 내용의 순번을 따라 다음 박스를 열어보는 것이다. 이러한 과정은 결과적으로 모든 순번은 닫혀있도록 구성되어 있고, 내가 처음에 연 박스는 이 루프의 마지막 박스로부터 오게 될 것임으로 결과적으로 "본인 번호가 적힌 상자에서 시작한 것이 해당 번호가 적힌 쪽지가 존재하는 루프에 있다는 것을 보장" 한다. 즉 터무니없는 확률에서 약 30%대의 확률로 승률을 올릴 수 있다.

• 한명의 실패는 전체의 실패임을 인지할 것, 즉, 한명이 실패하든 100명이 모두 실패하든 동일한 결과
• 모두가 성공할 수 있는 확률을 높이기 위해서는 루프 전략이 더 적합함
• 루프 전략을 사용하게 된다면 모두 같이 이기거나 실패함

확률 도출

단순하게 1/2 확률로 모든 죄수가 우연하게 통과할 확률 : (1/2)^100
루프를 만들어서 모두 통과할 확률 : 1-(1/51+1/52+1/53+...+1/100) = 31.18%

루프로 해결하는 방식을 일반화한다면 약 30.7% 수렴

핵심 포인트

이 문제에서 도출해낸 포인트는 다음과 같다.

• 무작위 같은 상황에서도 패턴이 보일 수 있음
  • 일반적으로 무작위처럼 보이더라도 정렬, 루프 등 특정한 방식이 있을 수 있음
  • 벤포드의 법칙처럼 실제로는 무작위적이지 않은 경우도 있음
• 문제를 더 자세히 정의하고, 목표에 따라 증명할 부분을 재고해 볼 것
  • 기존 정의 : 100명의 죄수들이 각 50개의 박스를 열어서 모두가 통과할 확률
  • 재정의 : 루프의 길이가 50 이하가 될 확률
• 개별 확률은 전략에 의해 바뀔 수 있음

Random vs Loop Strategy

응용지점

• 특정 확률을 유도하고 싶다면 박스를 열수 있는 수를 조정하거나, 인원수를 조정할 수 있음
  • 다만 오픈 가능한 박스 수를 과반수 미만으로 설정하게 되면, 루프 길이가 초과되는 그룹이 2개 이상 만들어지기 때문에 확률 계산을 지금과는 다르게 해야 함 (예를 들면, 30개만 가능할 경우, 31,31,31,7이 되면서 한 그룹이라도 30개가 넘어갈 확률로 계산해야 함)