카지노 셔플 기계: 검정은 통과했는데 도박꾼은 두 배로 맞혔다

카드 맞히기 게임 — 4.5장과 9.3장

잘 섞은 카드 52장에서 다음 장을 맞혀 보면 평균 4.5장이 맞는다. 한 카지노 장비 회사가 새로 만든 자동 셔플 기계로 섞은 덱에서는 같은 게임의 결과가 9.3장이었다. 그 기계는 이미 엔지니어들의 무작위성 검정을 전부 통과한 뒤였다.

게임 규칙은 단순하다. 맨 위부터 한 장씩 뒤집는데, 뒤집기 전에 다음에 나올 카드를 소리 내어 부른다. 뒤집힌 카드는 매번 보여 주니, 부르는 쪽은 지금까지 나온 카드를 전부 알고 다음 장을 고른다. 그렇게 최선을 다해도 잘 섞인 덱에서 적중은 평균 4.5장이다.

52장 중 4.5장이면 10%에도 못 미친다. 잘 섞였다는 말은 아무리 잘 불러도 이만큼까지라는 뜻이다. 그런데 같은 게임을 셔플 기계로 섞은 덱에서 하면 9.3장이 맞는다. 두 배가 조금 넘는 숫자인데, 속임수가 들어간 것은 아니다. 도박꾼이 보는 것은 여전히 이미 뒤집힌 카드뿐이다.

설계 엔지니어들이 돌린 검정은 하나가 아니었다. 맨 위 카드와 맨 아래 카드가 어디로 갔는지, 원래 붙어 있던 카드들이 얼마나 흩어졌는지, 연속된 카드 묶음의 순서가 얼마나 뒤집혔는지를 각각 쟀다. 논문은 그 결과를 "만족스러워 보였다"(seemed satisfactory)고 적었다.

검정 하나하나는 합리적이다. 제대로 섞였다면 맨 위 카드가 어디로 갈지 예측할 수 없어야 하고, 붙어 있던 카드들은 흩어져야 하고, 연속된 묶음의 순서는 뒤죽박죽이어야 한다. 기계는 그 셋을 다 만족시켰다. 남은 질문은 그 셋을 통과하고도 살아남는 규칙성이 있느냐였다.

제조사가 세 명의 수학자(Persi Diaconis · Jason Fulman · Susan Holmes)에게 물은 것은 하나였다. 이 기계를 한 번만 통과시켜도 카드가 충분히 섞이는가. 그 확인 작업이 2013년 논문 한 편으로 남았다.

이 글이 따라갈 것은 4.5와 9.3 사이의 격차다. 검정을 다 통과한 기계에서 도박꾼이 두 배를 맞혔다면, 통과시킨 검정 쪽에 무슨 일이 있었다는 뜻이다. 기계가 고장 난 것도, 검정 계산이 틀린 것도 아니었다. 답은 상자 안에서 카드가 쌓이는 방식에 있다.

셔플 기계 안에서 카드가 쌓이는 방식

기계는 불투명한 상자다. 안에 선반이 열 개 있고, 위쪽으로 덱을 통째로 떨어뜨려 넣으면 안쪽 엘리베이터가 덱을 오르내리며 맨 아래 카드부터 한 장씩 뽑아 선반으로 보낸다. 어느 선반으로 갈지는 난수 발생기가 매번 균등하게 고른다. 그 선반에 이미 카드가 쌓여 있으면, 새 카드는 확률 1/2로 그 더미의 위에 놓이거나 아래에 놓인다. 다 뽑고 나면 선반마다 덱의 1/10쯤이 올라가 있고, 열 개의 더미를 무작위 순서로 다시 하나로 합친다. 여기까지가 한 번 통과다.

선반이 열 개라는 것은 덱을 한 번에 열 조각으로 나눈다는 뜻이다. 손으로 치는 리플 셔플은 덱을 둘로 갈라 겹칠 뿐이니, 열 조각으로 나누는 쪽이 한 번에 훨씬 잘게 흩어 놓을 것처럼 보인다. 이 인상이 어긋나는 지점은 조각의 개수가 아니라 조각 안쪽에 있다.

