‘진짜 랜덤’으로 섞는다는 것: 피셔-예이츠 셔플과 공정한 무작위

“랜덤으로 섞었다”는 말은 쉽지만, 정말 모든 순서가 같은 확률로 나오게 섞는 건 생각보다 어렵습니다. 사람 손은 물론이고, 그럴듯해 보이는 컴퓨터 코드조차 특정 결과가 더 잘 나오는 편향을 품기 쉽거든요. 이 글은 손 셔플이 왜 안 섞이는지부터, 나쁜 알고리즘의 편향 사례, 그리고 그 문제를 깔끔하게 푸는 피셔-예이츠 셔플의 원리까지 그림 그리듯 풀어봅니다.

최종 업데이트: 2026년 7월

1. 사람 손 셔플은 왜 안 섞일까

제비뽑기 쪽지를 통에 넣고 흔들거나, 카드를 몇 번 섞는 걸 떠올려 보세요. 문제는 두 가지입니다.

• 섞임이 금방 균일해지지 않습니다. 쪽지를 통에 넣고 흔들어도 먼저 넣은 쪽지는 아래쪽에 몰려 있기 쉽습니다. 카드도 마찬가지라서, 몇 번 대충 섞은 카드는 원래 순서의 흔적이 꽤 남아 있다는 게 수학적으로 알려져 있어요. 트럼프 카드 한 벌을 제대로 섞으려면 리플 셔플을 일곱 번 정도는 해야 한다는 유명한 연구도 있습니다.
• 사람의 개입 여지가 남습니다. 통을 흔든 사람, 쪽지를 접은 사람, 뽑는 순서를 정한 사람 모두가 결과에 영향을 줄 수 있는 위치에 있습니다. 실제로 영향을 안 줬더라도, 줄 수 있었다는 사실만으로 의심의 근거가 됩니다.

즉 손 셔플은 덜 섞이고, 의심을 지울 수 없습니다. 그래서 순서가 중요한 자리일수록 계산으로 섞는 쪽이 낫습니다. 그런데 계산이라고 다 공정한 건 아닙니다.

2. 그럴듯한 셔플의 함정: 편향 사례

프로그래머가 셔플을 처음 짤 때 흔히 저지르는 실수가 있습니다. 대표적인 두 가지만 볼게요.

• “정렬 함수에 랜덤 비교를 넣기”: 두 항목을 비교할 때마다 동전을 던져 앞뒤를 정하는 방식입니다. 얼핏 완벽해 보이지만, 정렬 알고리즘은 비교 결과가 일관되다고 가정하고 움직이기 때문에 결과 분포가 심하게 일그러집니다. 실제로 2010년 한 유럽 브라우저 선택 화면이 이 방식을 썼다가, 특정 브라우저가 첫 자리에 훨씬 자주 노출되는 편향이 발견되어 화제가 됐습니다.
• “모든 위치를 아무 위치와 바꾸기”: 각 항목을 전체 범위의 아무 위치와 한 번씩 맞바꾸는 방식입니다. 그럴듯하지만 경우의 수를 세어 보면 어긋납니다. 3장을 이 방식으로 섞으면 나올 수 있는 과정은 27가지인데, 가능한 순서는 6가지입니다. 27은 6으로 나누어떨어지지 않으니 어떤 순서는 반드시 다른 순서보다 자주 나옵니다. 미세해 보여도, 수백 번 반복되는 자리 배정이라면 누군가는 꾸준히 유리해지는 거죠.

3. 피셔-예이츠 셔플: 상자에서 하나씩 꺼내기

피셔-예이츠(Fisher-Yates) 셔플의 아이디어는 허무할 만큼 단순합니다. “상자에 전부 넣고, 하나씩 꺼내서 줄 세우기”를 컴퓨터로 옮긴 것뿐이에요.

1. 이름 5개가 상자에 들어 있다고 상상하세요.
2. 상자에서 무작위로 하나를 꺼내 1번 자리에 놓습니다. 5개 중 하나니까 각자 1/5 확률.
3. 남은 4개 중 하나를 꺼내 2번 자리에 놓습니다. 각자 1/4 확률.
4. 이걸 상자가 빌 때까지 반복합니다.

