Seberapa sering Anda harus melempar dadu 6 sisi untuk mendapatkan setiap angka setidaknya satu kali?

41

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 n=1n16(56)n1=6.

Namun, saya punya dua pertanyaan:

  1. Berapa kali Anda harus melempar dadu enam sisi sampai Anda mendapatkan setiap angka setidaknya satu kali?
  2. 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)
Jonas
sumber
11
Masalah pengumpul Kupon juga lihat - googling akan memberi Anda lebih banyak klik dan lebih banyak info. Coba juga cari di sini di stats.SE .
Glen_b
1
@ Glen_b: Terima kasih, saya tidak tahu nama itu!
Jonas
1
@whuber: Saya tidak yakin pertanyaan ini seharusnya ditutup. Dia menginginkan waktu memukul minimum yang diharapkan dari empat percobaan. Saya baru saja akan memperbaiki jawaban saya untuk solusi pemrograman dinamis.
Neil G
2
@whuber: Saya akan mengedit posting saya untuk memperjelas
Jonas
3
Math.SE post yang relevan: Distribusi probabilitas dalam masalah pengumpul kupon
Glen_b

Jawaban:

22

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 parameter p adalah

f(z,p)=p1(1p)z.

Oleh karena itu pgf untuk jumlah enam variabel ini adalah

g(z)=i=16f(z,i/6)=6z4(5 2z+5+10 3z+45 4z+4+5z+4+5).

(Produk dapat dihitung dalam bentuk tertutup ini dengan memisahkannya menjadi lima istilah melalui fraksi parsial.)

gz

F(z)=6z4((1) 1z+4+(5) 2z+4(10) 3z+4+(10) 4z+4(5) 5z+4+(1) 6z+4).

(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

E(6+X)=6+i=1(1F(i))=14710.

mXF(z)mm=4

6+i=1(1F(i)4)21.4820363.

6.77108.6

Angka

18500.3%

whuber
sumber
Metode solusi ini terinspirasi oleh pengamatan bahwa jumlah variabel geometrik adalah campuran (mungkin dengan bobot negatif) variabel geometrik yang memiliki parameter yang sama. Hubungan yang sama berlaku di antara variabel Gamma (dengan parameter laju berbeda). Saya minta maaf karena melakukan pekerjaan di Mathematica, tapi saya yakin Matlab dapat melakukan perhitungan ini juga :-).
whuber
2
Ini adalah jawaban yang saya harapkan. Terima kasih banyak! Saya pikir saya harus dapat menghitung hasil numerik di Matlab :)
Jonas
f(z,p)=p1(1p)zi=16f(z,i/6)F(z)g(z)
1
f(z,p)
@ MartijnWeterings Terima kasih - Saya percaya itu adalah istilah yang lebih akurat dan konvensional. (Bisa dibilang saya cenderung menganggap PMF dan pgf sebagai hal yang hampir sama, karena kebiasaan lama menggunakan fungsi pembangkit.) Saya akan mengubah terminologi dalam posting ini.
whuber
13

{0,,6}ii6ii+16i6

i=0566i=14.7

(6,6,6,6)jiTiijpipijij. Anda dapat menemukan waktu dan probabilitas memukul dengan pemrograman dinamis. Ini tidak begitu sulit karena ada perintah traversal untuk mengisi waktu dan probabilitas memukul. Misalnya, untuk dua dadu: pertama hitung T dan p untuk (0,0), lalu untuk (1,0), lalu (1, 1), (2, 0), lalu (2, 1), dll.

Dengan Python:

import numpy as np
import itertools as it
from tools.decorator import memoized  # A standard memoization decorator

SIDES = 6

