Gambarkan bilangan bulat secara independen & seragam secara acak dari 1 ke

18

Saya ingin menggambar bilangan bulat dari 1 ke beberapa tertentu dengan menggulirkan sejumlah dadu enam sisi yang adil (d6). Jawaban yang baik akan menjelaskan mengapa metodenya menghasilkan bilangan bulat seragam dan independen .N

Sebagai contoh ilustrasi, akan sangat membantu untuk menjelaskan bagaimana solusi bekerja untuk kasus .N=150

Lebih jauh, saya berharap agar prosedur ini seefisien mungkin: gulirkan rata-rata paling sedikit d6 untuk setiap angka yang dihasilkan.

Konversi dari senary ke desimal diizinkan.


Pertanyaan ini terinspirasi oleh utas Meta ini .

Sycorax berkata Reinstate Monica
sumber

Jawaban:

12

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 dn, katakanlah

F=Pr(t(ω)=Failure)=NFdn.

(Untuk referensi di masa mendatang, perhatikan bahwa jumlah waktu yang diharapkan t harus dipanggil sebelum tidak gagal adalah 1/(1F). )

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),

(1)Pd,n(tA)1F=Pc,m(A)

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 cm.Biarkan t(A) (gulungan dadu yang terkait dengan η ) memiliki elemen Nη . (1) menjadi

(2)Nηdn1NFdn=Pd,n(tA)1F=Pc,m(A)=cm.

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(1F).

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=dnNF>0.

Ini memperjelas bahwa dalam konteks tertentu (ditentukan oleh c,d,n,m ), F dibuat sekecil mungkin dengan membuat dnNF 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×11F.

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/cm1 pendekatan N=1 dalam batas (otomatis menjamin F0 ). Salah satu urutan tersebut diperoleh dengan mengambil n=1,2,3, dan menentukan

(3)m=nlogdlogc.

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 d6untuk mensimulasikan setiap d150hasil.

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 cmdn 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 216150=66 dari hasil tiga gulungan a d6ke Kegagalan dan 150 hasil lainnya masing-masing akan dikaitkan dengan hasil tunggal a d150.

Dalam kasus kedua t akan mengaitkan 7836416409675937500000 dari hasil 14 gulungan a d6ke 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,,d1 dan wajah c sisi dadu dengan angka 0,1,,c1. . 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 d6akan menghasilkan urutan 10.383.070 gulungan a d150dengan tingkat kegagalan kurang dari 2×108, untuk efisiensi 2.79649 dibedakan dari batas asimptotik.

whuber
sumber
2
Luar biasa seperti biasanya, hampir sepertinya jawaban ini diformat dan disiapkan bahkan sebelum pertanyaan diajukan!
Łukasz Grad
1
Terima kasih, @ ŁukaszGrad. Namun, saya tidak bersalah dari tipu daya semacam itu dan saya yakin para pembaca yang tajam akan menemukan bukti dari tergesa-gesa yang telah saya tuliskan ini, yang sebelumnya saya minta maaf.
Whuber
Bukankah seharusnya juga diperhitungkan bahwa ketika tidak prima, ruang sampel Ω ( d , 1 ) dapat dipartisi menjadi himpunan bagian dari probabilitas yang sama? Misalnya, Anda dapat menggunakan d6 sebagai d2 atau d3, & ruang sampel dengan 162 elemen - lebih dekat dengan 150 daripada 216 adalah - kemudian dapat dicapai dengan 4 gulungan, 1d6 + 3d3. (Itu memberikan rol no. Yang diharapkan sama dengan solusi 3d6, tetapi varians yang lebih rendah.)dΩ(d,1)
Scortchi - Reinstate Monica
@Scortchi Anda menguraikan pengaturan yang sedikit berbeda di mana seseorang memiliki pilihan dadu untuk digunakan untuk mensimulasikan menggambar dari distribusi yang seragam. Analisis serupa berlaku - Anda mungkin merasa senang melakukannya.
whuber
7

Untuk kasus N=150 , menggulirkan d6 tiga kali dengan jelas menciptakan 63=216 hasil.

Hasil yang diinginkan dapat ditabulasi dengan cara ini:

  • Rekam d6 tiga kali secara berurutan. Ini menghasilkan hasil a,b,c . Hasilnya seragam karena semua nilai a,b,c memiliki kemungkinan yang sama (dadu adil, dan kami memperlakukan setiap gulungan sebagai berbeda).
  • Kurangi 1 dari masing-masing.
  • Ini adalah angka senary: setiap digit (nilai tempat) bergerak dari 0 hingga 5 dengan kekuatan 6, sehingga Anda dapat menulis angka dalam desimal menggunakan
    (a1)×62+(b1)×61+(c1)×60
  • Tambahkan 1.
  • Jika hasilnya melebihi 150, buang hasilnya dan putar lagi.

