Bagaimana saya bisa memodelkan membalik sampai N berhasil?

17

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)
Pisang Demetri
sumber
3
Saat Anda melempar koin hingga r gagal dan kemudian melihat distribusi jumlah keberhasilan yang terjadi sebelum menyelesaikan percobaan tersebut, maka ini adalah distribusi binomial negatif .
Tim
2
Saya tidak dapat mereproduksi nilai 2%. Saya menemukan bahwa pemain pertama menang 53.290977425133892% waktu.
whuber
1
@whuber ya, saya yakin Anda benar. Saya menjalankan simulasi saya lebih sedikit dari yang seharusnya. Hasil saya sepadan dengan Anda.
Demetri Pananos
1
Jika satu menang 53% dari waktu, yang lain harus 47%, jadi bukankah seharusnya deskripsi berbunyi "pemain pertama menang 6% lebih dari pemain kedua," atau "3% lebih dari separuh waktu"? Tidak (seperti yang dikatakan saat ini) "3% lebih tinggi dari pemain yang membalik kedua"
JesseM
3
Apakah Anda mendapatkan pertanyaan ini dari FiveThirtyEight Riddler Express ?
foutandabout

Jawaban:

19

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.10101/2fGn0f(n)n10G(n)n10

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 ) .nnf(n)G(n)

Menjumlahkan semua kemungkinan memberikan peluang kemenangan pemain pertama sebagain

n=0f(n)G(n)53.290977425133892%.

Itu sekitar lebih dari separuh waktu.3%

Secara umum, mengganti 10 dengan bilangan bulat positif , jawabannya dapat diberikan dalam hal fungsi Hypergeometric: sama denganm

1/2+22m12F1(m,m,1,1/4).

Saat menggunakan koin bias dengan kesempatan kepala, ini digeneralisasi kep

12+12(p2m)2F1(m,m,1,(1p)2).

Berikut ini adalah Rsimulasi 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.0.53250.843

n.sim <- 1e6
set.seed(17)
xy <- matrix(rnbinom(2*n.sim, 10, 1/2), nrow=2)
p <- mean(xy[1,] <= xy[2,])
cat("Estimate:", signif(p, 4), 
    "Z-score:", signif((p - 0.532909774) / sqrt(p*(1-p)) * sqrt(n.sim), 3))
whuber
sumber
1
Sama seperti catatan yang mungkin tidak jelas sekilas, jawaban kami setuju secara numerik: (.53290977425133892 - .5) * 2 pada dasarnya persis seperti probabilitas yang saya berikan.
Dougal
1
@Dougal Terima kasih telah menunjukkan itu. Saya melihat jawaban Anda, melihat , dan mengetahui bahwa itu tidak setuju dengan bentuk jawaban yang diminta dalam pertanyaan, saya tidak menyadari bahwa Anda telah menghitung dengan benar. Secara umum itu ide yang baik untuk membingkai jawaban atas pertanyaan dalam bentuk yang diminta, jika mungkin: yang membuatnya mudah dikenali ketika itu benar dan mudah untuk membandingkan jawaban. 6.6%
whuber
1
@whuber saya merespons frasa "Simulasi permainan ini menunjukkan bahwa pemain yang membalik pertama menang 2% (EDIT: 3% lebih banyak setelah mensimulasikan lebih banyak permainan) lebih banyak daripada pemain yang membalik kedua". Saya akan mengartikan "menang 2% lebih banyak" sebagai ; nilai yang benar memang 6,6%. Saya tidak yakin cara untuk menafsirkan "menang 2% lebih banyak" berarti "menang 52% dari waktu", meskipun tampaknya itulah yang dimaksudkan. Pr(A wins)Pr(B wins)=2%
Dougal
@Dougal Saya setuju bahwa deskripsi OP membingungkan dan bahkan salah. Namun, kode dan hasilnya menegaskan bahwa yang ia maksudkan adalah "3% lebih dari separuh waktu" daripada "3% lebih dari pemain lain."
whuber
1
@whuber Setuju. Sayangnya, saya menjawab pertanyaan sebelum kode diposting, dan tidak menjalankan simulasi sendiri. :)
Dougal
15

Kami dapat memodelkan game seperti ini:

  • Pemain A membalik koin berulang kali, mendapatkan hasil A1,A2, sampai mereka mendapatkan total 10 kepala. Biarkan indeks waktu dari kepala ke-10 menjadi variabel acak X .
  • Pemain B melakukan hal yang sama. Biarkan indeks waktu dari kepala ke-10 menjadi variabel acak Y , yang merupakan salinan X dari X .
  • Jika XY , Pemain A menang; jika tidak, Pemain B menang. Yaitu,
    Pr(A wins)=Pr(XY)=Pr(X>Y)+Pr(X=Y)Pr(B wins)=Pr(Y>X)=Pr(X>Y).

Kesenjangan dalam tingkat kemenangan demikian

Pr(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", yaituX10, memiliki

Pr(X10=k)=(k+9k)210k,
dan probabilitas tabrakan adalah
Pr(X=Y)=k=0(k+9k)222k20,
yang dikatakan oleh Mathematica adalah7649952511622614676.6%.

Dengan demikian tingkat kemenangan Pemain B adalah Pr(Y>X)46.7% , dan Pemain A adalah 619380496116226146753.3%.

Dougal
sumber
kepala tidak harus berturut-turut, hanya 10 total. Saya berasumsi bahwa itulah yang Anda perbaiki.
Demetri Pananos
6
(+1) Saya menyukai pendekatan ini lebih baik daripada yang saya posting karena secara komputasi lebih sederhana: hanya membutuhkan fungsi probabilitas, yang memiliki ekspresi sederhana dalam hal koefisien binomial.
whuber
1
Saya telah mengirimkan suntingan menggantikan paragraf terakhir yang mempertanyakan perbedaan dari jawaban yang lain dengan penjelasan tentang bagaimana hasil mereka sebenarnya sama.
Monty Harder
1

Mari Eij 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 pijPr(Eij) .

Kemudian pij=Pr(Ei1j1|X=hh)Pr(X=hh)+Pr(Ei1j|X=ht)Pr(X=ht)+Pr(Eij1|X=th)Pr(X=th)+Pr(Eij|X=tt)Pr(X=tt)

Pr(X=)=1/4pij=1/4[pi1j1+pi1j+pij1+pij]

pij=1/3[pi1j1+pi1j+pij1]

But p0j=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 complexity O(ij) and memory complexity O(min(i,j)). Here's a simple fold implemented in Haskell:

Prelude> let p i j = last. head. drop j $ iterate ((1:).(f 1)) start where
  start = 1 : replicate i 0;
  f c v = case v of (a:[]) -> [];
                    (a:b:rest) -> sum : f sum (b:rest) where
                     sum = (a+b+c)/3 
Prelude> p 0 0
1.0
Prelude> p 1 0
0.0
Prelude> p 10 10
0.5329097742513388
Prelude> 

UPDATE: Someone in the comments above asked whether one was suppose to roll 10 heads in a row or not. So let Ekl 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=11/2[pl,k+1+pl,0] where pil=pii=1,pki=0

This is a linear system with i2 unknowns and one unique solution.

To convert it into an iterative scheme, simply add an iterate number n and a sensitivity factor ϵ:

pk,l,n+1=1/(1+ϵ)[ϵpk,l,n+11/2(pl,k+1,n+pl,0,n)]

Choose ϵ and pk,l,0 wisely and run the iteration for a few steps and monitor the correction term.

John Rambo
sumber