@memoized
def get_t_and_p(state):
    if all(s == 0 for s in state):
        return 0, 1.0
    n = len(state)
    choices = [[s - 1, s] if s > 0 else [s]
               for s in state]
    ts = []
    ps = []
    for last_state in it.product(*choices):
        if last_state == state:
            continue
        last_t, last_p = get_t_and_p(tuple(sorted(last_state)))
        if last_p == 0.0:
            continue
        transition_p = 1.0
        stay_p = 1.0
        for ls, s in zip(last_state, state):
            if ls < s:
                transition_p *= (SIDES - ls) / SIDES
            else:
                transition_p *= ls / SIDES
            stay_p *= ls / SIDES
        if transition_p == 0.0:
            continue
        transition_time = 1 / (1 - stay_p)
        ts.append(last_t + transition_time)
        ps.append(last_p * transition_p / (1 - stay_p))
    if len(ts) == 0:
        return 0, 0.0
    t = np.average(ts, weights=ps)
    p = sum(ps)
    return t, p

print(get_t_and_p((SIDES,) * 4)[0])
Neil G
sumber
1
Anda telah melewatkan jumlah maksimum gulungan dalam empat repetisi independen dari permainan.
probabilityislogic
Ah, aku baru sadar. Saya pikir maksud Anda minimum, tapi ya.
Neil G
@ NeilG: Sebenarnya saya maksudkan maksimum (lihat pertanyaan saya yang diperbarui), meskipun saya berasumsi bahwa strateginya sama untuk min dan maks. Bisakah Anda menguraikan strategi pemrograman dinamis?
Jonas
@Jonas: diperbarui untuk maksimum. Saya punya banyak pekerjaan, tetapi saya mungkin bisa membuat kode ini untuk Anda nanti.
Neil G
2
@ NeilG: Terima kasih. Saya berharap untuk mendapatkan pendekatan analitis sepenuhnya, tetapi kode DP cukup instruksional juga.
Jonas
6

Perkiraan cepat dan kotor Monte Carlo dalam R dari panjang permainan untuk 1 pemain:

N = 1e5
sample_length = function(n) { # random game length
    x = numeric(0)
    while(length(unique(x)) < n) x[length(x)+1] = sample(1:n,1)
    return(length(x))
}
game_lengths = replicate(N, sample_length(6))

μ^=14.684σ^=6.24[14.645,14.722]

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

grouped_lengths = matrix(game_lengths, ncol=4)
min_lengths = apply(grouped_lengths, 1, min)

μ^=9.44σ^=2.26[9.411,9.468]

bnaul
sumber
1
Saya sampai pada hasil yang sangat mirip dengan simulasi Matlab, tetapi saya ingin tahu bagaimana saya akan menyelesaikan ini secara analitis. Juga, karena saya bermain dengan anak-anak saya, mereka semua ingin menyelesaikan permainan, terlepas dari siapa yang menang, jadi saya ingin bertanya tentang maksimum.
Jonas
5

m

T1=6
Tm=1+6m6Tm+m6Tm1

m1

  • Tm6m6m6
  • Tm1mm6

14.7

ThePawn
sumber
Ti=Ti1+66i+1
1
Ya maaf membuat kesalahan, saya memperbaikinya
ThePawn
Saya harap Anda tidak keberatan bahwa saya menambahkan jawaban. 14.7 benar, tetapi hubungan perulangan masih cacat ...
Neil G
Tidak masalah, harus hati-hati pertama kali :). Jawaban Anda bagus.
ThePawn
5

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.

5665

4664

3663

Dan seterusnya sampai kami berhasil menyelesaikan roll ke-6 kami:

66+65+64+63+62+61=14.7 rolls

Jawaban ini mirip dengan jawaban Neil G, hanya saja, tanpa rantai markov.


sumber
1

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

MikeP
sumber
-4

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'.

Stef van Buuren
sumber
6
Itu akan menjawab pertanyaan 'untuk menjamin dengan kepastian mutlak untuk mendapatkan setiap nomor setidaknya satu kali'. Untuk pertanyaan yang diajukan, jawabannya adalah variabel acak, distribusinya dapat diperkirakan dengan baik.
Glen_b