Probabilitas menjaga hasil adalah p=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 harapanp1=3625 . Oleh karena itu, menggunakan metode ini untuk menghasilkan 1 hasil undian memerlukan pengerolan3625×3=4.32dadu gulungan rata-rata (karena setiap upaya melempar 3 dadu).


Kredit ke @whuber ke untuk menyarankan ini dalam obrolan.

Sycorax berkata Reinstate Monica
sumber
Saya percaya metode Henry tidak menghasilkan distribusi yang seragam. Itu karena daur ulang akan menyebabkan beberapa digit disukai. Saya tidak sepenuhnya yakin tentang itu karena saya tidak sepenuhnya mengerti bagaimana daur ulang dimaksudkan untuk dilakukan.
whuber
1
@whuber AH! Saya mengerti keprihatinan Anda sekarang. Saya hanya mencoba menjelaskan prosesnya kepada diri saya sendiri dan saya menyadari mengapa intuisi saya cacat: kemungkinan menggulirkan die tambahan dapat mengubah penetapan probabilitas menjadi angka desimal dan menjadikannya tidak seragam karena kita tidak tahu sebelumnya bagaimana banyak dadu yang kami gulung.
Sycorax berkata Reinstate Monica
4

Berikut adalah alternatif yang lebih sederhana untuk jawaban oleh Sycorax untuk kasus di mana N=150 . Karena 150=5×5×6 Anda dapat melakukan prosedur berikut:

Menghasilkan nomor acak seragam dari 1 hingga 150:

  • Buat tiga gulungan 1D6 yang dipesan dan tunjukkan sebagai R1,R2,R3 .
  • Jika salah satu dari dua gulungan pertama adalah enam, putar kembali sampai tidak 6.
  • Angka (R1,R2,R3) adalah angka seragam yang menggunakan notasi posisi dengan radix 5-5-6. Dengan demikian, Anda dapat menghitung angka yang diinginkan sebagai:
    X=30(R11)+6(R21)+(R31)+1.

Metode ini dapat digeneralisasikan ke N lebih besar , tetapi menjadi sedikit lebih canggung ketika nilainya memiliki satu atau lebih faktor prima lebih besar dari 6 .

Pasang kembali Monica
sumber
1
Bisakah Anda menyatakan efisiensi metode ini dalam hal jumlah gulungan yang diharapkan dihasilkan, dan mengklarifikasi mengapa hasilnya seragam pada 1,2, ...., 150?
Sycorax berkata Reinstate Monica
Probabilitas mendapatkan hasil yang tidak memerlukan re-rolling , yang sama seperti dalam jawaban Anda. Untuk memahami mengapa seragam, perhatikan bahwa Anda secara efektif hanya menghasilkan nomor seragam menggunakan notasi posisi dengan radix 5-5-6 (yaitu, digit terakhir adalah unit, digit kedua terakhir adalah "enam" dan yang ketiga Digit terakhir adalah "tiga puluhan"). 25/36
Pasang kembali Monica
1
Metode ini efektif hanya sedikit variasi pada metode dalam jawaban Anda. Dalam jawaban Anda, Anda membuat angka seragam pada skala angka 6-6-6 dan kemudian membuang nilai yang tidak valid, sedangkan dalam jawaban saya, Anda membuang nilai yang tidak valid terlebih dahulu untuk menghasilkan angka pada skala 5-5-6.
Pasang kembali Monica
3
+1 Secara praktis, ini adalah algoritma yang menarik. Ini menarik, dan mungkin menunjukkan analisis yang lebih luas, bahwa itu mengimplementasikan otomat kondisi terbatas yang didorong oleh gulungan mati. Ini memiliki empat negara, {Mulai, A, B, Terima}. Mulai transisi ke A setelah bergulir 1..5; A transisi ke B setelah bergulir 1..5; dan transisi B untuk Menerima setelah menggulirkan apa pun. Setiap transisi menyimpan nilai roll yang menyebabkannya, jadi setelah mencapai Terima Anda mengeluarkan urutan tiga roll yang disimpan dan transisi secara otomatis kembali ke Mulai.
whuber
4
Anda menolak sesering @Sycorax, tetapi membuat gulungan lebih sedikit rata-rata. Tidak diharapkan. gulungan per varian adalah . 65+65+1=3.4
Scortchi
2

