Matematika Pengacakan yang Adil

Pengacakan mengajukan pertanyaan matematika yang tepat: diberikan n objek berbeda, hasilkan salah satu dari n! kemungkinan urutan, masing-masing dengan probabilitas yang identik. Untuk 12 bilangan bulat, itu berarti 479,001,600 permutasi. Urutan di atas dipilih dari ruang tersebut dengan probabilitas seragam, dihasilkan sepenuhnya di dalam browser Anda menggunakan algoritma Fisher-Yates dan Web Cryptography API.

Fisher-Yates: Algoritma Definitif

Ronald Fisher dan Frank Yates mendeskripsikan metode pengacakan asli dalam buku mereka tahun 1938 Statistical Tables for Biological, Agricultural and Medical Research. Donald Knuth kemudian menyempurnakannya untuk implementasi komputer dalam The Art of Computer Programming (1969). Versi modern berjalan mundur melalui array. Pada setiap posisi, ia memilih elemen acak dari bagian yang belum diacak dan menukarnya. Satu kali iterasi melalui data menghasilkan pengacakan seragam sempurna dalam waktu O(n) menggunakan ruang tambahan O(1).

Bukti kebenaran menunjukkan bahwa setelah memproses posisi k, setiap dari k! kemungkinan sub-susunan dari k elemen pertama memiliki kemungkinan yang sama. Secara induksi, hasil akhir mencakup semua n! permutasi dengan probabilitas seragam. Kesalahan implementasi yang umum, yaitu "naive shuffle," memilih dari seluruh array pada setiap langkah alih-alih dari bagian yang belum diproses. Ini menghasilkan nⁿ urutan pertukaran yang dipetakan ke n! permutasi. Karena nⁿ umumnya tidak habis dibagi n!, beberapa permutasi menjadi lebih mungkin daripada yang lain. Algoritma Fisher-Yates menghindari hal ini sepenuhnya.

Skala Permutasi yang Mencengangkan

Pertumbuhan faktorial melampaui setiap fungsi matematika umum lainnya. Sepuluh item menghasilkan 3.628.800 susunan. Dua puluh item menghasilkan lebih dari 2,4 kuintiliun. Satu dek standar 52 kartu menghasilkan sekitar 8,07 \xC3\x97 10\xE2\x81\xB6\xE2\x81\xB7 kemungkinan urutan. Angka tersebut melebihi perkiraan jumlah atom di alam semesta yang dapat diamati.

Bayangkan: jika setiap atom di alam semesta mengacak satu dek kartu setiap nanodetik, dan telah melakukannya sejak Big Bang 13,8 miliar tahun yang lalu, total pengacakan yang dilakukan masih akan menjadi fraksi yang sangat kecil dari 52!. Setiap pengacakan yang Anda lakukan di halaman ini hampir pasti menciptakan susunan yang belum pernah ada sebelumnya dan tidak akan pernah ada lagi.

Titik Tetap: Paradoks Derangement

Titik tetap adalah angka yang berakhir di posisi aslinya setelah pengacakan. Perhatikan lingkaran bercincin emas di atas: itulah titik tetap Anda. Jumlah titik tetap yang diharapkan adalah tepat 1, berapa pun jumlah item yang Anda acak. Sepuluh item, satu titik tetap yang diharapkan. Sepuluh ribu item, tetap satu.

Probabilitas elemen tertentu tetap di tempatnya adalah 1/n. Dijumlahkan untuk n elemen, jumlah yang diharapkan sama dengan 1. Hasil ini, yang terkait dengan konsep matematika derangement yang dipelajari oleh Leonhard Euler, berarti sekitar 36,8% dari semua pengacakan memiliki nol titik tetap, 36,8% memiliki tepat satu, 18,4% memiliki tepat dua, dan probabilitasnya turun dengan cepat setelahnya.

Teorema Tujuh Pengacakan

Persi Diaconis dan Dave Bayer membuktikan pada tahun 1992 bahwa riffle shuffle standar pada dek 52 kartu memerlukan tepat tujuh iterasi untuk mencapai pengacakan yang memadai. Pengacakan Fisher-Yates digital mencapai apa yang didekati oleh tujuh riffle shuffle fisik: pengacakan seragam sempurna dalam satu kali proses komputasi.

Di Ruang Kelas

Minta setiap siswa mengunjungi /sequence/1/10 dan mengacak sekali. Lalu tanyakan: apakah ada dua siswa yang menghasilkan urutan yang sama? Dengan 3.628.800 kemungkinan susunan, kecocokan sangat tidak mungkin terjadi. Untuk demonstrasi proyektor, buka /sequence/1/52 dan acak berulang kali. Cincin-cincin berwarna cerah tersebar menjadi pola baru setiap kali, membuat keacakan langsung terlihat secara visual. Alat ini tidak memerlukan akun, tidak menyimpan cookie, dan tidak menyimpan data siswa.