이 동작은 카드에 번호표를 붙이는 절차로 똑같이 옮겨 적을 수 있다. 논문의 Description 1이다. 선반이 m개면 번호표는 1번부터 2m번까지 쓴다 — 선반마다 위쪽 자리와 아래쪽 자리가 따로 있으니 자리 수가 2m이다. 번호 순서대로 쌓든 무작위로 합치든 결과 분포는 같다고 논문이 밝혔다. 카드마다 번호표를 무작위로 하나씩 붙인 다음, 1번 묶음을 원래 순서대로, 2번 묶음을 뒤집어서, 3번 묶음을 다시 원래 순서대로 쌓아 올린다. 짝수 번호 묶음만 뒤집는 것이 규칙의 전부다.

한쪽만 뒤집히는 이유는 기계 쪽에 있다. 어떤 선반에서 더미의 위에 놓인 카드들은 나중에 온 것일수록 더 위로 올라가고, 아래에 놓인 카드들은 나중에 온 것일수록 더 아래로 내려간다. 그래서 한 자리의 카드들은 뽑힌 순서 그대로 쌓이고, 다른 자리의 카드들은 순서가 거꾸로 쌓인다. 번호표의 홀수와 짝수가 그 두 자리다.

논문이 든 예시가 12장짜리 덱에 선반 2개다. 번호표를 논문에 적힌 그대로 넣고 돌려, 나온 순열이 논문과 같은지 본다.

# 논문 §3.1 의 12장 예시 — 카드 12장, 선반 2개(번호표 1~4)
labels = [2, 1, 1, 4, 3, 3, 1, 2, 4, 3, 4, 1]
deck = list(range(1, 13))            # 섞기 전, 위에서부터 1..12

out = []
for lab in range(1, 5):
    packet = [c for c, l in zip(deck, labels) if l == lab]
    if lab % 2 == 0:                 # 짝수 번호 묶음은 뒤집어서 쌓는다
        packet.reverse()
    out.extend(packet)

valleys = [i + 1 for i in range(1, len(out) - 1) if out[i - 1] > out[i] < out[i + 1]]

print("섞은 결과:", out)
print("논문 예시와 같은가:", out == [2, 3, 7, 12, 8, 1, 5, 6, 10, 11, 9, 4])
print("골이 있는 자리:", valleys, "/ 모두", len(valleys), "개")

섞은 결과: [2, 3, 7, 12, 8, 1, 5, 6, 10, 11, 9, 4]
논문 예시와 같은가: True
골이 있는 자리: [6] / 모두 1 개

결과가 논문에 실린 순열과 숫자 하나까지 같다. 앞으로 나올 계산은 전부 이 번호표 절차에서 나온다. 상자 안의 엘리베이터를 흉내 내지 않아도, 수학적으로 같은 이 절차만 있으면 확률을 끝까지 따라갈 수 있다는 뜻이다.

골(valley) — 이 기계가 셀 수 없는 것

섞인 덱을 보는 눈금이 하나 필요하다. 방금 출력의 마지막 줄이 이미 세어 둔 그것, 골(valley)이다. 어떤 자리의 값이 바로 앞 값보다 작고 바로 뒤 값보다도 작으면 그 자리가 골이다.

방금 돌린 12장 결과에서 골은 딱 한 군데였다. 여섯 번째 자리의 1이다 — 앞이 8이고 뒤가 5니까 양쪽보다 작다. 섞인 덱을 위에서부터 훑으며 카드 값을 꺾은선으로 그려 보면 골이 어디인지 눈에 보인다. 값이 내려가다가 다시 올라가는 지점, 그러니까 꺾은선의 골짜기 바닥이 골이다. 잘 섞인 덱은 이 선이 쉴 새 없이 오르내리니 골짜기가 많고, 덜 섞인 덱은 길게 오르거나 길게 내려가니 골짜기가 적다. 골 수는 그 오르내림이 얼마나 잦은지를 세는 눈금인 셈이다.

답부터 말한다. 잘 섞인 52장 덱은 골이 평균 16.67개인데, 10선반 기계로 한 번 섞은 덱은 8.63개다. 절반쯤이다. 더 중요한 것은 평균이 아니라 이 기계가 낼 수 있는 골 수의 상한이다. 골이 10개 이상인 덱은 아예 만들지 못한다. 드물게 나온다는 뜻이 아니라 확률이 정확히 0이다.

이유는 번호표 절차에 그대로 적혀 있다. 선반이 열 개면 묶음이 스무 개고, 홀수 묶음은 오름차순, 짝수 묶음은 내림차순이라 오름과 내림이 번갈아 붙는다. 골은 내림이 끝나고 오름이 시작되는 자리에서만 생긴다. 오름 구간 안에서는 값이 계속 커지니 골이 될 자리가 없고, 내림 구간 안에서는 계속 작아지니 역시 없다. 묶음 스무 개가 만드는 그런 경계는 아홉 군데뿐이다.

