Khi giáo viên gọi một học sinh trả lời, khi nhóm chọn người thuyết trình trước, hay khi cửa hàng chọn người trúng quà, những người liên quan chỉ quan tâm một điều: mọi người có cơ hội như nhau không? "Ngẫu nhiên mà" chưa hẳn là câu trả lời. Một công cụ bốc thăm có thể thiên vị theo những cách nhỏ, vô hình, và một lần bốc thăm có thể công bằng mà trông vẫn như gian lận. Bài này giải thích một công cụ công bằng chọn như thế nào, đi qua lỗi kinh điển bằng số liệu thật, và kết thúc bằng quy trình cho những lần bốc thăm mà người khác cần tin tưởng.
Phương pháp được mô tả là cách công cụ bốc thăm tên ngẫu nhiên của chúng tôi dùng, và các con số được tính tay rồi kiểm tra lại bằng script.
Bước một: một nguồn ngẫu nhiên tốt
Trình duyệt có hai nguồn ngẫu nhiên. Math.random() nhanh và đủ dùng cho hiệu ứng và trò chơi, nhưng nó không được thiết kế để không thể đoán trước: về nguyên tắc, trạng thái bên trong của nó có thể được suy ra từ đủ nhiều kết quả. crypto.getRandomValues() lấy từ bộ sinh số mật mã của hệ điều hành, cùng nguồn dùng để tạo khoá mã hoá. Với bất cứ thứ gì có giải thưởng hay hệ quả, hãy dùng nguồn thứ hai. Công cụ của chúng tôi dùng nguồn này, và không có gì trong lần bốc thăm rời khỏi trình duyệt của bạn.
Bước hai: biến các bit ngẫu nhiên thành một cái tên
Bộ sinh số an toàn cho bạn một số 32 bit, từ 0 tới 4.294.967.295. Giả sử bạn có 30 cái tên. Cách hiển nhiên là lấy số dư: x % 30. Đó chính là lỗi kinh điển, gọi là độ lệch modulo (modulo bias).
Dễ thấy nhất với một nguồn nhỏ. Giả sử bạn chỉ có một byte ngẫu nhiên, từ 0 tới 255, và muốn một chữ số từ 0 tới 9. 256 chia 10 được 25 dư 6. Vậy các giá trị từ 0 tới 249 phủ mỗi chữ số đúng 25 lần, còn sáu giá trị dư, từ 250 tới 255, rơi thêm một lần nữa vào các chữ số 0 tới 5:
| Chữ số | Số giá trị byte cho ra nó | Xác suất |
|---|---|---|
| 0 tới 5 | mỗi số 26 | 26 ÷ 256 ≈ 10,16% |
| 6 tới 9 | mỗi số 25 | 25 ÷ 256 ≈ 9,77% |
Các chữ số nhỏ thắng thường xuyên hơn các chữ số lớn khoảng 4%. Trong một lần bốc thăm ở lớp với nguồn ngẫu nhiên cỡ một byte, sáu cái tên đầu danh sách sẽ có lợi thế đo được.
Với 32 bit, hiệu ứng nhỏ đi nhưng không biến mất. 2³² chia 30 dư 16, nên với x % 30 thì 16 tên đầu mỗi tên có 143.165.577 khả năng, 14 tên còn lại mỗi tên có 143.165.576. Không ai nhận ra chênh lệch một phần 143 triệu, nhưng nó không bằng nhau, và cách sửa chẳng tốn gì.
Cách sửa: lấy mẫu loại bỏ
Bỏ đi các giá trị dư và rút lại. Với 30 tên, chỉ chấp nhận x khi nó nhỏ hơn 4.294.967.280 (bội số lớn nhất của 30 còn vừa), rồi lấy x % 30. Khi đó mỗi tên có đúng 143.165.576 giá trị được chấp nhận. Xác suất phải rút lại là 16 trên 4,3 tỉ, nên trên thực tế gần như không bao giờ xảy ra. Công cụ của chúng tôi làm đúng như vậy, và công cụ tung xúc xắc và đồng xu cũng dùng kỹ thuật này cho xúc xắc.
Cách thay thế phổ biến, Math.floor(Math.random() * n), có độ lệch cùng loại nhưng nhỏ hơn nhiều vì Math.random() có nhiều bit hơn, song nó vẫn dùng nguồn không phải mật mã.
Vòng quay chỉ để trang trí
Vòng quay khiến người ta thấy công bằng hơn một cái tên hiện ra tức thì, vì vậy các công cụ bốc thăm đều có. Trong một công cụ làm đúng, vòng quay không quyết định gì cả. Công cụ của chúng tôi chọn người thắng trước, từ nguồn an toàn, rồi mới tính vòng quay phải dừng ở đâu để lát của người thắng nằm dưới kim chỉ, ở một vị trí ngẫu nhiên trong lát, sau vài vòng quay trọn. Hiệu ứng được tính từ kết quả, không bao giờ theo chiều ngược lại.
Điều đó quan trọng vì một vòng quay để vật lý quyết định kết quả thì chỉ công bằng bằng chính phần vật lý đó: ma sát, tốc độ khung hình và thời gian giữ nút đều có thể làm lệch điểm dừng.
Tên trùng, loại người thắng và nhiều giải
- Tên xuất hiện hai lần có gấp đôi cơ hội. Nếu danh sách được dán từ biểu mẫu đăng ký, ai đăng ký hai lần sẽ có hai lát. Hãy bật "bỏ qua tên trùng nhau", trừ khi nhiều lượt là quy định (ví dụ mỗi vé mua được một lượt).
- Bốc nhiều giải: loại từng người thắng. Với 30 tên và 3 giải, loại người thắng sau mỗi lượt quay cho mỗi người đúng 3 trên 30, tức 10% cơ hội trúng một giải. Nếu giữ lại người thắng, có khoảng 9,8% khả năng cùng một người được chọn hai lần trong ba lượt (1 − 30 × 29 × 28 ÷ 30³), và bạn phải quyết định bốc lại nghĩa là gì.
- Thứ tự trong danh sách không quan trọng khi việc chọn là đồng đều. Không ai được lợi vì đứng đầu hay đứng cuối.
Công bằng khác với trông có vẻ công bằng
Kết quả ngẫu nhiên thật sự có những chuỗi lặp. Một học sinh bị gọi hai buổi liền không phải bằng chứng công cụ hỏng: với 30 học sinh, xác suất cùng một em bị gọi ở hai buổi liên tiếp là 1 trên 30 mỗi lần, nên trong cả học kỳ rất có thể điều đó xảy ra với ai đó. Nếu mục tiêu là ai cũng tới lượt, đó là xoay vòng chứ không phải bốc thăm, và tuỳ chọn "xóa người thắng sau mỗi lượt quay" biến công cụ thành đúng như vậy.
Với bốc thăm công khai, quy trình mới là thứ người ta tin:
- Công bố toàn bộ danh sách trước khi bốc.
- Nói rõ luật từ trước: mỗi người một lượt, bao nhiêu giải, điều gì xảy ra nếu người thắng không phản hồi.
- Bốc trực tiếp hoặc quay màn hình, với danh sách hiện rõ.
- Lưu lại danh sách và kết quả.
Những lỗi thường gặp
- Dùng
x % ntrên một số ngẫu nhiên nhỏ. - Dùng
Math.random()cho lần bốc thăm có giải thưởng thật. - Để nguyên tên trùng trong danh sách lẽ ra mỗi người một lượt.
- Quay lại cho tới khi kết quả "trông có vẻ ngẫu nhiên", tức là đang chọn chứ không phải bốc thăm.
- Bốc nhiều giải mà không loại người thắng, rồi xoay xở khi cùng một cái tên hiện ra hai lần.
Hãy dán danh sách vào công cụ bốc thăm tên ngẫu nhiên, quyết định thiết lập về tên trùng và loại người thắng trước khi quay, và để vòng quay lo phần trình diễn. Lựa chọn thực sự đã được đưa ra, một cách công bằng, trước khi vòng quay bắt đầu. Về xác suất của xúc xắc, đồng xu và lượt tung có lợi thế, xem bài xác suất xúc xắc 2d6 và lợi thế.