Cara mensimulasikan dadu diberi koin yang adil

21

Misalkan Anda diberi koin yang adil dan Anda ingin mensimulasikan distribusi probabilitas berulang kali membalik mati (enam sisi) yang adil. Ide awal saya adalah bahwa kita perlu memilih bilangan bulat yang sesuai , sehingga . Jadi setelah membalik koin kali, kami memetakan angka yang dikodekan oleh bitstring k-panjang untuk output dari die dengan membagi kisaran menjadi 6 interval masing-masing panjang . Namun, ini tidak mungkin, karena memiliki dua sebagai satu-satunya faktor prima tetapi faktor utama mencakup tiga. Seharusnya ada cara sederhana lain untuk melakukan ini, bukan? $k,m$ $2^k = 6m$ $k$ $[0,2^k-1]$ $m$ $2^k$ $6m$

probability-theory randomness sampling probability_guy
sumber

Lihat pertanyaan ini di mana masalah ini ditangani dengan cara yang lebih umum.

Raphael

Inilah artikel tentang masalah ini . Ini menjelaskan cara menggunakan sampel penolakan dan cara menggunakan kembali bit "terbuang" untuk mempercepat gulungan lebih lanjut.

ZeroUltimax

12

Untuk memiliki metode yang sedikit lebih efisien daripada yang ditunjukkan oleh @FrankW tetapi menggunakan ide yang sama, Anda dapat membalik koin Anda kali untuk mendapatkan angka di bawah . Kemudian tafsirkan ini sebagai batch flips, di mana adalah angka terbesar sehingga (seperti yang sudah dikatakan, kesetaraan tidak pernah berlaku di sini). Jika Anda mendapatkan angka yang lebih besar atau sama dengan Anda harus menolak nilainya dan ulangi semua flips. $n$ $2^n$ $m$ $m$ $6^m < 2^n$ $6^m$ $n$

Anda dapat mengimplementasikan fungsi yang mengembalikan satu kali lipat flip dengan membuat koin membalik dan kemudian men-cache hasilnya untuk permintaan flip-flip berikut . $n$ $m-1$

Poin yang menarik adalah bahwa beberapa nilai lebih baik daripada yang lain karena mereka memiliki tingkat penolakan yang kurang. Berikut adalah daftar nilai yang baik (yaitu nilai yang memiliki tingkat penolakan lebih rendah dari yang sebelumnya): $n$

n m r
3 1 0.25
8 3 0.15625
13 5 0.05078125
44 17 0.0378308072686
75 29 0.0247036782182
106 41 0.0113974522704
243 94 0.00933096248381
380 147 0.00726015308463
517 200 0.00518501504347
654 253 0.00310553931213
791 306 0.00102171682348

diperoleh dengan rumus: .

m = ⌊ n \log_{3} 2 ⌋ r = 1 - \frac{3^{m}}{2^{n}}

$m = \lfloor {n\log_3 2} \rfloor \\ r = 1 - \frac{3^m}{2^n}$

Baris pertama sesuai dengan jawaban @ FrankW dengan tingkat penolakan 25%. Angka-angka berikut ini bagus: dan keduanya dapat disimpan dalam variabel statis integer tunggal. Secara khusus tingkat penolakan hanya 5% yang merupakan peningkatan yang masuk akal sehubungan dengan 25% dan menjadikan ini kandidat yang baik untuk implementasi yang mungkin. $n=8$ $n=13$ $n=13$

Emanuele Paolini
sumber

Anda tidak perlu 6 ^ m, 6 * m sudah cukup. Jadi Anda bisa menggunakan 5 lemparan untuk mendapatkan nomor 5 bit yang menolak hanya 1/16 kasing.

Taemyr

Tingkat penolakan 5% untuk 13 kali lemparan itu mengerikan, jika dibandingkan dengan 25% untuk 3 kali lemparan. Karena 25% untuk 3 kali lemparan hanya akan menolak 4 kali (mis. Menghabiskan lebih dari 12 kali lemparan) di 0,390625% dari kasus.

Taemyr

