Anda dan saya memutuskan untuk memainkan permainan di mana kami bergiliran membalik koin. Pemain pertama yang membalikkan 10 kepala total memenangkan permainan. Tentu saja, ada argumen tentang siapa yang harus pergi dulu.
Simulasi permainan ini menunjukkan bahwa pemain yang membalik pertama menang 6% lebih banyak daripada pemain yang membalik kedua (pemain pertama menang kira-kira 53% dari waktu). Saya tertarik untuk memodelkan ini secara analitis.
Ini bukan variabel acak binomial, karena tidak ada jumlah percobaan tetap (balik sampai seseorang mendapatkan 10 kepala). Bagaimana saya bisa memodelkan ini? Apakah ini distribusi binomial negatif?
Agar dapat membuat ulang hasil saya, berikut adalah kode python saya:
import numpy as np
from numba import jit
@jit
def sim(N):
P1_wins = 0
P2_wins = 0
for i in range(N):
P1_heads = 0
P2_heads = 0
while True:
P1_heads += np.random.randint(0,2)
if P1_heads == 10:
P1_wins+=1
break
P2_heads+= np.random.randint(0,2)
if P2_heads==10:
P2_wins+=1
break
return P1_wins/N, P2_wins/N
a,b = sim(1000000)
probability
python
binomial
negative-binomial
Pisang Demetri
sumber
sumber
Jawaban:
Distribusi jumlah ekor sebelum mencapai kepala adalah negatif Binomial dengan parameter 10 dan 1 / 2 . Biarkan f menjadi fungsi probabilitas dan G fungsi bertahan hidup: untuk setiap n ≥ 0 , f ( n ) adalah peluang pemain untuk n ekor sebelum 10 kepala dan G ( n ) adalah peluang pemain untuk n atau lebih banyak ekor sebelum 10 kepala.10 10 1/2 f G n≥0 f(n) n 10 G(n) n 10
Karena para pemain berguling secara independen, peluang pemain pertama menang dengan menggulirkan tepat ekor diperoleh dengan mengalikan peluang itu dengan kesempatan pemain kedua menggulir n atau lebih, sama dengan f ( n ) G ( n ) .n n f(n)G(n)
Menjumlahkan semua kemungkinan memberikan peluang kemenangan pemain pertama sebagain
Itu sekitar lebih dari separuh waktu.3%
Secara umum, mengganti10 dengan bilangan bulat positif , jawabannya dapat diberikan dalam hal fungsi Hypergeometric: sama denganm
Saat menggunakan koin bias dengan kesempatan kepala, ini digeneralisasi kep
Berikut ini adalah0.5325 −0.843
R
simulasi dari sejuta game semacam itu. Ini melaporkan perkiraan . Uji hipotesis binomial untuk membandingkannya dengan hasil teoretis memiliki skor-Z sebesar - 0,843 , yang merupakan perbedaan yang tidak signifikan.sumber
Kami dapat memodelkan game seperti ini:
Kesenjangan dalam tingkat kemenangan demikianPr(X=Y)=∑kPr(X=k,Y=k)=∑kPr(X=k)2.
Seperti yang Anda duga,X (dan Y ) didistribusikan pada dasarnya sesuai dengan distribusi binomial negatif. Notasi untuk ini berbeda-beda, tetapi dalam parameterisasi Wikipedia , kami memiliki kepala sebagai "kegagalan" dan berbuntut sebagai "sukses"; kita perlu r=10 "kegagalan" (kepala) sebelum percobaan dihentikan, dan probabilitas keberhasilan p=12 . Maka jumlah "sukses", yaituX−10 , memilikiPr(X−10=k)=(k+9k)2−10−k,
dan probabilitas tabrakan adalah
Pr(X=Y)=∑k=0∞(k+9k)22−2k−20,
yang dikatakan oleh Mathematica adalah764995251162261467≈6.6% .
Dengan demikian tingkat kemenangan Pemain B adalahPr(Y>X)≈46.7% , dan Pemain A adalah 6193804961162261467≈53.3% .
sumber
MariEij menjadi peristiwa yang pemain di roll membalik kepala saya sebelum pemain lain membalik kepala j, dan membiarkan X menjadi yang pertama dua membalik memiliki ruang sampel {hh,ht,th,tt} di mana h berarti kepala dan t ekor, dan biarkan pij≡Pr(Eij) .
Kemudianpij=Pr(Ei−1j−1|X=hh)∗Pr(X=hh)+Pr(Ei−1j|X=ht)∗Pr(X=ht)+Pr(Eij−1|X=th)∗Pr(X=th)+Pr(Eij|X=tt)∗Pr(X=tt)
Butp0j=p00=1 and pi0=0 , implying that the recursion fully terminates. However, a direct naive recursive implementation will yield poor performance because the branches intersect.
An efficient implementation will have complexityO(i∗j) and memory complexity O(min(i,j)) . Here's a simple fold implemented in Haskell:
UPDATE: Someone in the comments above asked whether one was suppose to roll 10 heads in a row or not. So letEkl be the event that the player on roll flips i heads in a row before the other player flips i heads in a row, given that they already flipped k and l consecutive heads respectively.
Proceeding as before above, but this time conditioning on the first flip only,pk,l=1−1/2∗[pl,k+1+pl,0] where pil=pii=1,pki=0
This is a linear system withi2 unknowns and one unique solution.
To convert it into an iterative scheme, simply add an iterate numbern and a sensitivity factor ϵ :
Chooseϵ and pk,l,0 wisely and run the iteration for a few steps and monitor the correction term.
sumber