Himpunan Ω(d,n) dari hasil yang dapat diidentifikasi berbeda dalam n gulungan independen dadu dengan d=6 wajah memiliki elemen dn . Ketika die adalah adil, itu berarti setiap hasil dari satu roll memiliki probabilitas 1/d dan independensi berarti masing-masing hasil karena itu akan memiliki probabilitas (1/d)n: yaitu, mereka memiliki distribusi yang seragam Pd,n.
Misalkan Anda telah merancang beberapa prosedur t yang menentukan m hasil dari die c(=150) - yaitu, elemen Ω(c,m) atau yang lain melaporkan kegagalan (yang berarti Anda harus mengulangi untuk mendapatkan hasil). Itu adalah,
t:Ω(d,n)→Ω(c,m)∪{Failure}.
Misalkan F adalah probabilitas t menghasilkan kegagalan dan catat bahwa F adalah beberapa kelipatan integral dari d−n, katakanlah
F=Pr(t(ω)=Failure)=NFd−n.
(Untuk referensi di masa mendatang, perhatikan bahwa jumlah waktu yang diharapkan t harus dipanggil sebelum tidak gagal adalah 1/(1−F). )
Persyaratan bahwa hasil ini di Ω(c,m) menjadi seragam dan independen bersyarat pada t tidak melaporkan berarti kegagalan yang t mempertahankan probabilitas dalam arti bahwa untuk setiap acara A⊂Ω(c,m),
Pd,n(t∗A)1−F=Pc,m(A)(1)
dimana
t∗(A)={ω∈Ω∣t(ω)∈A}
adalah himpunan gulungan die bahwa prosedur t ditunjuk untuk acara A.
Pertimbangkan peristiwa atom A={η}⊂Ω(c,m) , yang harus memiliki probabilitas c−m.Biarkan t∗(A) (gulungan dadu yang terkait dengan η ) memiliki elemen Nη . (1) menjadi
Nηd−n1−NFd−n=Pd,n(t∗A)1−F=Pc,m(A)=c−m.(2)
Hal ini langsung bahwa Nη semua sama untuk beberapa bilangan bulat N. Tetap hanya untuk menemukan prosedur yang paling efisien t. Jumlah yang diharapkan non-kegagalan per roll dari sisi c mati adalah
1m(1−F).
Ada dua implikasi langsung dan jelas. Salah satunya adalah jika kita dapat menjaga F kecil ketika m tumbuh besar, maka efek melaporkan kegagalan adalah asimtotik nol. Yang lainnya adalah bahwa untuk setiap m diberikan (jumlah gulungan c side sided untuk disimulasikan), kami ingin membuat F sekecil mungkin.
Mari kita perhatikan lebih dekat (2) dengan menghapus penyebut:
Ncm=dn−NF>0.
Ini memperjelas bahwa dalam konteks tertentu (ditentukan oleh c,d,n,m ), F dibuat sekecil mungkin dengan membuat dn−NF sama dengan kelipatan cm yang kurang dari atau sama dengan dn. Kami dapat menulis ini dalam hal fungsi integer terbesar (atau "lantai") ⌊∗⌋ as
N=⌊dncm⌋.
Akhirnya, jelas bahwa N harus sekecil mungkin untuk efisiensi tertinggi, karena ia mengukur redundansi dalam t . Secara khusus, jumlah yang diharapkan dari gulungan dari d -sided mati diperlukan untuk memproduksi satu gulungan c -sided die is
N×nm×11−F.
Dengan demikian, pencarian kami untuk prosedur efisiensi tinggi harus fokus pada kasus-kasus di mana dn sama dengan, atau hanya sedikit lebih besar dari, beberapa kekuatan cm.
Analisis berakhir dengan menunjukkan bahwa untuk diberikan d dan c, ada urutan kelipatan (n,m) dimana pendekatan ini mendekati efisiensi sempurna. Ini jumlah untuk mencari (n,m) yang dn/cm≥1 pendekatan N=1 dalam batas (otomatis menjamin F→0 ). Salah satu urutan tersebut diperoleh dengan mengambil n=1,2,3,… dan menentukan
m=⌊nlogdlogc⌋.(3)
Buktinya mudah.
Ini semua berarti bahwa ketika kita bersedia untuk menggulung d sisi yang asli dengan jumlah yang cukup besar , n, kita dapat mensimulasikan hampir logd/logc=logcd hasil dari c sided dadu per roll. Setara,
Dimungkinkan untuk mensimulasikan sejumlah besar m dari gulungan independen dari c sisi dadu menggunakan d sisi mati adil menggunakan rata-rata log(c)/log(d)+ϵ=logd(c)+ϵ gulungan per hasil di mana ϵ dapat dibuat sewenang-wenang kecil dengan memilih m cukup besar.
Contoh dan algoritme
Dalam pertanyaan, d=6 dan c=150, dari mana
logd(c)=log(c)log(d)≈2.796489.
Dengan demikian, prosedur terbaik yang mungkin akan membutuhkan, rata-rata, setidaknya 2.796489 gulungan d6
untuk mensimulasikan setiap d150
hasil.
Analisis menunjukkan bagaimana melakukan ini. Kita tidak perlu menggunakan teori bilangan untuk melaksanakannya: kita bisa menabulasi kekuatan dn=6n dan kekuatan cm=150m dan membandingkannya untuk menemukan di mana cm≤dn dekat. Perhitungan brute force ini menghasilkan (n,m) pasangan
(n,m)∈{(3,1),(14,5),…}
misalnya, sesuai dengan angka
(6n,150m)∈{(216,150),(78364164096,75937500000),…}.
Dalam kasus pertama t akan mengaitkan 216−150=66 dari hasil tiga gulungan a d6
ke Kegagalan dan 150 hasil lainnya masing-masing akan dikaitkan dengan hasil tunggal a d150
.
Dalam kasus kedua t akan mengaitkan 78364164096−75937500000 dari hasil 14 gulungan a d6
ke Kegagalan - sekitar 3,1% dari semuanya - dan jika tidak akan menghasilkan urutan 5 hasil dari a d150
.
Algoritma sederhana untuk mengimplementasikan t memberi label wajah d sisi dadu dengan angka 0,1,…,d−1 dan wajah c sisi dadu dengan angka 0,1,…,c−1. . n gulungan dadu pertama ditafsirkan sebagai n jumlah -digit dalam basis d. Ini dikonversikan ke angka dalam basis c. Jika memiliki maksimal m digit, urutan m terakhirmdigit adalah output. Jika tidak, t mengembalikan Kegagalan dengan memohon sendiri secara rekursif.
Untuk urutan yang lebih lama, Anda dapat menemukan pasangan yang cocok (n,m) dengan mempertimbangkan setiap n/m konvergen ekspansi fraksi lanjutan dari x=log(c)/log(d). Teori fraksi lanjutan menunjukkan bahwa konvergen ini bergantian antara kurang dari x dan lebih besar dari itu (dengan anggapan x belum rasional). Pilih yang kurang dari x.
Dalam pertanyaan itu, beberapa konvergensi pertama adalah
3,14/5,165/59,797/285,4301/1538,89043/31841,279235/99852,29036139/10383070….
Dalam kasus terakhir, urutan 29.036.139 gulungan a d6
akan menghasilkan urutan 10.383.070 gulungan a d150
dengan tingkat kegagalan kurang dari 2×10−8, untuk efisiensi 2.79649 dibedakan dari batas asimptotik.
Untuk kasusN=150 , menggulirkan d6 tiga kali dengan jelas menciptakan 63=216 hasil.
Hasil yang diinginkan dapat ditabulasi dengan cara ini:
Probabilitas menjaga hasil adalahp=150216=2536 . Semua gulungan independen, dan kami mengulangi prosedur sampai "sukses" (hasil dalam1,2,…,150 ) sehingga jumlahupayauntuk menghasilkan 1 hasil imbang antara 1 dan 150 didistribusikan sebagai variabel acak geometrik, yang memiliki harapanp−1=3625 . Oleh karena itu, menggunakan metode ini untuk menghasilkan 1 hasil undian memerlukan pengerolan3625×3=4.32 dadu gulungan rata-rata (karena setiap upaya melempar 3 dadu).
Kredit ke @whuber ke untuk menyarankan ini dalam obrolan.
sumber
Berikut adalah alternatif yang lebih sederhana untuk jawaban oleh Sycorax untuk kasus di manaN=150 . Karena 150=5×5×6 Anda dapat melakukan prosedur berikut:
Metode ini dapat digeneralisasikan keN lebih besar , tetapi menjadi sedikit lebih canggung ketika nilainya memiliki satu atau lebih faktor prima lebih besar dari 6 .
sumber
Sebagai ilustrasi algoritma untuk memilih secara seragam antara150 nilai menggunakan dadu enam sisi, coba ini yang menggunakan setiap gulungan untuk mengalikan nilai yang tersedia dengan 6 dan membuat masing-masing nilai baru sama-sama mungkin:
Jika Anda berada di salah satu dari6 nilai yang tersisa setelah 6 gulungan maka Anda berada dalam situasi yang sama dengan posisi setelah 1 gulungan. Jadi Anda bisa melanjutkan dengan cara yang sama: probabilitas Anda berhenti setelah 7 gulungan adalah 0279936 , setelah8 gulungan adalah1501679616 dll.
Tambahkan ini dan Anda menemukan bahwa jumlah gulungan yang diharapkan adalah sekitar3.39614 . Ini memberikan pilihan yang seragam dari 150 , karena Anda hanya memilih nilai pada saat Anda dapat memilih masing-masing dari 150 dengan probabilitas yang sama
Sycorax bertanya dalam komentar untuk algoritma yang lebih eksplisit
Algoritma ini adalah lemparan dadu berturut-turut:
Gulung tiga dadu pertama untuk menghasilkan angka dari0006 hingga 5556 . Karena 10006÷4106=16 remainder 1506 Anda mengambil nilai yang dihasilkan (yang juga sisanya pada pembagian dengan 4106 ) jika nilai yang dihasilkan benar-benar di bawah 10006−1506=4106 dan berhenti;
Jika melanjutkan, putar dadu keempat sehingga Anda sekarang telah menghasilkan angka dari41006 hingga 55556 . Karena 100006÷4106=126 remainder 2406 Anda mengambil sisa dari nilai yang dihasilkan di divisi dengan 4106 jika nilai yang dihasilkan benar-benar di bawah 100006−2406=53206 dan berhenti;
Jika melanjutkan, putar dadu kelima sehingga Anda sekarang telah menghasilkan angka dari532006 hingga 555556 . Karena 1000006÷4106=1236 remainder 3306 Anda mengambil sisa dari nilai yang dihasilkan di divisi dengan 4106 jika nilai yang dihasilkan benar-benar di bawah 1000006−3306=552306 dan berhenti;
Jika melanjutkan, putar dadu keenam sehingga Anda sekarang telah menghasilkan angka dari5523006 hingga 5555556 . Karena 10000006÷4106=12356 remainder 106 Anda mengambil sisa dari nilai yang dihasilkan di divisi dengan 4106 jika nilai yang dihasilkan benar-benar di bawah 10000006−106=5555506 dan berhenti;
dll.
sumber