HOME » 사다리 게임, 절대 걸리지 않는 법
사다리 게임, 절대 걸리지 않는 법
2018년 1월 15일 초안 작성
본론
실험 증명
확률과 통계 문제만큼 컴퓨터로 실험하기에 좋은 주제도 흔치 않다. 개인적으로 가장 존경하는 과학자가 실험 과학자로 유명했던 마이클 패러데이이기도 한데, 아인슈타인 또한 그를 존경해 침실 벽면에 그의 초상화를 걸어두었다고 한다.
컴퓨터를 이용한 최초의 수학 증명은 1976년 4색 정리였다. 당시에는 1,936개의 도형 분할을 계산하는 데에 컴퓨터로 50일이 넘게 걸렸고, 수학적으로 우아하지 못하다는 비판도 잇따랐다. 그러나 역사적으로 볼때 공학 기술은 언제나 이론을 앞서갔다.
얼마 전에 본 해커를 위한 통계학 발표도 인상적이었다. 수학적 통계 명제를 해커들이 컴퓨터 실험으로 직접 증명해 보이는 방식은 무척 신선했다. 이 발표를 본 이후로는 수식을 마주칠 때마다 실험으로 확인해보고 싶어지는 습관이 생길 정도다. 최근에는 수능 수학 문제를 코드로 풀어보는 시도도 깊은 인상을 남겼다. 공식을 외워서 푸는 방식이 아니라 코드로 공식을 유도하고 컴퓨터 계산으로 풀어내면 수학의 원리를 깨우치는 동시에 진정한 수학의 재미를 느낄 수 있다.
이 글에 사용한 도구는 파이썬과 주피터 노트북, 그리고 컴퓨터뿐이다. 모든 도구는 무료로 갖출 수 있다. 여기서도 같은 도구로 풀이해보겠다.
한중일 전통 게임
먼저 관련 통계 자료를 찾아봤다. 사다리 게임이라면 한 번쯤 통계학에서 관심 가질 만한 주제인데 자료가 너무 없다. 왜 이런가 살펴봤더니 사다리 게임이란 것이 한중일에서만 통용되는 게임이었다. 영미권에서는 이 게임이 없으니 영어로 된 통계책에는 사다리 게임이 한 번도 등장하지 않았던 것이다. 그러고 보니 『통계의 힘』 도 일본 책이고, 사다리 게임을 다룬다며 간간히 접한 자료들도 죄다 한국어로 된 것뿐이었다.
그뿐만 아니라 사다리 게임을 제대로 구현한 오픈소스도 찾을 수가 없었다. 누군가 만들어두었을 법한데, 동아시아권에 한정된 게임이다 보니 영어로 쓰인 코드가 아예 없었다. 생각해보면 이 글 또한 아무리 자세히 풀어 쓴들 한국어로 쓰인 이상 영어권에서는 이 글을 발견하지 못할 것이다. 아쉬운 부분이다.
구현 실험
결국 사다리 게임을 직접 구현해보기로 했다. 최대한 단순하게 만들기 위해 각 다리(세로줄)와 계단(가로줄)을 모두 2차원 배열에 표현하고 출발지에서 시작해 단계별로 계단 유무를 판별하여 이동시켜 최종 도착지의 값을 구하는 방식으로 구현했다.
먼저 『통계의 힘』 책에 나온 결과부터 살펴보자. 8개의 다리가 있고, 12개의 계단이 있다. 4번이 술래일때 1,000번의 반복 시뮬레이션 결과로 다음을 제시했다.
같은 조건으로 직접 실험해봤다.
책에서와 비슷한 정규분포가 나온다. 3번과 5번에서 미세하게 모양이 달랐지만, 이는 실험 횟수가 부족한 탓으로 보인다. 큰 수의 법칙Law of large numbers에 따라 실험 횟수가 충분히 늘어나면 거의 동일한 형태로 수렴할 것이다.
출발지에 따른 결과 분포
그렇다면 출발지를 바꾸면 결과 분포는 어떻게 달라질까. 보통 우리는 사다리 게임이 공평하리라 기대한다. 그래야 이 게임이 수백 년간이나 이어져 내려올 수 있었을 테니까. 그 통념을 검증하기 위해 ‘사다리 게임은 공평하지 않다’를 귀무가설Null Hypothesis로 세우고 이를 기각하는 방향으로 데이터를 살펴보겠다.
같은 조건(8개의 다리, 12개의 계단, 1,000번 반복)으로 출발지에 따른 결과 분포를 실험한 결과는 다음과 같다.
이대로만 보면 전혀 공평하지 않다.
중앙 부근에서 출발하면 항상 정규 분포를 띄며, 심지어 끝에서 끝까지는 도달하지도 못한다. 1번에서 출발하면 8번에는 절대 도착할 수 없다는 뜻이다. 다시 말해 8번이 술래일 때 1번을 택하면 절대로 걸리지 않는다는 얘기가 된다. 과연 그럴까. 정말로 사다리 게임은 불공평한 게임일까.
계단 수에 따른 결과 분포
여기서 1번에서 출발하면 8번에 도달할 수 없다는 점에 다시 주목해보자. 왜 도달하지 못할까. 이래서야 게임 자체가 성립할 수 없을 텐데, 혹시 계단의 개수가 부족해서 그런 건 아닐까. 그렇다면 계단 개수를 늘려가며 실험해보자.
계단의 갯수를 10개에서 시작해 400개까지 차츰 늘렸을 때, 1번에서 출발했을 경우의 도착점 분포다. 실제 확률에 가깝게 근사하도록 매번 1만 회씩 충분히 시행했다.
계단이 적을 때는 분포가 한쪽으로 확연히 치우친다. 그러나 점점 균등 분포Uniform Distribution를 띈다. 유의수준Significance Level은 통계학의 아버지 피셔가 일찍이 제안한 관례에 따라 5%로 잡았다. 여러 번의 실험 끝에 균등 분포에 95% 이상 일치하는 지점이 대략 계단 300개 부근임을 확인했고, 이로써 계단이 300개 이상일 때 ‘사다리 게임은 공평하지 않다’는 귀무가설을 기각할 수 있었다.
수식
일본어 위키피디아에 따르면 참가자가 \(N\)명일 때 필요한 계단의 갯수를 계산하는 수식은 아래와 같다.
우리의 실험값과 약간 차이가 있는데 이는 상수 계수를 생략한 대략적인 추산이기 때문이라 큰 의미는 없다. 중요한 점은 이 수식이 지수 함수 형태라는 점이다. 즉, 참가자(다리의 수)가 늘어날술폭 필요한 계단의 수가 기하급수적Exponential으로 증가한다.
실제로 이 수식에 대입해보면 \(N=8\)일 때 392, 9일 때는 576, 10일 때는 810이 나온다. 참가자가 10명이면 8명일 때보다 2배나 많은 계단이 필요하다는 얘기다.
현실
계단의 수가 충분하면 사다리 게임은 공평하다. 적어도 우리가 수백 년간 이어온 이 게임이 잘못되지 않았다는데 안도한다. 그러나 현실적으로 8명이 하는 게임에 계단을 300개나 그릴수는 없다. 참가자가 늘수록 필요한 계단 수는 무한히 늘어난다. 여러 사람이 모여 연습장에 빠르게 그려서 하는 사다리 게임의 특성상 『통계의 힘』 책에서 조언한 대로 확률적으로 낮은 자리를 택하는 것이 유리하다.
12개일때 결과 분포
그렇다면 다시, 계단이 12개일 때 결과 분포가 어떤 형태인지 살펴보자. 대부분의 사다리 게임에서는 이처럼 계단 수가 부족할텐데, 이때 어느 자리가 확률적으로 더 낮은지 실험으로 확인해보자.
이번에는 실제 확률에 훨씬 더 가깝게 근사하도록 각각 10만 회씩이나 시행해봤다. 앞서 ‘출발지에 따른 결과 분포’와 달리, 결과가 들쑥날쑥하지 않고 고르게 분포한 것을 확인할 수 있다.
마찬가지로 정규 분포 형태를 띄는데 특이한 점이 있다. 2번에서 출발하면 2번에 도착하는 것보다 오히려 1번에 도착할 확률이 더 높다는 점이다. 마찬가지로 7번에서 출발하면 8번에 도착할 확률이 가장 높다. 이런 경향은 3번에서도 이어진다. 1,2번에 도착할 확률이 나머지 4,5,6,7,8 모두를 합친 것 보다 더 높다. 6번도 마찬가지다. 분포가 가장자리 쪽으로 쏠리는 현상이 뚜렷이 보인다.
즉 도착점이 한쪽으로 치우쳐 있다면 가능한 한 그 반대쪽을 택해야 걸릴 확률이 낮다는 사실을 실험으로 확인할 수 있다.
TL;DR
지금까지의 내용을 정리하면 이렇다.
- 충분히 많은 계단을 그리면(8명이 참가할 경우 최소한 300개) 도착점은 고르게 분포한다. 그러나 현실적으로 그렇게 많이 그릴 수 없다.
- 따라서 출발점은 도착점에서 가능한 먼 곳을 택한다.
- 도착점이 한쪽으로 치우쳐Skewed 있는 경우 걸릴 확률은 치우쳐 있는 방향이 더 높다. 따라서 반대 방향을 택해야 한다.
- 도착점이 오른쪽에 치우쳐 있는 경우 출발점은 가능한 왼쪽으로 멀리 택한다.
- 도착점이 왼쪽에 치우쳐 있는 경우 출발점은 가능한 오른쪽으로 멀리 택한다.
정리
이제 여러분은 더 이상 점심을 사지 않아도 된다.
물론 처음 한두 번은 운 나쁘게 걸릴 수도 있다. 하지만 1년 내내 사다리 게임으로 점심 내기를 하기로 했고, 여러분이 이 글의 내용을 충분히 숙지한 채 임한다면, 큰 수의 법칙에 따라 여러분은 그해 점심을 가장 적게 산 사람으로 기억될 것이다.
통계의 마법이다.