@ Taemyr angka 5 bit dapat mewakili 32 nilai yang berbeda yang memungkinkan Anda untuk mewakili satu dadu (karena dua dadu memiliki 36 kemungkinan). Jadi hanya nilai 6/32 yang dapat diterima dengan tingkat penolakan 27/32 = 84%

Emanuele Paolini

@ Taemyr: tingkat tolak

pada

tosses berarti bahwa, rata-rata setiap batch dari

tosses akan ditolak dengan probabilitas

. Jadi, secara rata-rata, setiap lemparan ditolak dengan laju

sama (tidak tergantung pada

).

r

$r$

n

$n$

n

$n$

r

$r$

r

$r$

n

$n$

Emanuele Paolini

Iya nih. Dan menggunakan metode FrankW yang memiliki tingkat rejetion 25% untuk batch 3 kali lemparan, Anda akan memiliki probabilitas 1-0.00390625 untuk diterima selambat-lambatnya dari batch ke-4.

Taemyr

29

Yang dapat Anda lakukan, adalah menggunakan metode yang disebut sampling penolakan :

Balikkan koin 3 kali dan tafsirkan setiap flip sedikit (0 atau 1).
Menggabungkan 3 bit, memberikan angka biner dalam . $[0,7]$
Jika nomornya ada di , anggap saja sebagai die roll. $[1,6]$
Kalau tidak, yaitu jika hasilnya atau , ulangi membalik. $0$ $7$

Sejak dari kemungkinan hasil mengarah ke penghentian di setiap set, probabilitas membutuhkan lebih dariset membalik untuk mendapatkan die roll adalah $\frac 68$ $l$ . Karenanya, metode ini efisien dalam praktiknya. $(1-\frac 68)^l = \dfrac 1{4^l}$

Perbaikan:

Jawaban @ Angel menunjukkan, bahwa jumlah koin membalik di setiap set tetapi yang pertama dapat dikurangi dari 3 menjadi 2, dengan menggunakan perbedaan antara dan sebagai bit pertama untuk set berikutnya. $0$ $7$

@Emanuele Paolini menjelaskan, bagaimana Anda dapat mengurangi jumlah rerolls, jika Anda memerlukan beberapa gulungan gulungan.

FrankW
sumber

Tidakkah metode ini akan memberikan kecenderungan sentral yang lebih besar daripada d6 sejati?

Red_Shadow

3

@Red_Shadow No. Perhatikan bahwa Anda tidak menambahkan lemparan koin (tiga tidak akan cukup, lalu) tetapi Anda memilih setiap bit dalam

bit biner number by coin. Dengan demikian, Anda sampel secara seragam dari

dan menolak angka bukan dari interval target; ini hanya dapat menghasilkan distribusi seragam pada interval target.

k

$k$

[{0..2}^{k} - 1]

$[0..2^k - 1]$

Raphael

Jika Anda licik dengan rentang yang ditolak, dalam kasus ini sebenarnya mudah untuk menggunakannya untuk mengurangi jumlah koin yang diperlukan dalam kasus penolakan.

Mooing Duck

@MooingDuck Anda dapat memutuskan apakah akan membuang hasil Anda setelah 2 kali lemparan: jika itu adalah 0,0 0,1 atau 1,0 lalu aduk lagi untuk bit terakhir atau mulai lagi dari awal

ratchet freak

1

@NikosM. Probabilitas untuk mengambil lebih lama dari

langkah menurun menuju nol secara eksponensial, meskipun, jadi jawabannya tidak membuat klaim yang salah: itu adalah efisien dalam praktek, dan pada kenyataannya digunakan secara luas. (Untuk distribusi yang lebih rumit, ini sering merupakan satu-satunya metode yang diketahui.)

k

$k$

Raphael

7

Alternatif untuk sampel penolakan (seperti dijelaskan dalam jawaban FrankW ) adalah dengan menggunakan algoritma penskalaan, yang memperhitungkan jawaban [7,8] seolah-olah itu adalah koin lain yang membalik.

Ada penjelasan yang sangat rinci di mathforum.org , termasuk algoritma (itu NextBit()akan membalik koin Anda yang adil).