앞의 꺾은선으로 옮기면 이런 그림이다. 52장이 스무 토막으로만 오르내리고, 토막 안에서는 방향이 한 번도 바뀌지 않는다. 골짜기 자리가 아홉 개로 못 박혀 있으니 그 위로는 올라갈 방법이 없다.

그래서 분포가 좁다. 10선반 기계에서 골이 8개일 확률이 0.298, 9개일 확률이 0.667이다. 나머지 값을 다 합쳐도 0.035에 못 미치니, 사실상 8개 아니면 9개가 나온다. 반대쪽 끝에서도 같은 편향이 보인다. 골이 하나도 없는 덱, 그러니까 한 번 올라갔다가 내려오기만 하는 배열이 이 기계에서 나올 확률은 잘 섞인 경우보다 10조 배가 넘게 높다. 그림 1가 두 분포를 겹쳐 놓은 그림이다.

총변동거리로 잰 거리

검정을 몇 개 더 돌리는 대신, 저자들은 이 기계가 내놓는 순열의 확률 분포를 통째로 구했다. 그게 가능했던 이유가 방금 본 골이다. 선반 m개짜리 기계가 어떤 순열을 낼 확률은 그 순열의 골 수 하나에만 달려 있고, 카드가 어느 자리에 어떻게 놓였는지는 확률식에 들어오지 않는다. 골 수만 알면 그 순열이 나올 확률이 정해진다는 뜻이다.

분포를 손에 쥐면 "얼마나 안 섞였나"를 거리로 잴 수 있다. 총변동거리(total variation distance)는 같은 사건을 두고 두 분포가 매기는 확률이 얼마나 벌어지는지, 그 최댓값이다. 0이면 두 분포를 구별할 방법이 아예 없고, 1이면 확실하게 갈라내는 사건이 있다는 뜻이다.

52장을 10선반 기계로 한 번 섞은 분포와 균등 분포 사이의 거리는 소수 셋째 자리까지 1.000이다. 잴 수 있는 최댓값에 붙어 있다. 선반을 15개로 늘리면 0.943, 20개면 0.720, 50개라야 0.159까지 내려온다. 0.010에 닿으려면 200개가 필요하다. 그림 2에서 실제 기계가 선 자리는 곡선이 아직 천장에 붙어 있는 왼쪽 끝이다.

저자들의 판정은 짧았다. "선반 열 개로는 형편없이 부족하다. 사실 50개로도 충분하다고 하기 어렵다"(ten shelves are woefully insufficient. Indeed, 50 shelves are hardly sufficient).

카드를 다시 맞혀 보니

이 숫자를 들고 갔더니 회사 쪽이 알아듣지 못했다. 논문에 그 대목이 그대로 적혀 있다. 자문을 맡긴 엔지니어와 임원들은 총변동거리를 이해하기 어려워했다("found it hard to understand the total variation distance"). 그러고는 더 현실에 붙은 형태로 어긋남을 보여 달라고 했다.

그래서 저자들이 꺼낸 것이 맨 앞의 카드 맞히기 게임이다. 이 게임에서는 잘 섞인 덱이라도 적중이 0장은 아니다. 이미 나온 카드는 다시 나오지 않으니 뒤로 갈수록 후보가 줄고, 마지막 한 장은 반드시 맞는다. 그 앞자리는 둘 중 하나라 1/2, 그 앞은 셋 중 하나라 1/3이다. 자리마다의 적중 확률을 다 더한 값이 기댓값이다.

식 1이 잘 섞인 덱의 기준선이다. 논문은 이 값을 "약 4.5장"으로 적었고, 끝까지 더하면 4.54장이 된다. 편차도 크지 않다 — 논문은 적중 장수의 70%가 2.7장에서 6.3장 사이에 들어온다고 적었다.

이 기계로 섞은 덱에서는 부르는 방법을 바꾼다. 다음 카드가 방금 카드보다 커질지 작아질지를 골 구조가 알려 주기 때문이다.

이 전략을 선반 수마다 10,000덱씩 돌린 것이 그림 3다. 논문 값과 재현값을 나란히 적으면 이렇다. 선반이 1개면 39장(재현 38.99), 2개면 27장(27.01), 4개면 17.6장(17.61)이다. 실제 기계인 10개에서 9.3장(9.28)이다. 20개면 6.2장(6.14), 64개라야 4.7장(4.70)까지 내려온다.

