Wie kann ich Flips modellieren, bis N Erfolge erzielt wurden?

Sie und ich beschließen, ein Spiel zu spielen, bei dem wir abwechselnd eine Münze werfen. Der erste Spieler, der insgesamt 10 Köpfe umdreht, gewinnt das Spiel. Natürlich gibt es einen Streit darüber, wer zuerst gehen sollte.

Simulationen dieses Spiels zeigen, dass der Spieler, der zuerst flippt, 6% mehr gewinnt als der Spieler, der als Zweiter flippt (der erste Spieler gewinnt ca. 53% der Zeit). Ich bin daran interessiert, dies analytisch zu modellieren.

Dies ist keine binomische Zufallsvariable, da es keine feste Anzahl von Versuchen gibt (drehen, bis jemand 10 Köpfe bekommt). Wie kann ich das modellieren? Ist es die negative Binomialverteilung?

Um meine Ergebnisse neu erstellen zu können, ist hier mein Python-Code:

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)

Die Verteilung der Anzahl der Schwänze vor Erreichen von Köpfen ist Negativbinomial mit den Parametern und . Sei die Wahrscheinlichkeitsfunktion und die Überlebensfunktion: Für jedes ist die Chance des Spielers, Schwänze vor Köpfen zu haben, und die Chance des Spielers, oder mehr Schwänze vor Köpfen zu haben .10 1 / 2 f G n ≥ 0 f ( n ) n 10 G ( n ) , n $10$$10$$1/2$$f$$G$$n\ge 0$$f(n)$$n$$10$$G(n)$$n$$10$

Da die Spieler unabhängig würfeln, wird die Chance, dass der erste Spieler gewinnt , wenn er genau Schwänze würfelt, durch Multiplizieren dieser Chance mit der Chance, dass der zweite Spieler oder mehr Schwänze würfelt , gleich .n f ( n ) G ( n $n$$n$$f(n)G(n)$

Das Summieren aller möglichen ergibt die Gewinnchancen des ersten Spielers als$n$

Das sind ungefähr mehr als die Hälfte der Zeit.$3\%$

Im Allgemeinen kann die Antwort durch Ersetzen von durch eine positive ganze Zahl in Form einer hypergeometrischen Funktion angegeben werden: Sie ist gleich$10$$m$

Bei Verwendung einer voreingenommenen Münze mit einer Wahrscheinlichkeit von Köpfen verallgemeinert sich dies auf$p$

Hier ist eine RSimulation von einer Million solcher Spiele. Es gibt eine Schätzung von . Ein Binomialhypothesentest zum Vergleich mit dem theoretischen Ergebnis weist einen Z-Score von , was einen unbedeutenden Unterschied darstellt.- $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))

Wir können das Spiel so modellieren:

• Spieler A wirft wiederholt eine Münze und erhält die Ergebnisse $A_1, A_2, \dots$ bis er insgesamt 10 Köpfe hat. Lassen Sie den Zeitindex der 10. Köpfe der Zufallsvariable $X$ .
• Spieler B macht das Gleiche. Der Zeitindex der 10. Köpfe sei die Zufallsvariable $Y$ , die eine iid-Kopie von $X$ .
• Wenn $X \le Y$ , gewinnt Spieler A; ansonsten gewinnt Spieler B. Das heißt, $$\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}$$

Die Lücke in den Gewinnraten ist somit

Wie Sie vermutet haben, werden $X$ (und ) im Wesentlichen gemäß einer negativen Binomialverteilung verteilt. Notationen dafür variieren, aber in der Parametrisierung von Wikipedia haben wir Köpfe als "Fehler" und Schwänze als "Erfolg"; wir brauchen r = 10 "Fehler" (Köpfe), bevor das Experiment gestoppt wird, und die Erfolgswahrscheinlichkeit p = 1$Y$$r = 10$$p = \tfrac12$ . Dann hat die Anzahl der "Erfolge", die$X - 10$ist, und die Kollisionswahrscheinlichkeit ist was Mathematica hilfreich mitteilt, ist.

Somit beträgt die Gewinnrate von Spieler B und die von Spieler A .$\Pr(Y > X) \approx 46.7\%$$\frac{619\,380\,496}{1\,162\,261\,467} \approx 53.3\%$

Sei der Fall, dass der Spieler, der würfelt, i Köpfe dreht, bevor der andere Spieler j Köpfe dreht, und sei die ersten beiden Köpfe mit dem Abtastraum wobei h Köpfe bedeutet und t tails, und lass .$E_{ij}$$X$$\{ hh,ht,th,tt\}$$p_{ij} \equiv Pr(E_{ij})$

Dann ist $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)$

Angenommen, eine Standardmünze bedeutet, dass$Pr(X=*)=1/4$$p_{ij}=1/4*[p_{i-1j-1}+p_{i-1j}+p_{ij-1}+p_{ij}]$

Auflösen nach ,$p_{ij}$$= 1/3*[p_{i-1j-1}+p_{i-1j}+p_{ij-1}]$

Aber und , was bedeutet, dass die Rekursion vollständig endet. Eine direkt naive rekursive Implementierung führt jedoch zu einer schlechten Leistung, da sich die Zweige überschneiden.$p_{0j}=p_{00}=1$$p_{i0}=0$

Eine effiziente Implementierung weist eine Komplexität und eine Speicherkomplexität . Hier ist eine einfache, in Haskell implementierte Falte:$O(i*j)$$O(min(i,j))$

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: Jemand in den obigen Kommentaren fragte, ob man 10 Köpfe hintereinander würfeln sollte oder nicht. Also sei der Fall, dass der Spieler, der würfelt, i Köpfe in einer Reihe dreht, bevor der andere Spieler i Köpfe in einer Reihe dreht, vorausgesetzt, er hat bereits k bzw. l aufeinanderfolgende Köpfe gedreht.$E_{kl}$

Es wird wie oben vorgegangen, jedoch nur beim ersten Flip konditioniert: wobei$p_{k,l} = 1-1/2*[p_{l,k+1}+p_{l,0}]$$p_{il}=p_{ii}=1, p_{ki}=0$

Dies ist ein lineares System mit Unbekannten und einer einzigartigen Lösung.$i^2$

Um es in ein iteratives Schema umzuwandeln, fügen Sie einfach eine iterative Zahl und einen Sensitivitätsfaktor :$n$$\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})]$

Wählen Sie und Bedacht und führen Sie die Iteration für einige Schritte aus und überwachen Sie den Korrekturterm. $\epsilon$$p_{k,l,0}$