추첨과 순서 정하기가 공정하려면

공정한 추첨에는 재료와 손질이 모두 필요해요

발표 순서나 청소 당번을 정할 때 "컴퓨터가 정했으니 공정하다"는 말을 자주 들어요. 그런데 컴퓨터가 정했다는 사실만으로는 부족해요. 공정한 추첨이 되려면 두 단계가 모두 맞아야 하거든요. 첫째는 재료예요. 예측할 수 없는 숫자, 곧 난수를 어디서 가져오느냐의 문제예요. 둘째는 손질이에요. 받아 온 숫자를 '1부터 6 중 하나'나 '다섯 사람의 줄 세우기'처럼 쓸 수 있는 모양으로 바꾸는 과정이에요.

재료가 좋아도 손질이 서투르면 결과가 한쪽으로 기울어요. 반대로 손질이 정확해도 재료가 뻔하면 다음 결과를 짐작할 수 있게 돼요. 이 글에서는 두 단계를 차례로 살펴보고, 이 사이트의 순서 정하기, 주사위 굴리기, 제비뽑기가 각각 어떻게 처리하는지 코드를 읽고 확인한 내용으로 정리했어요. 표에 나오는 숫자는 직접 계산하거나 사이트 코드를 그대로 돌려 본 결과예요.

난수는 어디서 오나: 브라우저의 crypto

세 도구는 모두 사이트 공통 코드의 정수 뽑기 함수 하나를 거쳐요. 이 함수는 브라우저에 들어 있는 crypto.getRandomValues로 32비트 부호 없는 정수 하나를 받아 와요. 0부터 4,294,967,295까지 가운데 하나가 나오는 셈이에요.

W3C의 Web Cryptography 규격은 이 기능을 '암호학적으로 강한 난수'를 만드는 방법으로 정의해요. 구현 방식도 권하고 있어요. 운영체제의 엔트로피처럼 질 좋은 무작위 값으로 시드를 넣은, 검증된 암호용 의사난수 생성기를 쓰라는 거예요. 다만 규격은 엔트로피의 최소량을 따로 정하지 않고, 가능한 한 많이 확보하라고만 적어 두었어요. 한 번에 요청할 수 있는 양에도 한도가 있어서, 65,536바이트를 넘게 달라고 하면 오류를 내도록 정해져 있어요. 추첨 한 번에 4바이트씩 받는 이 사이트에는 걸릴 일이 없는 한도예요.

MDN 문서는 두 가지를 더 짚어 줘요. 하나는 이 함수가 Crypto 기능 가운데 유일하게 보안 연결이 아닌 페이지에서도 쓸 수 있다는 점이에요. 다른 하나는 흔히 쓰는 Math.random이 암호용이 아닌 난수 원천이라는 점이에요. 이 사이트의 추첨 코드는 Math.random을 쓰지 않아요.

나머지 연산(%)이 만드는 작은 쏠림

재료를 받았으면 이제 손질할 차례예요. 큰 수를 1~6 같은 작은 범위로 줄이는 가장 쉬운 방법은 6으로 나눈 나머지를 쓰는 거예요. 문제는 전체 경우의 수가 6으로 딱 나누어떨어지지 않을 때 생겨요. 0부터 255까지 나오는 1바이트 값으로 예를 들어 볼게요. 256을 6으로 나누면 몫이 42이고 4가 남아요. 그래서 나머지 0~3은 43번씩, 4와 5는 42번씩 나와요.

1~4의 눈이 5와 6보다 조금씩 자주 나오는 주사위가 되는 거예요. 32비트 값을 쓰면 쏠림은 훨씬 작아지지만 없어지지는 않아요. 4,294,967,296을 6으로 나누면 4가 남고, 1,000으로 나누면 296이 남아요. 1,000면 주사위라면 앞쪽 296개 눈이 나머지보다 2의 32제곱 분의 1만큼 더 자주 나오는 셈이에요.

이 사이트는 이 쏠림을 버리고 다시 뽑기로 없애요. 면 수로 나누어떨어지는 가장 큰 경계를 먼저 구하고, 받아 온 값이 그 경계 이상이면 버린 뒤 새로 받아요. 경계 아래의 값만 쓰기 때문에 모든 나머지가 정확히 같은 횟수로 나와요. 다시 뽑는 일이 얼마나 자주 생기는지도 계산해 봤어요.

버리는 일이 워낙 드물어서 사람이 느낄 만한 지연은 없어요. 그래도 그 드문 경우를 그냥 넘기지 않는 것, 그게 '거의 공평'과 '공평'의 차이예요.

섞는 방법이 틀리면 생기는 편향

순서를 정할 때는 숫자 하나가 아니라 목록 전체를 섞어야 해요. 여기서 흔한 실수가 두 가지 있어요. 하나는 '각 자리를 돌면서 전체 중 아무 자리와 바꾸기'예요. 세 명이면 자리마다 3가지 선택이 있어서 경우가 3×3×3 = 27가지인데, 가능한 줄은 6가지예요. 27은 6으로 나누어떨어지지 않으니 어떤 줄은 4번, 어떤 줄은 5번 나올 수밖에 없어요. 27가지를 전부 따져 본 결과와, 사이트의 난수 함수로 60만 번씩 돌려 본 결과를 함께 적었어요.