Kasus untuk melempar dadu dengan koin yang adil (pengambilan sampel 2 → 6) lebih mudah daripada algoritma umum. Anda hanya mengambil kegagalan (7 atau 8) sebagai input koin lain dan melakukan dua flips lagi.

Malaikat
sumber

2

Pendekatan lain untuk mensimulasikan gulungan dN menggunakan dM (dalam kasus pertanyaan spesifik yang diajukan d6 menggunakan d2) adalah mempartisi interval [0, 1) menjadi N dengan interval yang sama dengan panjang 1 / N, [0, 1 / N), [1 / N, 2 / N), ..., [(N-1) / N, N).

Gunakan dM untuk menghasilkan fraksi basis-M, 0.bbbb ..., dalam [0, 1). Jika itu termasuk dalam [(i-1) / N, i / N), anggap saya sebagai gulungan dN. Perhatikan bahwa Anda hanya perlu menghasilkan digit basis-M yang cukup dari fraksi untuk menentukan intervalnya.

tzs
sumber

Kondisi penghentian harus dibuat lebih tepat. Jika saya membalik koin begitu saya berakhir dengan fraksi biner 0,0 atau 0,1 (yaitu ½), keduanya jatuh ke dalam interval (masing-masing sesuai dengan 0 dan 3, dalam kasus ini). Anda perlu menganggap fraksi yang dihasilkan sebagai rentang dan Anda berhenti ketika seluruh rentang dalam satu interval. Saya yakin itulah yang Anda maksudkan tetapi saya tidak berpikir itu jelas.

rici

1

Penjelasan yang mungkin lebih sederhana tentang pengambilan sampel penolakan yang ditingkatkan.

Saya memberikan penjelasan ini karena semoga dapat membantu menyederhanakan pemahaman atau analisis probabilitas dalam beberapa situasi.

FrankW menyarankan menggunakan sampel penolakan, membalik koin tiga kali, menjaga hasilnya jika berada di kisaran yang tepat, atau mengulangi tiga membalik sebaliknya, hingga sukses.

Ángel menyarankan untuk menyimpan satu flip pada setiap percobaan, menggantinya dengan pilihan biner yang tersisa dari dua nilai yang tidak digunakan dari set sebelumnya tiga.

Ini benar-benar berarti bahwa satu bit informasi dihasilkan dengan tiga membalik pertama, yang tidak perlu diproduksi. Lebih tepatnya, Anda harus membalik koin hanya dua kali untuk mengetahui apakah set flips saat ini akan berhasil.

Mengetahui apakah set flip saat ini akan berhasil adalah satu-satunya probabilitas yang penting , karena menafsirkan set flip yang sukses adalah probabilitas independen. Dan ini bisa diketahui sebelum semua flips diselesaikan untuk set itu.

Ini dapat dicapai setidaknya dalam dua cara, atau lebih tepatnya dalam dua interpretasi yang berbeda dari flip. Mungkin ada yang lain.

Pengelompokan menghasilkan berpasangan

Idenya adalah untuk mempertimbangkan hanya tiga nilai (1,2), (3,4) dan (5,6) yang diwakili oleh tiga konfigurasi double-flip, katakanlah TT, TH, HT. Kemudian, Anda dapat menerapkan sampel penolakan dengan membalik ganda, berulang setiap kali Anda mendapatkan konfigurasi kegagalan HH.

Setelah Anda mendapatkan salah satu dari tiga konfigurasi yang berhasil, Anda cukup membalik koin sekali lagi untuk memutuskan apakah Anda harus mengambil nilai pertama atau kedua dari pasangan yang sesuai.

Deteksi dini kegagalan flip-set

Idenya adalah menggunakan pembacaan yang sedikit berbeda dari konfigurasi tiga flip. Jika Head dan Tail ditafsirkan sebagai 1 dan 0, maka konfigurasi harus sesuai dengan interpretasi biner ditambah satu. Yaitu TTT (yaitu 000) sesuai dengan 1, HTH (yaitu 101) sesuai dengan 6, HHT (yaitu 110) dan HHH (yaitu 111) sesuai dengan 7 dan 8, atau apa pun di luar [1,6].

