카드는 일곱 번 섞어야 한다
카드 덱을 반으로 갈라 섞어 보세요
52장의 카드 한 덱을 반으로 갈라 손가락으로 촤르륵 맞물리게 섞는 리플 셔플(Riffle Shuffle)을 해 봅니다.
한두 번 섞어서는 원래 순서의 흔적이 그대로 남아 있고, 서너 번도 부족합니다. 그런데 딱 일곱 번을 섞는 순간 급격하게 완전한 무작위 상태로 뒤바뀝니다. 왜 대충 섞이지 않고 7번에서 갑자기 마법처럼 섞일까요?
이야기
Steve Castillo Photos
Public domain · 위키미디어 공용
퍼시 다이아코니스는 열네 살에 집을 나가 마술사가 되었습니다. 당대 최고의 카드 마술사 다이 버넌을 따라다니며 십 년을 보냈고, 스물넷에 다시 학교로 돌아갔습니다. 카드가 정말 섞이는지 알고 싶어서였습니다. 그는 뒷날 스탠퍼드 대학 교수가 됩니다.
1992년 그는 데이브 베이어와 함께 답을 냈습니다. 리플 셔플로 일곱 번이면 충분하다는 것이었습니다.
그런데 「일곱」은 못 박힌 수가 아닙니다. 무엇을 「섞였다」로 볼지 잣대를 바꾸면 답도 바뀝니다. 어떤 잣대로는 여섯 번으로 충분하고, 마술사가 알아채는 정도까지 따지면 더 많이 섞어야 합니다. 「일곱 번」은 하나의 잣대가 준 답입니다.
재미있는 것은 갑자기 섞인다는 점입니다. 다섯 번까지는 원래 차례가 상당히 남아 있는데, 여섯째와 일곱째에서 절벽처럼 떨어집니다. 이것을 「차단 현상」이라 합니다.
왜 갑자기일까요. 한 번 섞을 때마다 가능한 배열의 수가 두 배씩 늘어나기 때문입니다. 카드 오십두 장의 배열은 어마어마하게 많아서, 두 배씩 늘어나도 한참은 표가 안 나다가 어느 순간 단번에 따라잡습니다.
카지노가 카드를 몇 번 섞을지 규정으로 정합니다. 다섯 번으로는 규칙이 남아 있습니다.
「얼마나 섞어야 무작위가 되는가」를 다루는 이론(마르코프 연쇄)이 컴퓨터의 난수 생성과 인공지능의 표본 추출에 그대로 쓰입니다.
계단 넷 — 같은 사실을 네 깊이로
카드를 섞어 순서를 살펴본다
새 카드 덱을 뜯어 순서대로 정렬한 뒤 리플 셔플을 한 번 해 봅니다. 카드를 펼쳐보면 원래 순서의 긴 띠들이 그대로 살아 있습니다.
두 번, 세 번 섞어도 카드 마술사들은 원래 카드를 쉽게 찾아냅니다. 네 번, 다섯 번, 여섯 번... 일곱 번째 셔플을 마치는 순간 비로소 이전의 모든 순서 정보가 완벽히 증발해 어떤 카드도 예측할 수 없게 됩니다.
카드를 섞어 보세요
6 번까지는 규칙이 남아 있고, 7 번째에 확 무너집니다.
섞임을 세는 방법
카드를 반으로 나눠 맞물려 섞을 때 카드가 쪼개지는 상승 수열(Rising Sequences)의 개수를 셉니다. 한 번 셔플하면 최대 2개의 상승 수열이 생기고, 번 셔플하면 최대 개로 늘어납니다.
52장의 순열 가지가 골고루 나타나려면 가 52보다 훨씬 커야 하며, 수학적 오차가 무의미해지는 임계점이 정확히 7번입니다.
갑자기 무너집니다
이런 것을 「차단 현상(cutoff)」 이라 부릅니다.
변동거리와 수렴
수학자이자 마술사인 퍼시 디아코니스와 데이비드 바이어는 1992년 길버트-섀넌-리드(GSR) 셔플 모델을 통해 전변동 거리(Total Variation Distance)를 정밀 계산했습니다.
셔플 횟수에 따른 불완전도 그래프를 그리면 5번까지는 1에 가깝다가 6번(0.61), 7번(0.33)에서 수직 낙하하듯 뚝 떨어지는 차단 현상(Cutoff Phenomenon)을 엄밀히 증명했습니다. 8번은 0.17로 7번이면 충분합니다.
장수에 따라 다릅니다
카드가 백만 장이어도 30 번이면 됩니다 — 로그의 힘입니다.
마르코프 연쇄
카드 셔플 연구는 마르코프 연쇄(Markov Chain)의 혼합 시간(Mixing Time) 이론을 혁명적으로 발전시켰습니다.
상태 공간이 거대한 복잡계에서 평형 상태(Stationary Distribution)로 수렴할 때 점진적이 아니라 특정 시점에서 계단식으로 급변하는 상전이(Phase Transition) 현상은 통계물리학의 이징 모델(Ising model)과 현대 MCMC 알고리즘 수렴 속도 평가의 핵심 도구입니다.
완벽한 섞기는 안 섞입니다
완벽함이 오히려 안 섞습니다 — 어설픔이 무작위를 만듭니다.
풀어 보기
카드 셔플과 전변동 거리. 52장의 카드 한 덱을 리플 셔플할 때 셔플 횟수 에 따른 전변동 거리를 라 하자.
(1) 52장의 카드를 일렬로 나열하는 모든 경우의 수를 기호로 나타내시오.
(2) 번의 리플 셔플로 생성될 수 있는 최대 상승 수열(Rising sequence)의 개수를 의 거듭제곱으로 쓰시오.
(3) 바이어와 디아코니스의 연구에 따르면 5번 셔플 시 에서 7번 셔플 시 으로 급격히 떨어지는 현상의 명칭을 쓰시오.
(1) , (2) , (3) 차단 현상(Cutoff phenomenon)입니다.
답과 풀이 보기
(1) 가지입니다 (약 ).
⭐ 우주가 생긴 뒤 흐른 시간을 초로 세어도 남짓입니다. 카드 한 벌을 잘 섞으면 인류 역사에서 단 한 번도 없던 순서가 나옵니다.
(2) 개입니다.
리플 셔플 한 번은 덱을 둘로 갈라 섞는 것이므로 상승 수열이 최대 2 배가 됩니다.
가 되려면 — 여기서 이미 6 이라는 숫자가 보입니다.
(3) 차단 현상(cutoff phenomenon)이라 합니다.
섞을수록 조금씩 고르게 되는 것이 아니라, 어느 지점까지는 거의 그대로 있다가 갑자기 무너집니다.
(거의 안 섞임) → → →
그래서 7 번이 기준이 되었습니다.
1992 년 바이어와 디아코니스의 이 결과는 신문 1 면에 실렸습니다. 카지노에서 몇 번 섞어야 하는가가 걸린 문제였기 때문입니다.
디아코니스는 원래 열네 살에 집을 나간 마술사였습니다. 카드 다루는 손재주를 수학으로 옮긴 셈입니다.
⛔ 세 번만 섞고 나눠 주면 순서가 상당히 남아 있어 유리해질 수 있습니다.
여기 「풀어 보기」는 기본 한 벌입니다. 더 풀어 보고 싶으면 행복수학의 그 단원으로 건너가세요.
더 멀리
「얼마나 섞어야 하나」는 계산에서 중요한 물음입니다.
- 마르코프 연쇄 — 무작위 과정이 안정 상태에 이르는 시간을 다룹니다
- 난수 생성 — 컴퓨터가 무작위를 만들 때 같은 이론을 씁니다
- 카지노 — 실제로 섞는 횟수를 규정으로 정해 두는 곳이 있습니다
이어지는 장
카드를 대충 서너 번 섞으면 이전 순서의 흔적이 고스란히 남아있듯이, 무작위처럼 보이는 일련의 사건에서도 독립성에 대한 오해가 생기면 도박사의 함정에 빠지게 됩니다 — 제90장 에서 우연과 독립시행의 진짜 얼굴을 다시 점검해 보세요.
영감을 받은 곳
수학자이자 마술사인 퍼시 디아코니스(Persi Diaconis)와 데이브 바이어(Dave Bayer)가 1992년 《응용확률연보》(The Annals of Applied Probability)에 발표한 논문 「Trailing the Dovetail Shuffle to its Lair」에서 리플 셔플의 임계 전이(cut-off)를 수학적으로 증명했습니다.