카드를 몇 번 섞어야 무작위에 가까워질까: 리플 셔플과 컷오프 현상

마술사 출신 수학자 퍼시 다이아코니스와 데이브 베이어는 1992년 카드를 리플 셔플로 섞을 때 무작위에 가까워지려면 몇 번이 필요한지를 수학적으로 분석했다. 영상은 이 연구를 출발점으로 삼아 카드 섞기의 기준을 따져 본다.

이승재 교수는 패 하나를 보고 무작위인지 아닌지를 가리는 것은 어렵다고 말한다. 1234처럼 정렬된 패와 우연히 그렇게 나온 패는 모양만으로는 구분할 수 없기 때문이다. 그래서 잘 섞였는지는 어떤 과정으로 섞었는지를 물어야 한다는 것이 그의 설명이다.

수학에서는 무작위로 섞은 경우가 만드는 분포와 리플 셔플이 만드는 분포를 비교한다. 사람이 직접 섞을 때는 속임수가 개입할 수 있어 카지노에서는 기계를 쓰는 이유도 같은 맥락에서 설명된다.

진행자는 1992년 연구에서 52장 카드를 리플 셔플로 약 일곱 번 섞어야 무작위에 가까워진다는 결과를 소개하며, 직접 한두 번, 세 번 섞어 본 경험을 이야기한다. 세 번 정도 섞으면 거의 무작위처럼 보여서 이 정도면 충분하다고 느꼈다는 것이다.

이승재 교수는 그 느낌이 수학적 기준과 다르다고 답한다. 눈으로 보기에는 무작위 같아도 확률 분포 기준으로는 거의 섞이지 않은 상태일 수 있으며, 사람들이 충분하다고 느끼는 기준과 수학적 기준이 어긋난다는 점이 이 대목의 핵심이다.

이승재 교수는 무작위로 섞을 때 가능한 모든 배열을 생각해 보면, 52장 중 한 장을 고르고 다음에 51장 중 한 장을 고르는 식으로 이어져 52!가지가 된다고 설명한다. 그 값은 대략 10의 68승으로, 우주의 별 개수보다 많다.

이만큼 많은 배열을 사람이 하나씩 확인하는 것은 불가능하다. 그래서 무작위 섞기가 만드는 분포와 리플 셔플이 만드는 분포를 확률로 비교하는 방식이 쓰인다.

이 연구는 두 확률 분포가 얼마나 다른지를 재는 기준으로 총 변동 거리, 곧 전 변동 거리라고도 부르는 토탈 베리에이션 디스턴스(TVD)를 쓴다. 이승재 교수는 52장을 한꺼번에 다루기 어려우므로 카드 네 장으로 예를 든다.

공정하게 속임수 없이 네 장을 뽑으면 각 카드가 처음 나올 확률은 모두 같아야 한다. 이 가정이 중요하다는 점을 교수는 강조한다.

이승재 교수는 누가 봐도 공정해 보이는 손동작이라도 확률이 한쪽으로 치우치면 공정하지 않다고 말한다. 예를 들어 처음 A가 나올 확률이 40%, 2가 30%, 3이 20%, 4가 10%로 나타나는 사람이 있다고 가정한다.

공정하다면 네 장 모두 처음에 나올 확률이 25%여야 한다. 이런 기술이 들어가면 안 된다는 것이 교수의 판단이다.

앞의 예에서 각 카드의 확률과 공정 기준 25%의 차이는 A 15%p, 2 5%p, 3 5%p, 4 15%p다. 이승재 교수는 차이가 서로 상쇄되지 않도록 절댓값을 씌운 뒤 모두 더하고, 그 합을 반으로 나눈다고 설명한다.

이 예에서 계산하면 합이 40이므로 반을 나눠 20%가 나온다. 값이 0이면 두 분포에 차이가 없고, 차이가 극단적이면 1에 가까워진다.

진행자가 왜 이 연구에서 총 변동 거리를 기준으로 삼았는지 묻자 이승재 교수는 학계에서 가장 흔히 쓰이는 대표적인 기준 중 하나이고, 설명하거나 보여 주기도 쉽기 때문이라고 답한다.

교수는 평균을 가장 흔하게 쓰는 것처럼 두 분포를 비교할 때 총 변동 거리가 대표적인 수치라고 덧붙인다. 0.2라는 값도 차이가 나름 있는 숫자라고 본다.

리플 셔플은 보통 52장을 26장씩 나눠 한 장씩 번갈아 떨어뜨리는 것으로 생각하기 쉽다. 그러나 이승재 교수는 이렇게 하면 이상적이지 않다고 말한다. 실제로는 정확히 26장씩 나누기 어렵기 때문이다.

진행자는 A부터 8까지 줄을 세운 카드를 가지고 직접 시연했다. 교수는 이 시연으로 리플 셔플의 실제 모습을 확인해 볼 수 있다고 설명한다.

진행자는 8장의 카드를 반씩 나눠 섞는 리플 셔플을 두 차례 시연했다. 중간에 한 장씩 떨어뜨리는 손동작까지 포함해 진행됐다.

두 번째 섞기가 끝난 뒤 A 2 3 4 5 6 7 8 순서가 그대로 돌아왔다. 이승재 교수는 아무 짓도 하지 않은 것처럼 보이는 결과가 나왔다는 점을 짚는다.

