Jak mogę modelować flipy, dopóki N nie odniesie sukcesu?

Ty i ja decydujemy się zagrać w grę, w której na zmianę podrzucamy monetę. Pierwszy gracz, który rzuci łącznie 10 głów, wygrywa. Oczywiście istnieje spór o to, kto powinien iść pierwszy.

Symulacje tej gry pokazują, że gracz, który przerzuca pierwszy, wygrywa o 6% więcej niż gracz, który przerzuca drugi (pierwszy gracz wygrywa przez około 53% czasu). Jestem zainteresowany modelowaniem tego w sposób analityczny.

To nie jest losowa zmienna dwumianowa, ponieważ nie ma ustalonej liczby prób (odwróć, aż ktoś zdobędzie 10 głów). Jak mogę to wymodelować? Czy to ujemny rozkład dwumianowy?

Aby móc odtworzyć moje wyniki, oto mój kod python:

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)

Rozkład liczby ogony przed osiągnięciem głowic ujemna dwumianowego parametrów 10 i 1 / 2 . Niech f będzie funkcją prawdopodobieństwa, a G funkcją przetrwania: dla każdego n ≥ 0 , f ( n ) oznacza szansę gracza na n- ogona przed 10 główami, a G ( n ) oznacza szansę gracza na n lub więcej ogonów przed 10 głowami.$10$$10$$1/2$$f$$G$$n\ge 0$$f(n)$$n$$10$$G(n)$$n$$10$

Ponieważ gracze rzucają niezależnie, szansę, którą pierwszy gracz wygrywa, rzucając dokładnie ogonami, uzyskuje się, mnożąc tę ​​szansę przez szansę, że drugi gracz rzuca n lub więcej ogonami, równą f ( n ) G ( n ) .$n$$n$$f(n)G(n)$

Zsumowanie wszystkich możliwych daje szanse wygranej pierwszego gracza jako$n$

To około więcej niż połowa czasu.$3\%$

Zasadniczo, zastępując dowolną dodatnią liczbą całkowitą m , odpowiedź można podać w kategoriach funkcji hipergeometrycznej: jest równa$10$$m$

Gdy używa się stronniczej monety z szansą głów, uogólnia się na$p$

Oto Rsymulacja miliona takich gier. Podaje szacunkową wartość . Dwumianowy test hipotezy, aby porównać go z wynikiem teoretycznym, ma wynik Z wynoszący - 0,843 , co jest nieznaczną różnicą.$0.5325$$-0.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))

Możemy wymodelować grę w następujący sposób:

• Gracz A wielokrotnie rzuca monetą, uzyskując wyniki $A_1, A_2, \dots$ aż do uzyskania łącznie 10 głów. Niech indeks czasu z szefów 10th być zmienna losowa $X$ .
• Gracz B robi to samo. Niech indeks czasu z szefów 10th być zmienna losowa $Y$ , który jest iid kopia $X$ .
• Jeśli $X \le Y$ , Gracz A wygrywa; w przeciwnym razie Gracz B wygrywa. Oznacza to, że $$\begin{align} \Pr(A\text{ wins})&= \Pr(X \ge Y) = \Pr(X > Y) + \Pr(X = Y)\\ \Pr(B\text{ wins})&= \Pr(Y > X) = \Pr(X > Y). \end{align}$$

Różnica w stawkach wygranych wynosi zatem

Jak podejrzewasz, $X$ (i $Y$ ) są rozmieszczone zasadniczo zgodnie z ujemnym rozkładem dwumianowym. Oznaczenia tego są różne, ale w parametryzacji Wikipedii mamy głowy jako „porażkę”, a ogony jako „sukces”; potrzebujemy $r = 10$ „awarii” (głów), zanim eksperyment zostanie zatrzymany, a prawdopodobieństwo sukcesu $p = \tfrac12$ . Wtedy liczba „sukcesów”, która wynosi$X - 10$, ma

Tak więc wskaźnik wygranych Gracza B wynosi $\Pr(Y > X) \approx 46.7\%$ , a Gracza A wynosi $\frac{619\,380\,496}{1\,162\,261\,467} \approx 53.3\%$

Let $E_{ij}$ be the event that the player on roll flips i heads before the other player flips j heads, and let $X$ be the first two flips having sample space $\{ hh,ht,th,tt\}$ where h means heads and t tails, and let $p_{ij} \equiv Pr(E_{ij})$.

Then $p_{ij}=Pr(E_{i-1j-1}|X=hh)*Pr(X=hh)+Pr(E_{i-1j}|X=ht)*Pr(X=ht)+Pr(E_{ij-1}|X=th)*Pr(X=th)+Pr(E_{ij}|X=tt)*Pr(X=tt)$

Assuming a standard coin $Pr(X=*)=1/4$ means that $p_{ij}=1/4*[p_{i-1j-1}+p_{i-1j}+p_{ij-1}+p_{ij}]$

solving for $p_{ij}$, $= 1/3*[p_{i-1j-1}+p_{i-1j}+p_{ij-1}]$

But $p_{0j}=p_{00}=1$ and $p_{i0}=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(i*j)$ 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 $E_{kl}$ 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, $p_{k,l} = 1-1/2*[p_{l,k+1}+p_{l,0}]$ where $p_{il}=p_{ii}=1, p_{ki}=0$

This is a linear system with $i^2$ unknowns and one unique solution.

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

$p_{k,l,n+1} = 1/(1+\epsilon)*[\epsilon*p_{k,l,n} +1-1/2*(p_{l,k+1,n}+p_{l,0,n})]$

Choose $\epsilon$ and $p_{k,l,0}$ wisely and run the iteration for a few steps and monitor the correction term.