Kemudian kita tahu bahwa flip-set berhasil atau gagal hanya dengan dua flip pertama. Jika mereka menghasilkan HH, set flip gagal terlepas dari flip terakhir. Jadi bisa dilewati.

Saya pikir deteksi dini selalu dapat digunakan sebagai penjelasan, tetapi tergantung pada jumlah wajah pada dadu simulasi Anda, deteksi kegagalan dapat terjadi setelah sejumlah variabel membalik.

Misalnya untuk dadu 10 wajah, pada prinsipnya Anda perlu set flip 4 membalik, dengan 6 konfigurasi yang sesuai dengan kegagalan. Kuncinya adalah memiliki semua konfigurasi kegagalan di urutan teratas dari nilai-nilai biner sebagai berikut:

TTTT  0000   1
HTTT  1000   9
HTTH  1001  10
HTHT  1001  11
HTHH  1011  12
HHTT  1100  13
HHHH  1111  16

Konfigurasi yang berhasil sesuai dengan rentang [1, 10] dan kegagalan untuk rentang [11,16].

Maka Anda gagal ketika dua membalik pertama memberi HH, atau ketika tiga membalik pertama memberikan HTH, tanpa harus bahkan mencoba membalik hilang dari set.

Jika Anda tidak gagal, Anda cukup menghentikan set flips.

babou
sumber

1

Ada dua pendekatan terkenal untuk ini. Salah satunya adalah "sampel penolakan". Misalnya, gunakan tiga bit untuk memilih satu dari enam nilai, coba lagi untuk dua sampel tambahan. Atau gunakan 14 bit (nilai 8192) untuk memilih 5 nilai dari 1 hingga 6 (7776 kemungkinan), coba lagi dalam 13 dari 256 kasus.

Yang lainnya adalah menggunakan bagian dekompresi dari algoritma kompresi / dekompresi: Dengan pengkodean aritmatika, suatu urutan nilai acak dari 1 hingga 6 dapat dikompres dengan hampir tanpa redundansi. Buat urutan terkompresi secara acak, dan dekompreslah. Ini jauh lebih rumit, tetapi praktis tidak akan memerlukan nomor acak tambahan.

gnasher729
sumber

0

Maaf sebelumnya jika penjelasannya berlebihan. Saya tidak yakin berapa banyak detail untuk masuk atau seberapa mudah konsep itu dipahami.

Katakanlah Anda memiliki tiga koin (koin adil). Jika Anda secara bertahap memberikan nilai ke setiap sisi dari setiap koin, Anda akan memiliki enam nilai.

Seperti itu: Pada koin pertama, kepala adalah 1 dan ekor adalah 2. Pada koin kedua, kepala adalah 3 dan ekor adalah 4. Pada koin ketiga, kepala adalah 5 dan ekor adalah 6.

Membalik koin akan meninggalkan Anda dengan satu set tiga angka, set Anda saat ini. Sekarang, set Anda saat ini akan menjadi set sebelumnya dan Anda akan mengulangi proses untuk mendapatkan set baru tiga angka.

Terus lakukan ini hingga satu dan hanya satu angka yang cocok dari set Anda saat ini dengan set sebelumnya. Itu nomormu.

Jadi jika Anda mendapatkan [kepala, ekor, kepala] untuk set saat ini, itu akan menjadi [1, 4, 5]. Sekarang Anda balikkan lagi dan set Anda saat ini adalah [2, 4, 5]. Dua pertandingan. Tidak baik. Coba lagi. Anda mendapatkan [2, 3, 6]. Hanya satu yang cocok. Nomor Anda dua.

Akan ada peluang yang sama bahwa setiap angka yang diberikan akan muncul, tetapi itu tidak terlalu hemat biaya, mengingat bahwa hanya ada perubahan 3/32 bahwa setiap pasangan perangkat akan berhasil (hanya satu pertandingan). Jadi rata-rata, algoritma harus mengulang sekitar sepuluh kali. Juga, tidak mudah digeneralisasikan untuk mati bernomor ganjil.

