Độ ngẫu nhiên và công bằng

Biên soạn: Chia Nhóm · Cập nhật:

Trang này giải thích chính xác cách các công cụ ngẫu nhiên của Chia Nhóm (chia nhóm, ghép cặp, xáo trộn, chọn tên) tạo ra kết quả, những gì được đảm bảo, những gì không, và cho bạn tự chạy kiểm tra ngay trong trình duyệt bằng đúng đoạn mã mà công cụ đang dùng.

Tóm tắt

  • Số ngẫu nhiên lấy từ crypto.getRandomValues của trình duyệt, là bộ sinh số ngẫu nhiên an toàn về mật mã do hệ điều hành cung cấp.
  • Thứ tự được xáo bằng thuật toán Fisher–Yates: mọi cách sắp xếp có xác suất xuất hiện bằng nhau.
  • Chia nhóm là cắt tuần tự danh sách đã xáo, sĩ số các nhóm chênh nhau tối đa 1 người.
  • Toàn bộ chạy trên máy bạn. Không có máy chủ nào biết danh sách hay kết quả.
  • Công cụ không lưu “hạt giống” (seed), nên một lần chia không thể tái lập để kiểm toán về sau. Không dùng cho xổ số, trúng thưởng có giá trị lớn hay quyết định pháp lý.

Bước 1: số ngẫu nhiên đến từ đâu

Mọi lựa chọn ngẫu nhiên đều đi qua một hàm duy nhất: sinh số nguyên trong khoảng [0, n). Hàm này gọi crypto.getRandomValues để lấy một số 32 bit từ bộ sinh của hệ điều hành, rồi dùng kỹ thuật lấy mẫu loại bỏ (rejection sampling): nếu số rơi vào phần dư không chia hết cho n thì bỏ và lấy lại. Nhờ vậy không có giá trị nào bị thiên lệch vì phép chia lấy dư (modulo bias), một lỗi rất phổ biến ở các công cụ viết vội.

Chỉ khi trình duyệt quá cũ không có API này, công cụ mới lùi về Math.random. Trình duyệt bạn đang dùng: đang kiểm tra…

Bước 2: xáo trộn bằng Fisher–Yates

Danh sách được duyệt từ cuối lên; ở mỗi vị trí i, phần tử hiện tại đổi chỗ với một phần tử ngẫu nhiên trong đoạn 0…i. Đây là thuật toán Fisher–Yates (bản Durstenfeld), cho mọi hoán vị xác suất đúng bằng 1/n!. Công cụ không dùng cách “sắp xếp theo Math.random() − 0,5”, vốn tạo ra phân phối lệch.

Bước 3: từ danh sách đã xáo thành nhóm, cặp hay tên được chọn

  • Chia nhóm: tính sĩ số từng nhóm trước (chênh nhau tối đa 1), rồi rải danh sách đã xáo vào các nhóm theo vòng tròn, bắt đầu từ một nhóm ngẫu nhiên. Nhờ điểm bắt đầu ngẫu nhiên, nhóm 1 không được ưu tiên nhận người dư.
  • Chia đều theo nhãn (ví dụ Lan|Nữ): xáo riêng từng nhóm nhãn, rải nhóm nhãn đông nhất trước, nhóm ít hơn lấp vào các chỗ còn lại. Mỗi nhãn được chia đều nhất có thể; kết quả vẫn ngẫu nhiên trong phạm vi nhãn đó.
  • Ràng buộc cùng nhóm / khác nhóm (mục Ràng buộc nâng cao): công cụ tạo nhiều phương án ngẫu nhiên rồi giữ phương án vi phạm ít nhất. Khi có ràng buộc, phân phối không còn hoàn toàn đều giữa mọi cách chia, đây là đánh đổi có chủ ý để tôn trọng yêu cầu của bạn, và công cụ báo rõ nếu không thoả được hết.
  • Ghép cặp: xáo rồi cắt từng 2 người; lẻ thì người cuối vào nhóm 3. Tuỳ chọn “tránh lặp cặp” chỉ ưu tiên phương án ít cặp trùng, không đảm bảo tuyệt đối khi lịch sử đã dày.
  • Chọn tên: xáo rồi lấy k tên đầu; người đã trúng được loại khỏi lượt sau nếu bạn bật tuỳ chọn đó.
  • Chế độ Lần lượt và hiệu ứng: kết quả được tính xong trước khi hoạt hình bắt đầu. Thuyền, khinh khí cầu, đèn lồng chỉ trình bày lại kết quả, không tham gia tạo ra nó.

Những gì công cụ không đảm bảo

  • Không tái lập được: vì không lưu seed, bạn không thể chạy lại để chứng minh với người khác rằng kết quả hôm qua “đúng là ngẫu nhiên”. Nếu cần bằng chứng, hãy chia trực tiếp trước mặt mọi người bằng chế độ Trình chiếu.
  • Phụ thuộc trình duyệt: chất lượng số ngẫu nhiên là của hệ điều hành và trình duyệt. Chia Nhóm không kiểm soát được thiết bị của bạn.
  • Không dành cho xổ số, trúng thưởng giá trị lớn, quyết định pháp lý: những việc đó cần quy trình được kiểm chứng độc lập và có nhật ký.
  • Ràng buộc và tránh lặp cặp là “tốt nhất có thể”, không phải bảo đảm tuyệt đối.

Tự kiểm chứng ngay tại đây

Bản demo dưới đây nhập đúng hai hàm shuffle và splitIntoGroups mà công cụ đang chạy, xáo danh sách 6 tên nhiều lần rồi đếm: mỗi tên đứng đầu bao nhiêu lần, và rơi vào Nhóm 1 bao nhiêu lần khi chia 2 nhóm. Với bộ sinh tốt, mỗi tên đứng đầu khoảng 16,67 % và vào Nhóm 1 khoảng 50 %. Toàn bộ chạy trên máy bạn.

Nguồn ngẫu nhiên trên trình duyệt này: …

Một lần chạy có χ² vượt ngưỡng không có nghĩa là lỗi: theo định nghĩa của ngưỡng 95 %, điều đó xảy ra ở khoảng 1 trong 20 lần chạy với cả bộ sinh hoàn hảo. Điều đáng ngờ là khi một tên luôn lệch cùng một hướng qua nhiều lần chạy.

Cách chúng tôi kiểm thử

  • Bộ kiểm thử tự động chạy trước mỗi lần phát hành, gồm: số ngẫu nhiên luôn nằm trong khoảng và phủ đủ mọi giá trị; xáo trộn giữ nguyên số phần tử và không sửa danh sách gốc; chia nhóm giữ mỗi người đúng một lần, sĩ số chênh tối đa 1, nhãn được rải đều kể cả khi nhãn lệch; ghép cặp xử lý đúng số lẻ và tránh cặp cũ khi có thể; khoá nhóm rồi chia lại giữ nguyên nhóm đã khoá.
  • Giao diện được kiểm tra trên Chrome và Safari (WebKit), ở các khổ màn hình từ 320 px đến 2560 px, cả điện thoại ngang, cùng bàn phím, trình đọc màn hình cơ bản và chế độ giảm chuyển động.
  • Mã JavaScript chạy công khai trong trình duyệt của bạn; bạn có thể mở công cụ nhà phát triển để xem đúng các hàm được mô tả ở trên.

Đọc thêm