논문 서론은 10선반 결과를 "약 9와 1/2장"으로 적었고, 표에 실린 값이 9.3장이다. 같은 전략을 잘 섞인 덱에 걸어 보면 4.54장이 나온다. 전략이 덱을 이기는 것이 아니라, 기계가 남긴 구조를 읽는 것이다.

검정이 놓친 이유

기계가 남긴 그 구조를 엔지니어들의 검정은 왜 못 봤을까? 그들이 무엇을 셌는지, 그리고 어디까지를 정상으로 봤는지에 답이 있다. 검정은 저마다 통계량 하나를 세고, 그 값이 정상 범위에 들면 통과로 친다.

무엇을 세느냐를 바꾸면 결과가 뒤집힌다. 엔지니어들도 맨 위 카드를 쟀지만, 어디까지를 정상으로 쳤는지는 논문에 없다. 원래 맨 위에 있던 카드가 섞은 뒤에도 맨 위에 남을 확률은, 잘 섞인 덱이면 1/52 곧 0.0192다. 10선반 기계에서는 0.0505였다. 논문이 든 하한 1/20, 곧 0.05에 거의 그대로 붙는다.

색 전환도 같은 이야기를 한다. 빨강 26장을 위에, 검정 26장을 아래에 두고 시작해서, 섞은 덱을 위에서부터 훑으며 색이 바뀌는 횟수를 센다. 잘 섞인 덱은 평균 26.04회(논문 26)에 표준편차 3.59다.

10선반 기계는 17.20회(논문 17)에 표준편차 1.81(논문 1.83)이다. 평균도 낮고 폭도 좁다. 같은 기계이고 같은 덱이다. 하강 개수로 보면 정상이고, 맨 위 카드나 색 전환으로 보면 결함이다.

두 번 돌리면 끝난다

저자들의 처방은 기계를 버리라는 것이 아니었다. 같은 기계에 한 번 더 통과시키라는 것이었다. 이 처방이 좋은 이유는 회사가 이미 가지고 있는 것만 쓴다는 데 있다. 기계도 그대로고 선반 수도 그대로다. 바뀌는 것은 덱을 한 번 더 넣었다 빼는 운용 하나뿐이라, 새로 사거나 고칠 것이 없다.

선반 셔플러를 이어 돌리면 선반 수가 곱으로 붙는다. 선반 m₁개짜리를 돌린 다음 m₂개짜리를 돌린 결과는 선반 2·m₁·m₂개짜리 한 번과 같다(Corollary 4.2). 10선반 기계를 두 번 통과시키면 2 × 10 × 10, 곧 200선반이다.

숫자가 그대로 따라온다. 200선반의 총변동거리는 0.010이다. 10선반 두 번 통과로 10,000덱을 돌려 보니 맞히기 평균이 4.56장이었고, 200선반 한 번은 4.54장, 잘 섞인 덱도 4.54장이다. 골 평균은 두 경우 모두 16.63개로 잘 섞인 덱의 16.67개에 붙는다. 논문은 총변동 기준으로 이 정도면 보통 리플 셔플 8~9회에 해당한다고 적었다.

이 감사는 기계보다 검사 쪽을 더 크게 바꿔 놓았다. 검정 목록을 늘리는 쪽으로는 답이 안 나온다. 목록이 길어져도 검정 하나하나는 여전히 자기가 세는 것만 보기 때문이다. 추천 목록의 셔플, 뽑기 확률, A/B 테스트의 무작위 배정, 코드 리뷰에 올라온 난수 생성기 — 지금까지 "검정을 통과했나"로 물어 온 자리들이다. 그 자리에서 통계량 대신 이득을 재면, 상대가 알아낸 구조를 전부 쓰게 해 놓고도 답이 장수 하나로 떨어진다. 제조사도 총변동거리 1.000에는 꿈쩍하지 않다가 그 장수를 보고 움직였다.

논문은 회사 사장의 반응을 그대로 옮겨 적었다.

더 읽기

• Persi Diaconis, Jason Fulman, Susan Holmes, "Analysis of casino shelf shuffling machines", The Annals of Applied Probability 23(4), 2013, 1692–1720 — https://arxiv.org/abs/1107.2961
• 저널판 DOI — https://doi.org/10.1214/12-AAP884
• 검정을 통과한 난수 생성기가 3차원에서는 격자에 갇혀 있던 사례: 난수를 세 개씩 묶어 찍으면 격자가 나온다