Sebagai ilustrasi algoritma untuk memilih secara seragam antara 150 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:

  • Setelah 0 gulungan, Anda memiliki 1 kemungkinan, tidak cukup untuk membedakan 150 nilai
  • Setelah 1 roll, Anda memiliki 6 kemungkinan, tidak cukup untuk membedakan 150 nilai
  • Setelah 2 gulungan, Anda memiliki 36 kemungkinan, tidak cukup untuk membedakan 150 nilai
  • Setelah 3 gulungan, Anda memiliki 216 kemungkinan, cukup untuk membedakan 150 nilai tetapi dengan 66 nilai tersisa; probabilitas Anda berhenti sekarang adalah 150216
  • Jika Anda belum berhenti, maka setelah 4 gulungan Anda memiliki 396 kemungkinan tersisa, cukup untuk membedakan 150 nilai dua arah tetapi dengan 96 nilai tersisa; probabilitas Anda berhenti sekarang adalah 3001296
  • Jika Anda belum berhenti, maka setelah 5 gulungan Anda memiliki 576 kemungkinan tersisa, cukup untuk membedakan 150 nilai tiga cara tetapi dengan 96 nilai tersisa; probabilitas Anda berhenti sekarang adalah 4507776
  • Jika Anda belum berhenti, maka setelah 6 gulungan Anda memiliki 756 kemungkinan tersisa, cukup untuk membedakan 150 nilai lima cara tetapi dengan 6 nilai tersisa; probabilitas Anda berhenti sekarang adalah 75046656

Jika Anda berada di salah satu dari 6 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 , setelah8gulungan adalah1501679616 dll.

Tambahkan ini dan Anda menemukan bahwa jumlah gulungan yang diharapkan adalah sekitar 3.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

  • Pertama, saya akan bekerja di base- 6 dengan 15010=4106
  • Kedua, daripada nilai target 16 hingga 4106 , saya akan mengurangi satu sehingga nilai target adalah 06 hingga 4096
  • Ketiga, setiap dadu harus memiliki nilai 06 hingga 56 , dan menggulung dadu melibatkan penambahan basis 6 digit ke sisi kanan dari angka yang dihasilkan. Angka yang dihasilkan dapat memiliki nol di depan, dan jumlah digit mereka adalah jumlah gulungan sejauh ini

Algoritma ini adalah lemparan dadu berturut-turut:

  • Gulung tiga dadu pertama untuk menghasilkan angka dari 0006 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 100061506=4106 dan berhenti;

  • Jika melanjutkan, putar dadu keempat sehingga Anda sekarang telah menghasilkan angka dari 41006 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 1000062406=53206 dan berhenti;

  • Jika melanjutkan, putar dadu kelima sehingga Anda sekarang telah menghasilkan angka dari 532006 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 10000063306=552306 dan berhenti;

  • Jika melanjutkan, putar dadu keenam sehingga Anda sekarang telah menghasilkan angka dari 5523006 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 10000006106=5555506 dan berhenti;

  • dll.

Henry
sumber
(+1) Jawaban ini akan lebih jelas jika Anda menjelaskan bagaimana Anda memetakan hasil, katakanlah, 4d6 atau 5d6 ke 1,2, ..., 150.
Sycorax mengatakan Reinstate Monica
@ Scorax - Saya sekarang telah menyediakan pemetaan basis 6
Henry
1
Pertimbangan entropi menunjukkan Anda dapat melakukan jauh lebih baik daripada algoritma ini. Ini juga tetap menunjukkan bahwa algoritma Anda benar-benar menghasilkan nilai yang didistribusikan secara independen dengan distribusi yang seragam .
whuber
@whuber - Algoritme saya menghasilkan tepat satu bilangan bulat dari kemungkinan dan melakukannya secara seragam dengan menyediakan gulungan dadu yang seragam dan independen. Pada setiap langkah jika tercapai, masing-masing dari 150 nilai sama-sama cenderung dipilih. Itu tidak menghasilkan banyak nilai (tidak seperti jawaban Anda)150150
Henry
1
Saya salah mengerti apa yang Anda maksudkan, kemudian, dalam menulis "algoritma adalah lemparan dadu yang berurutan." (Seharusnya saya membaca dengan lebih seksama.) Dengan melakukan hal itu, menurut saya algoritma Anda tidak menghasilkan distribusi yang seragam, tetapi saya tidak yakin karena saya belum dapat mengetahui apa yang dimaksud dengan algoritma umum untuk menjadi. Akan bagus untuk melihat demonstrasi yang menghasilkan nilai-nilai yang seragam.
whuber