카드 일곱 번 섞으면 충분하다? 그럼 '대충' 섞으면 몇 번인데

'카드 일곱 번이면 충분하다'의 뒷이야기

카드를 몇 번 섞어야 진짜로 무작위가 될까요? 수학자 퍼시 다이아코니스가 1992년에 내놓은 유명한 답이 '리플 셔플(카드를 반으로 나눠 좌르륵 깍지 끼우는 그 방식이에요) 일곱 번'이에요. 그런데 이건 '사람이 거의 완벽하게 섞는다'는 이상적인 모델 위에서 나온 숫자였거든요. 이번 Quanta 기사는 한 발 더 나가서 '그럼 엉성하게(sloppy) 섞으면 도대체 몇 번이 필요하냐'는, 훨씬 현실적인 질문을 다뤄요.

일곱 번의 비밀 — 컷오프 현상

핵심 개념부터 풀게요. 섞기를 수학적으로 보면, '아직 덜 섞인 상태'에서 '완전 무작위 상태'까지의 거리를 잴 수 있어요(총변동거리라는 척도를 써요). 재미있는 건 이 거리가 슬금슬금 줄어드는 게 아니라는 거예요. 6번까지는 '아직 패턴이 남아 있음' 상태로 버티다가, 7번째에 갑자기 뚝 떨어져서 '거의 무작위'가 돼요. 이걸 컷오프(cutoff) 현상이라고 불러요. 물이 99도까지는 멀쩡하다가 100도에서 확 끓는 것처럼, 무작위성도 어느 순간 확 완성되는 거죠.

그럼 엉성한 셔플은?

완벽한 리플 셔플은 양쪽 카드가 거의 한 장씩 번갈아 떨어지는 거예요. 그런데 현실에선 뭉텅이로 우르르 떨어지잖아요. 이렇게 한쪽으로 치우친 셔플을 모델링하면, 한 번 섞을 때 만들어지는 무작위성이 줄어들어서 결국 더 많은 횟수가 필요해져요. 연구자들은 이 '엉성함의 정도'에 따라 필요한 셔플 횟수가 어떻게 늘어나는지를 정밀하게 따져본 거예요.

개발자에게 — 셔플 알고리즘 이야기

이게 남 일이 아니에요. 코드에서 배열 섞을 때 직접 짠 셔플은 의외로 편향되기 쉽거든요. 정답은 Fisher-Yates(피셔-예이츠) 셔플이에요. 끝에서부터 i번째 원소를 0부터 i까지 중 무작위 위치와 맞바꾸는 방식인데, 이걸 살짝만 잘못 짜서(예를 들어 범위를 0~i가 아니라 0~n-1로 잡으면) 특정 순열이 더 자주 튀어나오는 편향이 생겨요. 말하자면 '엉성한 셔플'의 코드 버전인 셈이죠. 게다가 카드 게임 서버라면 난수 생성기(RNG)의 품질 자체가 보안 이슈가 돼요. 예측 가능한 난수면 카드를 읽힐 수 있으니까요.