Với bộ bài 52 lá xáo kiểu bồ câu (chia đôi rồi đan hai nửa vào nhau), khoảng 7 lần là đủ để bộ bài gần như ngẫu nhiên. Kết quả này đến từ bài báo năm 1992 của Dave Bayer và Persi Diaconis, "Trailing the Dovetail Shuffle to its Lair". Trước 5 lần, bộ bài còn rất xa ngẫu nhiên; từ lần thứ 6 tới thứ 8, độ lệch rơi xuống nhanh; sau đó mỗi lần xáo thêm chỉ còn giảm độ lệch đi khoảng một nửa.
Con số 7 đến từ đâu
Bài báo của Bayer và Diaconis đăng trên tạp chí Annals of Applied Probability năm 1992, nhưng kết quả đã lan ra công chúng từ trước đó: đầu năm 1990, tờ New York Times đưa tin với tiêu đề đại ý "xáo bài, 7 là con số thắng". Tên bài báo chơi chữ với chữ dovetail, nghĩa là mộng đuôi én của thợ mộc, cũng là tên tiếng Anh của kiểu xáo đan hai nửa bài vào nhau.
Điều làm bài báo nổi tiếng không chỉ là con số 7, mà là họ đưa ra được công thức chính xác cho xác suất của từng thứ tự sau k lần xáo, với bộ bài bao nhiêu lá cũng được. Có công thức chính xác thì không cần mô phỏng, cũng không phải ước lượng thô: tính thẳng ra độ lệch so với ngẫu nhiên hoàn hảo.
Mô hình toán của một lần xáo bồ câu
Để tính được, phải mô tả lần xáo bằng toán. Mô hình được dùng có tên Gilbert–Shannon–Reeds, ghép tên Edgar Gilbert và Claude Shannon, những người đề xuất nó từ thập niên 1950, với Jim Reeds, người phát triển thêm khoảng năm 1981. Mô hình có hai bước:
- Cắt: số lá ở nửa trên tuân theo phân phối nhị thức, giống như tung 52 đồng xu và đếm số mặt sấp. Thường thì cắt gần giữa, khoảng 26 lá, nhưng lệch vài lá là bình thường.
- Thả: hai nửa được thả xen vào nhau. Nếu nửa trái còn a lá và nửa phải còn b lá, lá tiếp theo rơi từ nửa trái với xác suất a/(a + b). Nửa nào còn nhiều thì dễ rơi hơn, giống như tay cầm phần dày hơn thì nhả nhiều hơn.
Các lần ghi lại và đo cách người thật xáo bài cho thấy mô hình này khớp khá tốt với người xáo bình thường. Người xáo quá điêu luyện, thả đều một lá trái một lá phải, lại trộn kém hơn mô hình, vì xáo đều tay thì quá dễ đoán.
Chuỗi tăng: chìa khoá để đếm
Ý tưởng then chốt của bài báo là đại lượng gọi là chuỗi tăng (rising sequence). Đánh số các lá theo thứ tự ban đầu từ 1 tới 52. Sau khi xáo, bắt đầu từ lá số 1, tìm lá số 2 ở phía sau nó, rồi lá số 3 phía sau lá 2, cứ thế cho tới khi lá kế tiếp lại nằm phía trước. Đoạn vừa dò được là một chuỗi tăng. Lặp lại từ lá đứt mạch.
Ví dụ tính tay với 8 lá
Thứ tự ban đầu 1 2 3 4 5 6 7 8. Cắt thành 1 2 3 4 và 5 6 7 8, thả xen ra 5 1 2 6 3 7 4 8. Dò: 1, 2, 3, 4 đều nằm theo thứ tự, rồi 5 lại nằm trước 4, nên chuỗi thứ nhất là 1–2–3–4, chuỗi thứ hai là 5–6–7–8. Hai chuỗi tăng.
Một lần xáo bồ câu luôn cho tối đa 2 chuỗi tăng, vì mỗi nửa giữ nguyên thứ tự bên trong. Hai lần xáo cho tối đa 4. Sau k lần xáo, tối đa 2^k. Bộ bài 52 lá cần có thể đạt tới 52 chuỗi tăng (bộ bài đảo ngược hoàn toàn), nên muốn phủ hết mọi thứ tự phải có 2^k ≥ 52, tức k ≥ 6. Đây là lý do đơn giản nhất vì sao 5 lần xáo chắc chắn chưa đủ.
Bayer và Diaconis chứng minh: dưới mô hình trên, xác suất ra một thứ tự cụ thể sau k lần xáo chỉ phụ thuộc vào số chuỗi tăng r của thứ tự đó, và bằng tổ hợp chập n của (2^k + n − r), chia cho 2^kn. Thứ tự càng ít chuỗi tăng, tức càng giống thứ tự cũ, thì càng dễ xuất hiện.
Bảng độ lệch theo số lần xáo
Để đo "đã ngẫu nhiên chưa", bài báo dùng khoảng cách biến phân toàn phần: lấy tổng chênh lệch tuyệt đối giữa xác suất thật của mỗi thứ tự và xác suất lý tưởng 1/52!, rồi chia đôi. Bằng 1 nghĩa là hoàn toàn chưa trộn; bằng 0 nghĩa là ngẫu nhiên hoàn hảo. Bảng dưới đây tính lại từ đúng công thức của họ:
| Số lần xáo | Khoảng cách tới ngẫu nhiên | Đọc như thế nào |
|---|---|---|
| 1 – 4 | ≈ 1,000 | gần như chưa trộn |
| 5 | 0,924 | vẫn còn rất xa |
| 6 | 0,614 | bắt đầu rơi mạnh |
| 7 | 0,334 | qua ngưỡng một nửa |
| 8 | 0,167 | giảm một nửa so với lần 7 |
| 9 | 0,085 | tiếp tục giảm một nửa |
| 10 | 0,043 | rất gần ngẫu nhiên |
| 12 | 0,011 | khó phân biệt bằng mọi phép thử thông thường |
Hình dạng của bảng mới là điều đáng nhớ: con số đứng yên quanh 1 suốt bốn lần đầu, rồi đổ dốc trong khoảng ba lần, rồi giảm đều theo cấp số nhân. Các nhà xác suất gọi đó là hiện tượng ngưỡng (cutoff). David Aldous và Persi Diaconis đã mô tả hiện tượng này trong bài viết năm 1986 về xáo bài và thời điểm dừng. Với n lá, ngưỡng nằm quanh (3/2) × log₂ n lần xáo; thay n = 52 được khoảng 8,6. Con số 7 là điểm mà độ lệch lần đầu xuống dưới một nửa.
Sau 7 lần, bộ bài còn lệch thế nào
"Gần ngẫu nhiên" không có nghĩa là không còn dấu vết. Dùng công thức trên có thể so xác suất của vài thứ tự đặc biệt với mức lý tưởng:
- Sau 7 lần xáo, thứ tự ban đầu nguyên vẹn (chỉ 1 chuỗi tăng) có xác suất cao gấp khoảng 9 860 lần mức lý tưởng. Vẫn cực hiếm, nhưng thiên lệch rõ.
- Thứ tự đảo ngược hoàn toàn (52 chuỗi tăng) có xác suất chỉ bằng khoảng 5 phần triệu mức lý tưởng: gần như không thể xảy ra.
- Thứ tự "bình thường" với khoảng 26 chuỗi tăng có xác suất bằng khoảng 0,86 lần mức lý tưởng, nghĩa là khá sát.
- Sau 10 lần, thứ tự ban đầu chỉ còn dễ xuất hiện hơn khoảng 3,6 lần, thứ tự đảo ngược bằng khoảng một phần tư mức lý tưởng.
Ngay trong bài báo, hai tác giả kể một mẹo ảo thuật dựa đúng vào chuỗi tăng: bộ bài xáo ít lần, rút một lá ra rồi cắm lại chỗ khác, người làm có thể tìm ra lá đó vì nó phá vỡ cấu trúc chuỗi. Mẹo này cho thấy độ lệch trong bảng không chỉ là con số trên giấy.
Những tranh luận quanh con số 7
Con số 7 phụ thuộc vào ba lựa chọn, và đổi lựa chọn là đổi con số.
Thước đo
Khoảng cách biến phân toàn phần là thước đo khắt khe và phổ biến, nhưng không phải duy nhất. Với những thước đo khác, như dựa trên entropy, một số tác giả về sau tính ra rằng ít lần hơn đã đạt mức chấp nhận được. Ngược lại, có những phép thử đặc thù (như theo dõi chuỗi tăng) vẫn bắt được dấu vết sau 7 lần.
Mô hình
Kết quả đúng cho mô hình Gilbert–Shannon–Reeds. Người xáo quá đều tay, hoặc người hay cắt lệch hẳn một bên, có thể cần số lần khác. Kiểu xáo tay từng nắm (overhand) thì chậm hơn hẳn, cần hàng nghìn lần.
Mục đích
Trong một ván bài giữa bạn bè, vài thiên lệch nhỏ chẳng ảnh hưởng gì. Trong mô phỏng khoa học, hay khi bộ bài được chia theo những quy tắc dễ lộ cấu trúc, đòi hỏi cao hơn. Vì vậy nên hiểu con số 7 là mức đủ dùng cho phần lớn mục đích thực tế, không phải một ngưỡng tuyệt đối.
Góc nhìn hôm nay: tự kiểm bằng một bộ bài
Muốn thấy hiện tượng ngưỡng bằng mắt, bạn có thể làm thí nghiệm nhỏ ở nhà:
- Xếp 52 lá theo thứ tự quen thuộc: cơ Át tới K, rồi rô, chuồn, bích.
- Xáo bồ câu một lần, lật ngửa, đếm số chuỗi tăng bằng cách dò lá 1, 2, 3… Bạn sẽ thấy đúng 2 chuỗi.
- Xếp lại từ đầu, xáo 3 lần, đếm lại. Tối đa là 8, và theo mô hình thì khoảng 95% trường hợp ra đúng 8.
- Làm tiếp với 5 lần và 7 lần. Theo mô hình, sau 5 lần số chuỗi tăng trung bình khoảng 19,6, sau 7 lần khoảng 24,7, nhích dần về 26,5, mức trung bình của một bộ bài thật sự ngẫu nhiên.
Đếm 52 lá mất vài phút mỗi lần, nhưng sau thí nghiệm này bạn sẽ không bao giờ tin "xáo hai lần là đủ" nữa. Muốn đọc tiếp, cuốn Magical Mathematics (2011) của Persi Diaconis và Ron Graham có phần về xáo bài viết cho người không chuyên; còn bài báo gốc năm 1992 dành cho người quen ký hiệu xác suất.
Câu hỏi thường gặp
Xáo bài mấy lần là đủ?
Với kiểu xáo bồ câu và bộ bài 52 lá, khoảng 7 lần là đủ cho hầu hết mục đích, theo kết quả của Bayer và Diaconis năm 1992. Dưới 5 lần, bộ bài còn rất xa ngẫu nhiên. Muốn chặt chẽ hơn thì xáo 9–10 lần.
Ai chứng minh xáo bài 7 lần là đủ?
Dave Bayer và Persi Diaconis, trong bài báo "Trailing the Dovetail Shuffle to its Lair" đăng trên Annals of Applied Probability năm 1992. Họ đưa ra công thức chính xác cho xác suất mọi thứ tự sau k lần xáo bồ câu.
Xáo bài nhiều hơn 7 lần có tốt hơn không?
Có, nhưng lợi ích giảm dần: từ lần thứ 8 trở đi, mỗi lần xáo thêm chỉ làm độ lệch giảm khoảng một nửa. Từ 7 lên 10 lần, độ lệch đi từ 0,33 xuống 0,04.
Bộ bài ít lá thì cần xáo ít lần hơn không?
Có. Ngưỡng trộn tăng theo log của số lá, cỡ 1,5 × log₂ n. Bộ bài 32 lá cần ít hơn bộ 52 lá khoảng một lần, còn hai bộ bài gộp 104 lá cần nhiều hơn khoảng một tới hai lần.
Chuỗi tăng trong bộ bài là gì?
Là một đoạn các lá có số thứ tự ban đầu liên tiếp 1, 2, 3… vẫn nằm theo đúng chiều trước sau trong bộ bài đã xáo, dù có lá khác xen giữa. Mỗi lần xáo bồ câu nhân đôi số chuỗi tăng tối đa, nên đếm chuỗi tăng cho biết bộ bài đã được trộn bao nhiêu.