실제로는 정확히 26장씩 자르기 어렵다는 점을 먼저 고려해야 한다. 이승재 교수는 카드를 어디서 자를지에 무작위성을 부여하는 방식을 쓴다고 설명한다.

예를 들어 52개의 동전을 던진다고 생각하면 앞면이 정확히 26번 나오지 않고 25번이나 27번 나올 수도 있다. 이와 같이 자르는 장수가 이항 분포를 따르도록 하고, 가장 공정하게 중간을 자르는 보정을 더한다.

위 더미에 30장, 아래 더미에 20장이 있다고 하자. GSR 모델에서는 모든 카드가 내려올 확률이 똑같다고 본다. 전체 50장 중 위 더미 카드가 먼저 내려올 확률은 30/50이고, 아래 더미 카드는 20/50이다.

한 장이 떨어진 뒤에는 남은 장수로 확률을 다시 계산한다. 이렇게 하면 한 번에 여러 장이 떨어지는 실제 손동작까지 반영할 수 있다. 교수는 이 모델이 리플 셔플을 수학적으로 옮긴 기본 틀이라고 설명한다.

이승재 교수는 결과를 먼저 밝힌다. GSR 모델로 네 번 셔플했을 때 총 변동 거리는 1에 거의 수렴한다. 수학적으로는 거의 섞이지 않았다는 뜻이다.

세 번 셔플만으로는 가능한 전체 배열을 만들기에 턱없이 부족하다. 다섯 번쯤 되면 값이 0.9 부근으로 내려가기 시작하고, 일곱 번이 되면 약 0.33에 이른다. 교수는 총 변동 거리가 0.5 아래로 떨어지면 무작위에 가깝다고 볼 수 있으며, 앞서 0.2는 잘 섞였다고 말할 수 있는 수준이라고 정리한다.

상승 수열은 카드 배열에서 순서대로 올라가는 연속 구간을 뜻한다. 이승재 교수는 52부터 1까지 거꾸로 놓인 배열에서는 상승 수열이 52개 생긴다고 설명한다.

그러나 네 번 리플 셔플을 하면 만들 수 있는 상승 수열의 최대치는 16개뿐이다. 따라서 52부터 1까지 거꾸로 가는 배열은 네 번 섞어서는 애초에 만들 수 없다. 다섯 번을 해도 마찬가지다.

이승재 교수는 셔플 횟수에 따라 무작위성이 서서히 좋아지는지, 아니면 어느 순간 갑자기 달라지는지를 묻는다. 그는 확률과 무작위성 분야에는 임계점과 비슷한 컷오프 현상이 있으며, 리플 셔플이 대표적인 예라고 답한다.

네 번까지 총 변동 거리는 사실상 1에 머문다. 여섯 번쯤 되면 64개 정도의 상승 수열이 생길 수 있지만 아직 부족하고, 일곱 번이면 128개의 상승 수열이 가능해져 이때부터 섞였다고 할 수 있다.

직관적으로는 한 번보다 두 번, 두 번보다 세 번 섞을수록 조금씩 좋아진다고 생각하기 쉽다. 그러나 실제 결과는 이와 달랐다. 두 번만 섞으면 두 번 섞어서 나올 수 있는 배열만 나오고, 상승 수열이 네 개 이상 포함된 배열은 전혀 나오지 않는다.

총 변동 거리를 계산하면 처음에는 0.999처럼 거의 1에 가까운 값이다. 다섯 번에도 0.9 대의 값이 남아 있다가, 6~7번쯤에 갑자기 꺾여 떨어진다. 교수는 이런 현상을 컷오프 현상이라고 부른다.

이승재 교수는 컷오프 현상이 카드에서만 나오는 것이 아니라 확률 분포와 무작위가 섞인 여러 곳에서 관찰된다고 말한다. 사다리 게임도 같은 현상을 보인다는 것이다.

사다리 세 개만 쓰면 시작점과 도착점의 4! 가지 경우가 균등하게 나오지 않는다. 직접 계산해 보면 사다리가 다섯이나 여섯 개쯤 되면 거의 섞이기 시작하고, 여섯 명이 참여하는 경우 대략 20~30개 정도는 그어야 무작위에 가깝다는 결과가 있다.

현실에서는 사람들이 그렇게 많이 긋지 않기 때문에, 원하는 곳 근처에 떨어질 확률이 생각보다 높게 나타난다.

이승재 교수는 분자의 운동이나 자기장 속 자성이 어떻게 분포되는지를 다루는 물리 분야에서도 컷오프 현상이 대표적으로 구현된다고 설명한다. 초기 배열과 상관없이 무작위로 섞이는 과정을 연구하는 것이다.

컴퓨터 과학에서도 구글의 페이지 랭크 알고리즘이나 딥러닝처럼 무작위성을 집어넣는 방법에서 같은 문제가 다뤄진다. 교수는 이런 과정을 MCMC, 곧 마르코프 체인 몬테카를로 같은 기법으로 설명한다.

이승재 교수는 수학적 무작위성이 초기 조건과 상관없이 모든 경우가 공평하게 나오는지를 묻는 개념이라고 정리한다. 일상에서 쓰는 무작위와는 조금 다르며, 그 차이를 아는 것이 중요하다고 말한다.

진행자는 이번 대담에서 리플 셔플 속의 무작위성과 실생활의 무작위성이 어떻게 다른지, 그리고 수학적 정의가 왜 중요한지를 함께 살펴봤다고 마무리했다.