공정한 셔플의 수학

셔플은 정확한 수학적 질문을 제기합니다: n개의 서로 다른 객체가 주어졌을 때, n!가지 가능한 순서 중 하나를 동일한 확률로 생성하는 것입니다. 10개의 정수의 경우, 이는 3,628,800가지 순열을 의미합니다. 위의 순서는 Fisher-Yates 알고리즘과 Web Cryptography API를 사용하여 브라우저 내에서 균등 확률로 해당 공간에서 선택되었습니다.

Fisher-Yates: 결정적 알고리즘

Ronald Fisher와 Frank Yates는 1938년 저서 Statistical Tables for Biological, Agricultural and Medical Research에서 원래의 셔플 방법을 기술했습니다. Donald Knuth는 이후 The Art of Computer Programming(1969)에서 컴퓨터 구현을 위해 이를 개선했습니다. 현대 버전은 배열을 역순으로 순회합니다. 각 위치에서 아직 섞이지 않은 나머지 부분에서 임의의 요소를 선택하여 교환합니다. 데이터를 한 번 통과하면 O(n) 시간과 O(1) 추가 공간으로 완벽한 균등 셔플이 생성됩니다.

정확성 증명은 위치 k를 처리한 후, 처음 k개 요소의 k!가지 가능한 부분 배열 각각이 동일한 확률을 가진다는 것을 보여줍니다. 귀납법에 의해 최종 결과는 모든 n!가지 순열을 균등 확률로 포함합니다. 흔한 구현 오류인 "나이브 셔플"은 처리되지 않은 부분이 아닌 전체 배열에서 선택합니다. 이는 nⁿ개의 교환 시퀀스를 n!개의 순열에 매핑합니다. nⁿ은 일반적으로 n!으로 나누어지지 않으므로, 일부 순열이 다른 것보다 더 자주 나타나게 됩니다. Fisher-Yates 알고리즘은 이 문제를 완전히 방지합니다.

순열의 놀라운 규모

팩토리얼 증가는 다른 모든 일반적인 수학 함수를 능가합니다. 10개의 항목은 3,628,800가지 배열을 만들어냅니다. 20개의 항목은 2.4경 이상의 배열을 생성합니다. 표준 52장 카드 한 벌은 약 8.07 \xC3\x97 10\xE2\x81\xB6\xE2\x81\xB7가지 가능한 순서를 생성합니다. 이 숫자는 관측 가능한 우주의 추정 원자 수를 초과합니다.

생각해 보세요: 우주의 모든 원자가 나노초마다 한 번씩 카드를 섞고, 138억 년 전 빅뱅 이후로 계속 그렇게 해왔다면, 수행된 총 셔플 횟수는 여전히 52!의 극히 미미한 비율에 불과합니다. 이 페이지에서 수행하는 모든 셔플은 거의 확실하게 이전에 존재한 적 없고 다시는 존재하지 않을 배열을 만들어냅니다.

고정점: 완전순열의 역설

고정점은 셔플 후 원래 위치에 남아있는 숫자입니다. 위의 금색 테두리 원을 주목하세요: 그것이 바로 고정점입니다. 고정점의 기대값은 항목 수에 관계없이 정확히 1입니다. 10개의 항목이든, 만 개의 항목이든 기대되는 고정점은 여전히 1입니다.

특정 요소가 고정될 확률은 1/n입니다. n개의 요소에 대해 합산하면 기대값은 1이 됩니다. Leonhard Euler가 연구한 완전순열의 수학적 개념과 관련된 이 결과는, 모든 셔플의 약 36.8%가 고정점이 0개이고, 36.8%가 정확히 1개, 18.4%가 정확히 2개이며, 그 이상에서는 확률이 급격히 감소함을 의미합니다.

7회 셔플 정리

Persi Diaconis와 Dave Bayer는 1992년에 52장 카드 한 벌의 표준 리플 셔플이 적절한 무작위화에 도달하려면 정확히 7회의 반복이 필요함을 증명했습니다. 디지털 Fisher-Yates 셔플은 7회의 물리적 리플 셔플이 근사하는 것, 즉 완벽한 균등 무작위화를 한 번의 계산 과정으로 달성합니다.

교실에서

각 학생에게 /sequence/1/10에 접속하여 한 번 섞도록 하세요. 그런 다음 물어보세요: 같은 순서를 얻은 학생이 두 명 이상 있나요? 3,628,800가지 가능한 배열이 있으므로, 일치할 가능성은 극히 낮습니다. 프로젝터 시연의 경우 /sequence/1/52를 열고 반복해서 섞으세요. 선명한 고리가 매번 새로운 패턴으로 흩어지며 무작위성을 즉시 시각적으로 보여줍니다. 이 도구는 계정이 필요 없고, 쿠키를 설정하지 않으며, 학생 데이터를 저장하지 않습니다.