Saya baru saja memainkan permainan dengan anak-anak saya yang pada dasarnya bermuara pada: siapa pun yang menggulung setiap angka setidaknya sekali pada die 6-sisi menang.
Saya menang, akhirnya, dan yang lainnya selesai 1-2 putaran kemudian. Sekarang saya bertanya-tanya: apa harapan dari panjang permainan?
Saya tahu bahwa harapan jumlah gulungan sampai Anda menekan angka tertentu adalah .
Namun, saya punya dua pertanyaan:
- Berapa kali Anda harus melempar dadu enam sisi sampai Anda mendapatkan setiap angka setidaknya satu kali?
- Di antara empat uji coba independen (yaitu dengan empat pemain), apa yang diharapkan dari jumlah maksimum gulungan yang dibutuhkan? [catatan: maksimum, bukan minimum, karena pada usia mereka, ini lebih tentang menyelesaikan daripada tentang pergi ke sana dulu untuk anak-anak saya]
Saya dapat mensimulasikan hasilnya, tetapi saya ingin tahu bagaimana cara menghitungnya secara analitis.
Berikut ini adalah simulasi Monte Carlo di Matlab
mx=zeros(1000000,1);
for i=1:1000000,
%# assume it's never going to take us >100 rolls
r=randi(6,100,1);
%# since R2013a, unique returns the first occurrence
%# for earlier versions, take the minimum of x
%# and subtract it from the total array length
[~,x]=unique(r);
mx(i,1)=max(x);
end
%# make sure we haven't violated an assumption
assert(numel(x)==6)
%# find the expected value for the coupon collector problem
expectationForOneRun = mean(mx)
%# find the expected number of rolls as a maximum of four independent players
maxExpectationForFourRuns = mean( max( reshape( mx, 4, []), [], 1) )
expectationForOneRun =
14.7014 (SEM 0.006)
maxExpectationForFourRuns =
21.4815 (SEM 0.01)
Jawaban:
Karena "pendekatan yang sepenuhnya analitis" telah diminta, berikut ini adalah solusi tepat. Ini juga menyediakan pendekatan alternatif untuk memecahkan pertanyaan di Probability untuk menggambar bola hitam dalam satu set bola hitam dan putih dengan kondisi penggantian campuran .
Jumlah bergerak di game,X , dapat dimodelkan sebagai jumlah dari enam realisasi independen Geometric (p) variabel dengan probabilitas p=1,5/6,4/6,3/6,2/6,1/6 , masing-masing bergeser 1 (karena variabel geometrik hanya menghitung gulungan sebelumnya)sukses dan kita juga harus menghitung daftar yang mencatat keberhasilan). Dengan menghitung dengan distribusi geometris, kami akan karena itu mendapatkan jawaban yang 6 kurang dari yang diinginkan dan karena itu harus pastikan untuk menambahkan 6 kembali di akhir.
The fungsi pembangkit probabilitas (PGF) dari seperti variabel geometris dengan parameterp adalah
Oleh karena itu pgf untuk jumlah enam variabel ini adalah
(Produk dapat dihitung dalam bentuk tertutup ini dengan memisahkannya menjadi lima istilah melalui fraksi parsial.)
(Saya telah menulis ungkapan ini dalam bentuk yang menyarankan derivasi alternatif melalui Prinsip Inklusi-Pengecualian.)
Dari ini kita mendapatkan jumlah gerakan yang diharapkan dalam game (menjawab pertanyaan pertama) sebagai
sumber
Dengan Python:
sumber
Perkiraan cepat dan kotor Monte Carlo dalam R dari panjang permainan untuk 1 pemain:
Untuk menentukan panjang permainan empat pemain, kita dapat mengelompokkan sampel menjadi empat dan mengambil panjang minimum rata-rata di atas masing-masing kelompok (Anda bertanya tentang maksimum, tetapi saya menganggap Anda berarti minimum karena, cara saya membacanya, permainan berakhir ketika seseorang berhasil mendapatkan semua angka):
sumber
sumber
Penjelasan sederhana dan intuitif untuk pertanyaan pertama:
Pertama-tama Anda harus memutar nomor apa pun. Ini mudah, itu akan selalu memakan waktu tepat 1 roll.
Dan seterusnya sampai kami berhasil menyelesaikan roll ke-6 kami:
Jawaban ini mirip dengan jawaban Neil G, hanya saja, tanpa rantai markov.
sumber
fungsi kepadatan probabilitas (atau yang setara diskrit) untuk mendapatkan nomor baru berikutnya adalah:
f = jumlah (p * (1 - p) ^ (i - 1), i = 1 .. inf)
di mana p adalah probabilitas per roll, 1 ketika tidak ada nomor yang telah digulung, 5/6 setelah 1, 4/6 .. turun ke 1/6 untuk nomor terakhir
nilai yang diharapkan, mu = jumlah (i * p * (1 - p) ^ (i - 1), i = 1 .. inf) membiarkan n = i - 1, dan membawa p di luar penjumlahan,
mu = p * jumlah ((n + 1) * (1 - p) ^ n, n = 0 .. inf)
mu = p * jumlah (n (1-p) ^ n, n = 0 .. inf) + p * jumlah ((1-p) ^ n, n = 0 .. inf) mu = p * (1-p ) / (1-p-1) ^ 2 + p * 1 / (1- (1-p))
mu = p * (1 - p) / p ^ 2 + p / p
mu = (1 - p) / p + p / p
mu = (1 - p + p) / p
mu = 1 / p
Jumlah nilai yang diharapkan (mus) untuk ps dari 1, 5/6, 4/6, 3/6, 2/6, dan 1/6 adalah 14,7 seperti yang dilaporkan sebelumnya, tetapi 1 / p per angka yang diperlukan bersifat umum terlepas dari ukuran die
sama halnya, kita dapat menghitung standar deviasi secara analitis
sigma ^ 2 = jumlah ((i - mu) ^ 2 * p * (1 - p) ^ (i - 1), i = 1 .. inf)
Saya akan memberikan Anda aljabar di sini, tetapi sigma ^ 2 = (1-p) / p ^ 2
Dalam kasus 6, jumlah sigma ^ 2 untuk setiap langkah adalah 38,99 untuk standar deviasi sekitar 6,24, sekali lagi, seperti yang disimulasikan
sumber
Pertanyaan 1 adalah:
Berapa kali Anda harus melempar dadu enam sisi sampai Anda mendapatkan setiap nomor setidaknya satu kali?
Jelas, jawaban yang benar harus 'tidak terbatas'.
sumber