7번 완벽 섞으면 카드가 무작위다. 뒤섞은 경우는 몇 번일까?

출처: Hacker News

1992년, 수학자들은 7개의 “리플 셔플”(https://www.stat.berkeley.edu/~aldous/157/Papers/bayer_diaconis.pdf)을 통해 덱을 섞는 것이 충분하다는 것을 증명했습니다. 여기서 플레이어는 카드를 두 손에 나눠 한 손에 있는 쪽에서 thumb으로 뒤섞으며 지퍼 모양처럼 다시 합칩니다.

When Dave Bayer and Persi Diaconis came up with this proof, they also revealed something surprising about what happens along the way: At first, the cards stay relatively orderly. But with that seventh shuffle, the deck suddenly tips into a highly unstructured state.

이때 나타난 현상은 cutoff phenomenon(단축 현상)이라고 부릅니다. 이 현상은 카드 외에도 많은 동역학적 시스템 — 예를 들어 condensed matter physics의 “spin glasses” — 가 보인다고 믿어집니다([link]).

Unfortunately, Bayer and Diaconis’ proof — referred to by some as a mathematical miracle — only works if you adhere to some rigid constraints about how to cut and shuffle the deck. If you shuffle more like a middle schooler than a magician, the result doesn’t hold.

이제 세 명의 수학자는 더 정확한 셔플로 이 결과를 확장했습니다. Mark Sellke, 하버드 대학교 통계학자(현재 OpenAI에서 근무 중)이며, Jialu Shi와 Jiamin Wang (프린스턴 대학교 및 케임브리지 대학교 대학원생)으로 구성된 팀은, 덱을 두 개의 완벽하게 균등한 부분으로 나누지 않아도 리플 셔플에서 단축 현상이 존재함을 증명했습니다.

Diaconis는 자신의 업데이트에 대해 매우 열광했습니다. “새로운 아이디어이고, 이렇게 효과적으로 작동할 수 있을 줄은 정말 놀랍다”고 말했습니다. “아주 brillante한 수학의 작품입니다.”

Mixing Cold Spots

The humble riffle shuffle is far from “complicated.” The number of possible arrangements for an ordinary deck of cards is 52 factorial — that is, 52 × 51 × 50 × … × 3 × 2 × 1, or (roughly speaking) an 8 followed by 67 zeros, close to the estimated number of atoms in our galaxy. Another way to put the figure into context: Every time you shuffle a deck of cards, you produce a configuration that has almost surely never existed before, and never will again.

하지만 카드 섞기에 대한 수학적 관심은 그 조합적 복잡성 이상을 넘어서 있습니다. 1981년, Diaconis와 Mehrdad Shahshahani 단축 현상을 발견했으며, 이후 수학자들은 이를 여기저기서 찾아냈습니다.

Persi Diaconis는 14세 때 집을 나와 마술사와 함께 일하기 시작했고, 10년 뒤 학교에 돌아왔으며 전문 수학자가 되었습니다. 카드 트릭은 그의 연구에서도 계속 중요한 역할을 합니다.

Caroline Gates

차가운 스팟 혼합

Cutoffs는 물리에서의 phase transitions와 유사합니다. 예를 들어, 0도에서 물이 갑자기 얼어 고체가 되는 현상처럼 말이죠. 하지만 cutoffs는 “Markov chains”라는 수학적 모델 — 시스템(예: 카드 덱)이 다양한 구성 사이를 확률적으로 이동하는 방식 — 에서 발생합니다.

Cutoff 현상은 이름 그대로 Ernest Hemingway가 빈곤에 빠지는 과정을 설명한 것처럼, 서서히 진행되다가 갑자기 일어납니다. cutoffs는 “대부분의 대형 복잡계”에서 나타난다고 Sellke가 말했으며, 이러한 현상을 일반 이론으로 증명하는 것은 어렵습니다. “대부분의 cutoffs가 존재할 것으로 예상되는 문제들에서 어떻게 증명을 해야 할지 모르는 경우가 많습니다,”라고 Laurent Saloff-Coste, 코넬 대학교 수학자이자 Diaconis와 협업한 사람이 말했습니다.

그래서 “7번 셔플이면 충분하다”는 teorema는 큰 의미가 있었습니다. Bayer와 Diaconis — adolescente 시절에 마술사에게서 카드 트릭을 배우기 위해 집을 나섰고, 이후 저명한 수학자가 된 사람들 — 는 단순히 실제 세계에서 정확한 단축 현상이 존재함을 보인 것이 아니라, 그 단축이 어디서 발생해야 하는지를 알려주는 단일 공식을 제공했으며, 이 공식은 어떤 덱 크기에도 적용되었습니다.

하지만 조건부도 있습니다. 첫째: 리플 셔플은 카드를 좌우 쪽에서 한 장씩 무작위로 섞는 현실적인 엄격한 모델을 따라야 합니다(각 카드는 남은 카드 수에 비례하는 확률로 왼쪽 혹은 오른쪽 쪽에서 떨어집니다. 이는 단순히左와 右가 번갈아 가며 떨어지는 predictable한 구조를 만들지 않고, “왼쪽, 오른쪽, 오른쪽, 왼쪽, 오른쪽, 왼쪽, 왼쪽”과 같은 순서가 나올 수 있음을 의미합니다).

둘째: 셔플하기 전에 덱을 거의 절반으로 나눠야 합니다.

“우리의 모든 분석은这些细节에 의존합니다,” Diaconis는 말했습니다.

1999년, Steven Lalley, 시카고 대학교 수학자이자 갈톤 연구소 소장,는 [이 제약 조건을 완화하려] 시도했습니다. 그는 대략 균등하게 나눈 덱이 아닌 리플 셔플에 대한 단축 증명을 찾고자 했습니다. “제게 자연스럽게 떠오른 질문은 — بعض 사람들은 덱을 약간 위쪽이나 아래쪽으로 자르기도 한다는 것이었습니다,”라고 말했습니다.

덜 균등하게 잘린 덱은 여러 번 섞어도 상대적인 순서를 유지하는 카드 집합으로 구성됩니다. 덱의 나머지 부분은 잘 혼합되어 있지만, 이러한 특정 카드 집합 — Lalley가 “cold spots”(차가운 스팟)라고 부른 것 — 은 원래 위치에 대한 정보를 여전히 간직하고 있습니다.

예를 들어, 카드를 1부터 52까지 번호 붙인다고 가정합니다. 여러 번 섞은 뒤, 카드 16과 17은 더 이상 덱 안에서 인접하지 않을 수 있지만, 16은 무작위 덱에 비해 17보다 앞에 나올 가능성이 높습니다.

원본 덱의 특정 구간(예: 카드 15~25) 내의 여러 쌍이 유사한 편향을 보인다면, 그 집합 전체가 차가운 스팟으로 형성됩니다.

Lalley는 차가운 스팟이 사라지면 덱 안 마지막 남은 질서도 사라질 것이라고 hoped를 했으며, 이를 통해 단축 현상의 존재를 보일 수 있을 거라고 생각했습니다.

하지만 그는 증명하지 못했습니다.

라벨 추적

두 십 년이 흐른 뒤에, 2019년 Lalley의 협력자 Thomas Sellke의 아들인 Mark — 당시 스탠퍼드 대학교 대학원생 — 은 Diaconis 교실에서 원래 7번 셔플 결과에 대해 배웠습니다. “그는 대충 말해왔는데, 덱을 절반으로 나누지 않으면 [증명]의 어떤 부분도 작동하지 않는다는 것을,”라고 Mark Sellke는 회상했습니다.

2021년까지, Mark Sellke는 단축 현상을 특정 지점까지 좁혔다 — Bayer와 Diaconis의 초기 연구보다 훨씬 불균등하게 잘린 덱에 대해서도 적용 가능했으며, 두 개 이상의 부분으로 나눈 덱에도 적용됐습니다. 하지만 덱은 여전히 같은 방식으로 자르는 것이 필요했습니다.

b