어떤 특정 순서가 나올 확률은 1/5 × 1/4 × 1/3 × 1/2 × 1, 즉 120가지 순서가 전부 정확히 1/120입니다. 어느 순서도 더 잘 나오거나 덜 나올 수 없다는 게 곱셈만으로 증명되죠. 실제 구현에서는 상자를 따로 두는 대신 목록 안에서 “아직 안 뽑힌 구간”과 자리를 맞바꾸는 식으로 처리하는데, 원리는 같습니다. 2번 함정과의 차이는 딱 하나입니다. 이미 자리가 정해진 항목은 다시 건드리지 않는다는 것. 그 한 끗이 편향을 없앱니다.

4. 난수의 재료: 암호학적 난수란

피셔-예이츠는 “어떻게 섞을지”의 답이고, 남은 문제는 “매번 어느 걸 꺼낼지”를 정하는 난수입니다. 컴퓨터의 흔한 난수(유사난수)는 사실 정해진 수식이 만들어내는 수열이라서, 시작값을 알면 다음 수를 전부 예측할 수 있습니다. 게임 효과음 정도엔 충분하지만, 이해관계가 걸린 순서 정하기엔 찜찜하죠.

그래서 등급이 다른 난수가 있습니다. 암호학적 난수는 비밀번호나 보안 키를 만들 때 쓰는 수준의 난수로, 지금까지의 출력을 다 지켜봐도 다음 값을 예측할 수 없도록 설계되어 있습니다. 요즘 브라우저에는 이 난수 생성기(crypto)가 기본으로 내장되어 있어서, 웹 도구도 이 수준의 무작위를 쓸 수 있습니다.

정리하면 공정한 섞기의 공식은 이렇습니다. 편향 없는 알고리즘(피셔-예이츠) + 예측 불가능한 재료(암호학적 난수). 둘 중 하나라도 빠지면 어딘가에 구멍이 생깁니다.

5. 이 도구의 공정성 장치

순서 정하기 도구는 위 공식을 그대로 따르고, 여기에 사람 쪽 구멍을 막는 장치를 더했습니다.

• 피셔-예이츠 셔플 + 암호학적 난수로 섞습니다. 모든 순열이 같은 확률이라서 “먼저 적은 사람이 앞 순서가 잘 나온다” 같은 편향이 구조적으로 생길 수 없습니다.
• 다시 섞은 횟수가 화면에 표시됩니다. 알고리즘이 완벽해도 마음에 드는 결과가 나올 때까지 몰래 다시 돌리면 소용없죠. 횟수가 드러나면 그 여지가 사라집니다.
• 재현 링크를 공유하면 누구나 같은 순서를 다시 확인할 수 있습니다. 발표 후에 결과를 바꿀 수 없다는 증빙이 됩니다.
• 명단은 서버로 전송되지 않습니다. 섞기는 전부 여러분의 브라우저 안에서만 계산됩니다.

6. 자주 묻는 질문

같은 사람이 두 번 연속 1번이 나왔는데, 고장 아닌가요?

아니요, 오히려 자연스러운 일입니다. 10명 기준으로 같은 사람이 두 번 연속 1번일 확률은 1/100인데, 섞기를 반복하다 보면 이런 일은 꼭 일어납니다. 진짜 무작위는 우리 직감보다 훨씬 자주 우연의 일치를 만들어냅니다. 매번 골고루 돌아가는 결과가 나온다면 그게 오히려 무작위가 아니라는 신호예요.

재현 링크가 있으면 결과를 미리 알 수 있는 것 아닌가요?

재현 링크는 섞기가 끝난 뒤에 만들어지는, 이미 나온 결과를 다시 보여주는 링크입니다. 다음 섞기의 결과를 예측하는 데 쓸 수 있는 정보는 담겨 있지 않습니다.

제비뽑기나 사다리타기보다 나은 점이 뭔가요?

결과의 무작위성 자체는 잘 만든 제비뽑기도 확보할 수 있습니다. 차이는 균일함의 보장과 증빙입니다. 손으로 만든 제비는 접힌 모양·위치 편향을 배제하기 어렵고, 과정을 다시 보여줄 수 없죠. 참고로 사다리타기는 또 다른 재미가 있는 방식인데, 그 구조가 궁금하다면 사다리타기 원리와 확률 글을 읽어 보세요.

암호학적 난수면 로또 번호도 잘 맞을까요?

그건 별개 문제입니다. 암호학적 난수는 “예측 불가능함”을 보장할 뿐, 당첨 확률을 높여주지는 않습니다. 어떤 방법으로 뽑아도 로또의 기대값은 같아요. 다만 남들이 안 고를 법한 조합을 고른다는 재미는 있죠.