Ini adalah pertanyaan yang saya temukan di Glassdoor : Bagaimana cara menghasilkan 7 bilangan bulat dengan probabilitas yang sama menggunakan koin yang memiliki ?
Pada dasarnya, Anda memiliki koin yang mungkin atau mungkin tidak adil, dan ini adalah satu-satunya proses penghasil angka acak yang Anda miliki, jadi buatlah generator bilangan acak yang menghasilkan bilangan bulat dari 1 hingga 7 di mana kemungkinan mendapatkan masing-masing bilangan bulat ini adalah 1/7.
Efisiensi data-menghasilkan hal-hal proses.
probability
binomial
random-generation
Orang Amazon
sumber
sumber
Jawaban:
Balikkan koin dua kali. Jika itu mendarat
HH
atauTT
, abaikan dan balikkan dua kali lagi.Sekarang, koin memiliki probabilitas yang sama untuk muncul
HT
atauTH
. Jika munculHT
, panggil iniH1
. Jika munculTH
, panggil iniT1
.Terus dapatkan
H1
atauT1
sampai Anda memiliki tiga berturut-turut. Tiga hasil ini memberi Anda angka berdasarkan tabel di bawah ini:Saya berpendapat bahwa ini akan bekerja dengan baik, meskipun Anda akan memiliki banyak lemparan yang sia-sia dalam prosesnya!
sumber
Asumsikan .p∈(0,1)
Langkah 1: . Lempar koin 5 kali.
Jika hasilnya
1(H,H,H,T,T) , kembali dan berhenti.1
2(H,H,T,T,H) , kembali dan berhenti.2
3(H,T,T,H,H) , kembali dan berhenti.3
4(T,T,H,H,H) , kembali dan berhenti.4
5(T,H,H,H,T) , kembali dan berhenti.5
6(H,H,T,H,T) , kembali dan berhenti.6
7(H,T,H,T,H) , kembali dan berhenti.7
Langkah 2: . Jika hasilnya tidak ada di atas, ulangi Langkah 1.
Perhatikan bahwa terlepas dari nilai , masing-masing dari tujuh hasil yang tercantum di atas memiliki probabilitas , dan jumlah lemparan koin yang diharapkan adalah . Server tidak perlu mengetahui nilai (kecuali bahwa dan ); dijamin bahwa tujuh bilangan bulat memiliki kemungkinan yang sama untuk dikembalikan oleh percobaan ketika berakhir (dan dijamin berakhir dengan probabilitas ).q = p 3 ( 1 - p ) 2 5p∈(0,1) q=p3(1−p)2 pp≠0p≠1157q p p≠0 p≠1 1
sumber
Generalisasi kasus yang dijelaskan oleh Dilip Sarwate
Beberapa metode yang dijelaskan dalam jawaban lain menggunakan skema di mana Anda melempar urutann koin dalam 'belokan' dan tergantung pada hasil Anda memilih angka antara 1 atau 7 atau membuang belokan dan melempar lagi.
Kuncinya adalah menemukan dalam perluasan kemungkinan kelipatan 7 hasil dengan probabilitas yang samapk(1−p)n−k dan mencocokkannya dengan satu sama lain.
Karena jumlah total hasil bukan kelipatan 7, kami memiliki beberapa hasil yang tidak dapat kami tetapkan ke suatu angka, dan memiliki beberapa probabilitas bahwa kami perlu membuang hasil dan memulai lagi.
Kasus menggunakan 7 koin membalik per giliran
Secara intuitif kita bisa mengatakan bahwa melempar dadu tujuh kali akan sangat menarik. Karena kita hanya perlu membuang 2 dari27 kemungkinan. Yakni, 7 kali head dan 0 kali head.
Untuk semua kemungkinan selalu ada kelipatan 7 kasus dengan jumlah kepala yang sama. Yaitu 7 kasus dengan 1 kepala, 21 kasus dengan 2 kepala, 35 kasus dengan 3 kepala, 35 kasus dengan 4 kepala, 21 kasus dengan 5 kepala, dan 7 kasus dengan 6 kepala.27−2
Jadi jika Anda menghitung angka (membuang 0 kepala dan 7 kepala)X=∑k=17(k−1)⋅Ck
dengan variabel terdistribusi Bernoulli (nilai 0 atau 1), maka X modulo 7 adalah variabel seragam dengan tujuh kemungkinan hasil.Ck
Membandingkan jumlah flips koin yang berbeda per giliran
Pertanyaannya adalah berapa jumlah gulungan optimal per giliran. Menggulirkan lebih banyak dadu per gilirannya akan membuat Anda lebih mahal, tetapi Anda mengurangi kemungkinan harus berguling lagi.
Gambar di bawah ini menunjukkan perhitungan manual untuk beberapa angka pertama flips koin per giliran. (mungkin mungkin ada solusi analitis, tapi saya yakin aman untuk mengatakan bahwa sistem dengan 7 membalik koin memberikan metode terbaik mengenai nilai ekspektasi untuk jumlah membalik koin yang diperlukan)
Menggunakan aturan penghentian awal
catatan: perhitungan di bawah ini, untuk nilai ekspektasi jumlah flips, adalah untuk koin yang adil , itu akan menjadi berantakan untuk melakukan hal ini untuk berbeda , tetapi prinsipnya tetap sama (meskipun pembukuan yang berbeda dari kasus diperlukan)p=0.5 p
Kita harus bisa memilih kasing (bukan rumus untuk ) sehingga kita bisa berhenti lebih awal.X
Dengan 5 koin membalik kita miliki untuk enam set kepala dan ekor yang tidak berurutan yang berbeda:
1 + 5 + 10 + 10 + 5 + 1 set yang dipesan
Dan kita dapat menggunakan kelompok dengan sepuluh kasus (yaitu kelompok dengan 2 kepala atau kelompok dengan 2 ekor) untuk memilih (dengan probabilitas yang sama) angka. Ini terjadi pada 14 dari 2 ^ 5 = 32 kasus. Ini membuat kita dengan:
1 + 5 + 3 + 3 + 5 + 1 set yang dipesan
Dengan flip koin ekstra (6-th) yang kami miliki untuk tujuh set kepala dan ekor unordered yang berbeda:
1 + 6 + 8 + 6 + 8 + 6 + 1 set yang dipesan
Dan kita dapat menggunakan kelompok dengan delapan kasus (yaitu kelompok dengan 3 kepala atau kelompok dengan 3 ekor) untuk memilih (dengan probabilitas yang sama) angka. Ini terjadi pada 14 dari 2 * (2 ^ 5-14) = 36 kasus. Ini membuat kita dengan:
1 + 6 + 1 + 6 + 1 + 6 + 1 set yang dipesan
Dengan flip koin ekstra lain (7-th) yang kami miliki untuk delapan set kepala dan ekor unordered yang berbeda:
1 + 7 + 7 + 7 + 7 + 7 + 7 + 1 set yang dipesan
Dan kita dapat menggunakan kelompok dengan tujuh kasus (semua kecuali semua ekor dan semua kasus kepala) untuk memilih (dengan probabilitas yang sama) angka. Ini terjadi pada 42 dari 44 kasus. Ini membuat kita dengan:
1 + 0 + 0 + 0 + 0 + 0 + 0 + 1 set pesanan
(kita bisa melanjutkan ini tetapi hanya pada langkah ke-49 hal ini memberi kita keuntungan)
Jadi probabilitas untuk memilih nomor
Ini membuat nilai ekspektasi untuk jumlah flips dalam satu giliran, dengan syarat bahwa ada keberhasilan dan p = 0,5:
Nilai ekspektasi untuk jumlah total flips (sampai ada keberhasilan), dengan syarat bahwa p = 0,5, menjadi:
Jawaban oleh NcAdams menggunakan variasi dari strategi stopping-rule ini (setiap kali menghasilkan dua flips koin baru) tetapi tidak secara optimal memilih semua flips.
Jawaban oleh Clid mungkin serupa juga walaupun mungkin ada aturan pemilihan yang tidak rata bahwa masing-masing dua koin membalik nomor mungkin dipilih tetapi tidak harus dengan probabilitas yang sama (perbedaan yang sedang diperbaiki selama membalik koin kemudian)
Perbandingan dengan metode lain
Metode lain yang menggunakan prinsip serupa adalah yang dilakukan oleh NcAdams dan AdamO.
Prinsipnya adalah : Keputusan untuk angka antara 1 dan 7 dibuat setelah sejumlah kepala dan ekor. Setelah jumlahx membalik, untuk setiap keputusan yang mengarah ke nomor i ada keputusan yang sama, kemungkinan sama, yang mengarah ke nomor j (jumlah kepala dan ekor yang sama tetapi hanya dalam urutan yang berbeda). Beberapa seri kepala dan ekor dapat mengarah pada keputusan untuk memulai kembali.
Untuk jenis metode seperti itu, yang ditempatkan di sini adalah yang paling efisien karena membuat keputusan sedini mungkin (segera setelah ada kemungkinan untuk 7 urutan probabilitas kepala dan ekor yang sama, setelah flip ke-x , kita dapat menggunakan mereka untuk membuat keputusan pada nomor dan kita tidak perlu membalik lebih jauh jika kita menemukan salah satu dari kasus-kasus itu).
Ini ditunjukkan oleh gambar dan simulasi di bawah ini:
gambar lain yang diskalakan denganp∗(1−p) untuk perbandingan yang lebih baik:
perbesar metode perbandingan yang dijelaskan dalam pos dan komentar ini
'lompatan bersyarat dari langkah ke-7' adalah sedikit perbaikan yang dapat dilakukan pada aturan penghentian awal. Dalam hal ini Anda memilih bukan grup dengan probabilitas yang sama setelah membalik ke-6. Anda memiliki 6 grup dengan probabilitas yang sama, dan 1 grup dengan probabilitas yang sedikit berbeda (untuk grup terakhir ini Anda perlu membalik satu kali lagi ketika Anda memiliki 6 kepala atau ekor dan karena Anda membuang 7 kepala atau 7 ekor, Anda akan berakhir setelah itu dengan probabilitas yang sama)
Ditulis oleh StackExchangeStrike
sumber
Bagilah kotak menjadi tujuh wilayah dengan luas yang sama, masing-masing diberi label dengan bilangan bulat. Lempar koin ke dalam kotak sedemikian rupa sehingga memiliki kemungkinan pendaratan yang sama di setiap wilayah.
sumber
0
, dan jika lemparan kedua melangkah lebih jauh itu adalah1
EDIT: berdasarkan umpan balik orang lain.
Inilah pemikiran yang menarik:
atur daftar {1,2,3,4,5,6,7}. Lempar koin untuk setiap elemen dalam daftar secara berurutan. Jika kepala mengarah ke atas untuk elemen tertentu, hapus nomor dari daftar. Jika semua angka dari iterasi tertentu dari daftar dihapus, ulangi pengambilan sampel. Lakukan sampai hanya satu nomor yang tersisa.
memberi saya distribusi sekitar seragam
Evaluasi nilai ekspektasi untuk jumlah lemparan koin
Solusi ditemukan dengan wxMaxima
Perhitungan dalam R
sumber
p <- 0.99
saya mendapatkan hasilnya0.89 0.02 0.02 0.02 0.02 0.02 0.02
Pertanyaannya agak ambigu, apakah ia bertanya "menghasilkan bilangan bulat acak sama atau kurang dari 7 dengan probabilitas sama", atau apakah ia bertanya "menghasilkan 7 bilangan bulat acak dengan probabilitas sama?" - tapi apa ruang bilangan bulat?!?
Saya akan berasumsi itu yang pertama, tetapi logika yang sama yang saya terapkan dapat diperluas ke kasus yang terakhir juga, setelah masalah itu diselesaikan.
Dengan koin bias, Anda dapat menghasilkan koin yang adil dengan mengikuti prosedur berikut: https://en.wikipedia.org/wiki/Fair_coin#Fair_results_from_a_ gantung_coin
Angka 7 atau kurang dapat ditulis dalam biner sebagai tiga {0,1} digit. Jadi yang perlu dilakukan adalah mengikuti prosedur di atas tiga kali, dan mengonversi angka biner yang dihasilkan menjadi desimal.
sumber
Sebuah solusi yang tidak pernah membuang membalik, yang banyak membantu untuk koin yang sangat bias.
Kerugian dari algoritma ini (seperti yang ditulis, setidaknya) adalah bahwa ia menggunakan aritmatika presisi arbitrer. Secara praktis, Anda mungkin ingin menggunakan ini sampai integer overflow, dan hanya kemudian membuangnya dan memulai lagi.
Juga, Anda perlu tahu apa bias adalah ... yang Anda mungkin tidak, katakanlah, jika suhu tergantung seperti fenomena fisik yang paling.
Dengan asumsi peluang kepala, katakanlah, 30%.
[1, 8)
.[1, 3.1)
. Lain, gunakan 70% yang tepat, jadi rentang baru Anda[3.1, 8)
.Kode lengkap:
sumber
diff *= 7
saya pikirkan ... pada kenyataannya, tidak ada kebutuhan khusus untuk menggunakan basis yang sama untuk setiap upaya.Seperti disebutkan dalam komentar sebelumnya, teka-teki ini berkaitan dengan makalah John von Neumann tahun 1951 "Berbagai Teknik yang Digunakan Sehubungan dengan Digit Acak" yang diterbitkan dalam jurnal penelitian National Bureau of Standards:
sumber
Kami pertama-tama mengubah (mungkin) koin yang tidak adil menjadi koin yang adil menggunakan proses dari jawaban NcAdams :
H1
T1
0.
H1 H1 T1
sumber
Terinspirasi oleh jawaban AdamO, berikut adalah solusi Python yang menghindari bias:
Ada dua perubahan utama di sini: Yang utama adalah jika semua nomor dibuang dalam satu putaran, ulangi putaran itu. Saya juga membalik pilihan apakah kepala atau ekor berarti membuang setiap waktu. Ini mengurangi jumlah flips yang dibutuhkan dalam kasus di mana p mendekati 0 atau 1 hingga ~ 70% ketika p = 0,999
sumber
Tampaknya kita diizinkan untuk mengubah pemetaan hasil setiap flip, setiap kali kita flip . Jadi, untuk kenyamanan tujuh bilangan bulat positif pertama, kami memberikan perintah berikut:
dll
Hitungan flips yang tidak berguna di sini akan cenderung
sumber