Paling tidak, mungkin itu makanan untuk dipikirkan. Pertanyaan yang sangat menarik.

Dan D
sumber

4

Ini akan selalu berkinerja besar-besaran, jauh lebih buruk daripada sampel penolakan. Untuk sampel penolakan, Anda hanya perlu membalik

⌈ \log n ⌉

$\lceil \log n\rceil$ koin untuk mensimulasikan

n

$n$ sisi-die dan setiap set flips berhasil dengan probabilitas yang benar-benar lebih besar dari

\frac{1}{2}

$\tfrac12$ . Metode yang Anda usulkan mengharuskan Anda membalik

\frac{n}{2}

$\tfrac{n}{2}$ koin dan setiap set flips hanya berhasil dengan probabilitas

n / 2^{n}

$n/2^n$ .

David Richerby

0

Saya akan membalik koin tiga kali dan menafsirkan hasilnya sebagai angka biner, menolak hasil di luar jangkauan.

Misalnya, biarkan kepala menjadi 1 dan ekor menjadi 0. Jika Anda membaliknya tiga kali dan mendapat kepala, ekor, kepala, Anda akan memiliki biner 101, yaitu 5 dalam desimal. HHT = 110b = 6. TTT = 000b = 0 dan HHH = 111b = 7, keduanya di luar jangkauan dan akan ditolak, dan Anda akan merefleksikan semua digit.

Sohcahtoa82
sumber

1

Itu hanya jawaban Frank.

Raphael

2

@ Raphael Sebenarnya, bagian ketat dari jawaban Frank, karena Frank membahas waktu berjalan yang diharapkan.

David Richerby

0

Sayangnya seseorang tidak dapat (dengan setia) mensimulasikan kematian (adil) menggunakan (urutan) koin yang adil.

Hanya karena ruang acara dadu memiliki dimensi $6$ dan ini tidak bisa persis cocok dengan kekuatan $2$ (Itulah yang disediakan oleh ruang acara dari koin yang adil).

Tetapi orang dapat melakukan ini dengan "koin tiga" yang adil (jika istilah seperti itu dapat digunakan). Berarti koin dengan 3 hasil. Dan koin 2 sederhana, jadi ruang gabungan dari 2 koin ini cocok persis dengan ruang acara die.

Sampling penolakan (seperti yang disebutkan dalam beberapa jawaban) dapat memberikan perkiraan simulasi . Tetapi masih akan memiliki sejumlah kesalahan atau salah-kecocokan probabilitas (dalam waktu yang terbatas). Jadi, jika seseorang ingin benar-benar mencocokkan ruang acara dari 2 sistem ini, akan ada kasus yang tidak akan berfungsi.

Dalam simulasi probabilistik (yang sampel penolakannya merupakan contoh), sekuens khas yang dihasilkan memang menunjukkan probabilitas elementer relatif (dalam hal ini ruang kejadian die). Namun (seperti yang disebutkan dalam komentar) masing-masing urutan khas ini dapat berisi sub-urutan panjang sewenang-wenang dari hasil yang persis sama. Ini berarti bahwa untuk menggunakan sampel penolakan (dalam beberapa kasus) dapat memakan waktu lama atau distribusi yang dihasilkan akan bias (yaitu tidak adil), karena terlalu banyak representasi atau kurang terwakili dari beberapa bagian ruang acara . jika ini tidak terjadi, maka algoritma deterministik akan mungkin yang akan persis cocok dengan ruang acara dadu dan koin (yang tidak cocok dengan dimensi).

Nikos M.
sumber

Komentar bukan untuk diskusi panjang; percakapan ini telah dipindahkan ke obrolan .

Gilles 'SANGAT berhenti menjadi jahat'

@Gilles, suara negatif yang terlalu buruk masih ada di sini, terlepas dari semua penjelasan dan obrolan (tentang kebenaran) yang terjadi: p

Nikos M.

Cara mensimulasikan dadu diberi koin yang adil

Jawaban:

Penjelasan yang mungkin lebih sederhana tentang pengambilan sampel penolakan yang ditingkatkan.