틀린 방법은 이론대로 약 8만 9천과 11만 1천 두 무리로 갈렸고, 사이트의 방법은 모든 줄이 10만 근처에 모였어요. 네 명으로 늘려 256가지를 모두 따져 보면 더 눈에 띄어요. 두 번째로 적은 사람이 맨 앞에 설 확률이 29.3%로, 공평한 값인 25%보다 높고 네 번째로 적은 사람은 21.1%에 그쳐요.

또 하나의 실수는 정렬 함수에 '무작위로 크다 작다를 답하는 비교'를 넣는 방법이에요. 결과가 정렬 알고리즘의 내부 사정에 끌려가요. Node.js(V8)에서 세 명으로 60만 번 돌린 시뮬레이션에서는 원래 순서 그대로가 22만 5천 번 넘게 나왔고, 어떤 줄은 3만 7천 번대에 머물렀어요. 이 숫자는 실행 환경마다 달라질 수 있지만, 고르지 않다는 점은 변하지 않아요.

이 사이트가 쓰는 방법은 피셔–예이츠 방식이라고 부르는 섞기예요. 목록의 맨 끝 자리부터 앞으로 오면서, 아직 정해지지 않은 앞쪽 자리 중 하나를 골라 바꿔요. 다섯 명이면 5, 4, 3, 2가지 중에서 차례로 고르니 경우가 5×4×3×2 = 120가지가 되고, 이는 가능한 줄의 수와 정확히 같아요. 경우 하나가 줄 하나에 대응하니 쏠릴 틈이 없어요.

세 도구가 난수를 쓰는 방식

공통 함수 위에서 세 도구는 각자 다른 방식으로 결과를 만들어요. 코드에서 확인한 내용을 표로 묶었어요.

제비뽑기는 겉보기에 복잡해서 정말 모두에게 공평한지 궁금할 수 있어요. 코드를 보면 한 판에서 필요한 만큼만 대결하고, 짝이 없는 사람은 부전승으로 다음 판에 올라가요. 비기면 그 짝만 다시 내는데, 50번 연속으로 비기면 마지막에는 둘 중 하나를 난수로 고르는 안전장치가 있어요. 그 확률은 3의 50제곱 분의 1이라 현실에서는 일어나지 않는다고 봐도 돼요.

사이트의 뽑기 함수를 그대로 반복해 돌려 본 결과는 이래요(시뮬레이션). 다섯 명 중 한 명을 30만 번 뽑았더니 각자 19.89~20.13%로 모두 20% 근처였고, 매번 세 판 만에 끝났어요. 열두 명 중 한 명을 12만 번 뽑을 때는 각자 8.27~8.41%로 이론값 8.33%에 모였고 언제나 네 판이 걸렸어요. 일곱 명 중 두 명을 20만 번 뽑았을 때는 각자 28.36~28.74%로, 7분의 2인 28.57% 주변이었어요. 대결 한 번이 첫 손에 끝난 비율은 66.7%로, 세 번 중 한 번은 비긴다는 가위바위보의 성질과 맞았어요.

결과를 모두가 믿게 진행하는 순서

난수와 섞기가 정확해도, 진행 방식이 허술하면 "다시 해"라는 말이 나오기 쉬워요. 아래 순서로 하면 결과를 두고 다툴 일이 줄어요.

1. 명단을 먼저 보여 주기. 이름을 입력한 화면을 모두에게 보여 주고 빠진 사람이나 같은 이름이 두 번 들어간 줄이 없는지 확인해요. 동명이인은 이름 뒤에 표시를 붙여요.
2. 몇 번 누를지 미리 정하기. '첫 결과를 그대로 따른다'처럼 다시 뽑는 조건을 시작 전에 합의해요. 결과를 본 뒤에 규칙을 바꾸면 어떤 난수도 공정함을 지켜 주지 못해요.
3. 누르는 장면을 함께 보기. 모인 자리라면 화면을 띄우고, 온라인이라면 화면 공유로 버튼을 누르는 순간을 보여 줘요.
4. 결과를 곧바로 기록하기. 복사 버튼으로 결과를 단체 대화방에 붙여 넣어요. 세 도구 모두 결과를 서버에 남기지 않으니 기록은 참가자 쪽에서 해 둬야 해요.
5. 제비뽑기는 회차를 이어서 쓰기. 여러 명을 차례로 뽑을 때는 '처음부터'를 누르지 말고 다음 회차로 이어 가야 이미 뽑힌 사람이 다시 나오지 않아요.

팁 이 글에서 확인한 것은 '결과가 한쪽으로 기울지 않는다'는 점이에요. 누가 결과를 미리 알 수 없다는 것까지 보장하려면 진행 과정도 공개돼야 해요. 상품이나 돈이 걸린 정식 추첨이라면 이런 웹 도구보다 참가자 모두가 지켜보는 공식 절차를 따르는 편이 맞아요.