Wie oft muss man einen 6-seitigen Würfel werfen, um jede Zahl mindestens einmal zu erhalten?

41

Ich habe gerade ein Spiel mit meinen Kindern gespielt, bei dem es im Grunde genommen darauf ankommt, dass jeder, der mindestens einmal auf einem 6-seitigen Würfel würfelt, gewinnt.

Ich habe letztendlich gewonnen und die anderen haben 1-2 Runden später beendet. Jetzt frage ich mich: Was ist die Erwartung an die Länge des Spiels?

Ich weiß, dass die Erwartung der Anzahl der Würfe, bis Sie eine bestimmte Zahl treffen, .n=1n16(56)n1=6

Ich habe jedoch zwei Fragen:

  1. Wie oft müssen Sie einen sechsseitigen Würfel werfen, bis Sie jede Zahl mindestens einmal bekommen?
  2. Wie hoch ist die Erwartung an die maximale Anzahl an Würfen bei vier unabhängigen Versuchen (dh mit vier Spielern) ? [Anmerkung: Es ist ein Maximum, nicht ein Minimum, denn in ihrem Alter geht es für meine Kinder mehr ums Beenden als darum, zuerst dort hinzukommen.]

Ich kann das Ergebnis simulieren, aber ich frage mich, wie ich es analytisch berechnen würde.


Hier ist eine Monte-Carlo-Simulation in 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
quelle
11
Das Problem des Couponsammlers ist auch zu sehen - googeln gibt Ihnen viel mehr Treffer und mehr Informationen. Versuchen Sie auch, hier unter stats.SE danach zu suchen .
Glen_b
1
@ Glen_b: Danke, ich wusste diesen Namen nicht!
Jonas
1
@whuber: Ich bin mir nicht sicher, ob diese Frage hätte geschlossen werden sollen. Er will die erwartete Mindestschlagzeit von vier Versuchen. Ich wollte gerade meine Antwort für die dynamische Programmierlösung festlegen.
Neil G
2
@whuber: Ich werde meinen Beitrag bearbeiten, um zu klären
Jonas
3
Relevanter math.SE-Beitrag: Wahrscheinlichkeitsverteilung im Problem des
Couponsammlers

Antworten:

22

Da ein "vollständig analytischer Ansatz" gewünscht wurde, ist hier eine genaue Lösung. Es bietet auch einen alternativen Ansatz zur Lösung der Frage unter Wahrscheinlichkeit, eine schwarze Kugel in eine Reihe von schwarzen und weißen Kugeln mit gemischten Ersetzungsbedingungen zu zeichnen .


Die Anzahl der Züge im Spiel, , kann als Summe von sechs unabhängigen Realisierungen von geometrischen Variablen mit Wahrscheinlichkeiten modelliert werden. , jeder von ihnen um verschoben (weil eine geometrische Variable nur die Rollen zählt, die einem Erfolg vorausgehen, und wir müssen auch die Rollen zählen, auf denen Erfolge beobachtet wurden). Durch Berechnen mit der geometrischen Verteilung erhalten wir daher Antworten, die kleiner als die gewünschten sind, und müssen daher sicherstellen, dass am Ende zurückaddiert werden.X(p)p=1,5/6,4/6,3/6,2/6,1/616 666

Die Wahrscheinlichkeitsfunktion (pgf) einer solchen geometrischen Variablen mit dem Parameter istp

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

Daher ist die pgf für die Summe dieser sechs Variablen

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

(Das Produkt kann in dieser geschlossenen Form berechnet werden, indem es über Teilfraktionen in fünf Terme aufgeteilt wird .)

Die kumulative Verteilungsfunktion (CDF) ergibt sich aus den Teilsummen von (als Potenzreihe in ), die die Summe der geometrischen Reihen ergeben, und ist gegeben durchgz

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

(Ich habe diesen Ausdruck in einer Form geschrieben, die eine alternative Herleitung über das Prinzip des Einschlusses-Ausschlusses vorschlägt .)

Daraus erhalten wir die erwartete Anzahl von Zügen im Spiel (Beantwortung der ersten Frage) als

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

Die CDF des Maximums von unabhängigen Versionen von ist (und daraus können wir im Prinzip alle Wahrscheinlichkeitsfragen über das Maximum beantworten, das wir mögen, wie z. B. die Varianz, das 99. Perzentil , und so weiter). Mit wir eine Erwartung vonmXF(z)mm=4

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

(Der Wert ist ein rationaler Bruch, der in reduzierter Form einen 71-stelligen Nenner hat.) Die Standardabweichung beträgt Hier ist eine Darstellung der Wahrscheinlichkeitsmassenfunktion des Maximums für vier Spieler (es wurde bereits um verschoben ):6.77108.6

Zahl

Wie zu erwarten ist, ist es positiv verzerrt. Der Modus ist bei Rollen. Es ist selten, dass die letzte Person, die fertig ist, mehr als Rollen nimmt (es sind ungefähr ).18500.3%

whuber
quelle
Diese Lösungsmethode wurde durch die Beobachtung angeregt, dass Summen geometrischer Variablen Gemische (möglicherweise mit negativen Gewichten) geometrischer Variablen mit denselben Parametern sind. Eine ähnliche Beziehung gilt für Gamma-Variablen (mit unterschiedlichen Ratenparametern). Ich entschuldige mich für die Arbeit in Mathematica, aber ich bin sicher, Matlab kann diese Berechnungen auch durchführen :-).
Whuber
2
Dies ist die Antwort, auf die ich gehofft habe. Vielen Dank! Ich denke, ich sollte in der Lage sein, die numerischen Ergebnisse in Matlab zu berechnen :)
Jonas
Wie hängt mit der Wahrscheinlichkeitsmassenverteilung der geometrischen Verteilung zusammen? Woher kommt das Produkt ? Ich erhalte die Bedeutung von , aber was ist die Bedeutung von ? f(z,p)=p1(1p)zi=16f(z,i/6)F(z)g(z)
Sextus Empiricus
1
Ich sehe jetzt , daß die Wahrscheinlichkeit ist , Erzeugungsfunktion. f(z,p)
Sextus Empiricus
@MartijnWeterings Danke - ich glaube, das ist der genauere und konventionellere Begriff. (Sie können feststellen, dass ich die Begriffe pmf und pgf aufgrund der langen Angewohnheit, generierende Funktionen zu verwenden, in der Regel als fast gleich betrachte.) Ich werde die Terminologie in diesem Beitrag ändern.
whuber
13

ThePawn hat die richtige Idee, das Problem mit einer Wiederholungsbeziehung anzugreifen. Stellen Sie sich eine Markov-Kette mit den Zuständen , die der Anzahl der einzelnen Würfelwürfe entspricht, die stattgefunden haben. Zustand 0 ist der Startzustand und Zustand 6 ist der Endzustand. Dann ist die Wahrscheinlichkeit des Übergangs vom Zustand zu sich selbst . Die Übergangswahrscheinlichkeit von Zustand zu Zustand ist . Daher ist der Endzeitpunkt {0,,6}ii6ii+16i6

i=0566i=14.7

Berücksichtigen Sie für maximal vier Versuche vierfache Zustände. Sie möchten die erwartete für den Zielzustand . Die erwartete Treffzeit eines Zustands ist der gewichtete Durchschnitt für jeden der erwarteten Treffzeit plus der Zeit von bis , gewichtet mit , der Wahrscheinlichkeit, in den Zustand und sich zu bewegenj i T i i j p i p i j i j(6,6,6,6)jiTiijpipijij. Sie können die Treffzeiten und Wahrscheinlichkeiten durch dynamische Programmierung ermitteln. Es ist nicht so schwer, da es einen Durchquerungsbefehl gibt, um die Schlagzeiten und Wahrscheinlichkeiten auszufüllen. Zum Beispiel für zwei Würfel: Berechnen Sie zuerst T und p für (0,0), dann für (1,0), dann (1, 1), (2, 0), dann (2, 1) usw.

In 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
quelle
1
Sie haben die erwartete maximale Anzahl von Würfen in vier unabhängigen Wiederholungen des Spiels verpasst.
Wahrscheinlichkeitsrechnung
Ah, das ist mir gerade aufgefallen. Ich denke du meinst Minimum, aber ja.
Neil G
@NeilG: Ich meine eigentlich Maximum (siehe meine aktualisierte Frage), obwohl ich davon ausgehe, dass die Strategie für min und max gleich ist. Können Sie bitte die Strategie der dynamischen Programmierung näher erläutern?
Jonas
@Jonas: Maximal aktualisiert. Ich habe eine Menge Arbeit, aber ich könnte das später für Sie programmieren.
Neil G
2
@ NeilG: Danke. Ich hatte gehofft, einen vollständig analytischen Ansatz zu erhalten, aber der DP-Code ist auch ziemlich anleitend.
Jonas
6

Schnelle und schmutzige Monte-Carlo-Schätzung in R der Länge eines Spiels für 1 Spieler:

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

Ergebnisse: , , daher beträgt das 95% -Konfidenzintervall für den Mittelwert .μ^=14.684σ^=6.24[14.645,14.722]

Um die Länge eines Spiels für vier Spieler zu bestimmen, können wir die Stichproben in vier Gruppen zusammenfassen und die durchschnittliche Mindestlänge für jede Gruppe ermitteln (Sie haben nach dem Maximum gefragt, aber ich nehme an, Sie haben das Minimum gemeint, da, wie ich es las, das Spiel endet, wenn es jemandem gelingt, alle Zahlen zu bekommen):

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

Ergebnisse: , , daher beträgt das 95% -Konfidenzintervall für den Mittelwert .μ^=9.44σ^=2.26[9.411,9.468]

bnaul
quelle
1
Ich kam mit einer Matlab-Simulation zu einem sehr ähnlichen Ergebnis, war aber gespannt, wie ich das analytisch lösen würde. Da ich mit meinen Kindern spiele, wollen sie alle das Spiel beenden, unabhängig davon, wer gewinnt. Deshalb möchte ich nach dem Maximum fragen.
Jonas
5

Wie wäre es mit einer rekursiven Beziehung in Bezug auf die verbleibende Anzahl Seiten, die Sie erhalten müssen, um zu gewinnen.m

T1=6
Tm=1+6m6Tm+m6Tm1

Grundsätzlich besagt die letzte Beziehung, dass die Anzahl der Rollen der verbleibenden unterschiedlichen Zahlen gleich plus ist:m1

  • Tm wenn Sie eine der Zahlen würfeln, die bereits gewürfelt wurden (Wahrscheinlichkeit )6m6m6
  • Tm1 wenn Sie eine der verbleibenden Zahlen würfeln (Wahrscheinlichkeit )mm6

Numerische Anwendung dieser Beziehung ergibt .14.7

Der Bauer
quelle
Mit dieser Antwort scheint etwas nicht zu stimmen. Sollte es nicht eine Summe am Ende sein? . Ti=Ti1+66i+1
Neil G
1
Ja, tut mir leid, einen Fehler gemacht, ich korrigiere es
ThePawn
Ich hoffe es macht Ihnen nichts aus, dass ich eine Antwort hinzugefügt habe. 14.7 ist richtig, aber die Wiederholungsbeziehung ist immer noch fehlerhaft ...
Neil G
Kein Problem, hätte beim ersten Mal aufpassen sollen :). Ihre Antwort ist großartig.
ThePawn
5

Eine einfache und intuitive Erklärung zur ersten Frage:

Sie müssen zuerst eine beliebige Zahl würfeln. Dies ist einfach, es wird immer genau 1 Rolle dauern.

Sie müssen dann eine andere Zahl als die erste würfeln. Die Chance, dass dies passiert, liegt bei werden also durchschnittlich (1,2) Würfe benötigt. 65665

Sie müssen dann eine andere Zahl als die ersten beiden würfeln. Die Chance, dass dies passiert, liegt bei , daher werden durchschnittlich (1,5) Würfe benötigt. 64664

Sie müssen dann eine andere Zahl als die ersten drei würfeln. Die Chance, dass dies passiert, liegt bei , daher werden durchschnittlich (2) Würfe benötigt. 63663

Und so weiter, bis wir unsere 6. Rolle erfolgreich abgeschlossen haben:

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

Diese Antwort ähnelt der Antwort von Neil G, nur ohne die Markov-Kette.


quelle
1

Die Wahrscheinlichkeitsdichtefunktion (oder ein diskretes Äquivalent) zum Erhalten der nächsten neuen Zahl lautet:

f = Summe (p * (1 - p) ^ (i - 1), i = 1 ... inf)

Dabei ist p die Wahrscheinlichkeit pro Wurf, 1, wenn keine Zahlen gewürfelt wurden, 5/6 nach 1, 4/6 .. bis auf 1/6 für die letzte Zahl

der erwartete Wert mu = Summe (i * p * (1 - p) ^ (i - 1), i = 1 ... inf), wobei n = i - 1 ist und p außerhalb der Summation gebracht wird,

mu = p * sum ((n + 1) * (1 - p) ^ n, n = 0 ... inf)

mu = p * sum (n (1 - p) ^ n, n = 0 ... inf) + p * sum ((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

Die Summe der erwarteten Werte (mus) für ps von 1, 5/6, 4/6, 3/6, 2/6 und 1/6 beträgt 14,7, wie zuvor berichtet, aber 1 / p pro erforderliche Anzahl ist unabhängig davon allgemein von der Größe sterben

Ebenso können wir die Standardabweichung analytisch berechnen

Sigma ^ 2 = Summe ((i - mu) ^ 2 * p * (1 - p) ^ (i - 1), i = 1 .. inf)

Ich werde Ihnen hier die Algebra ersparen, aber Sigma ^ 2 = (1-p) / p ^ 2

Im Fall von 6 beträgt die Summe von Sigma ^ 2 für jeden Schritt 38,99, was wiederum einer simulierten Standardabweichung von etwa 6,24 entspricht

MikeP
quelle
-4

Frage 1 war:

Wie oft müssen Sie einen sechsseitigen Würfel werfen, bis Sie jede Zahl mindestens einmal bekommen?

Offensichtlich muss die richtige Antwort "unendlich" sein.

Stef van Buuren
quelle
6
Das würde die Frage beantworten, "mit absoluter Sicherheit zu garantieren, dass jede Zahl mindestens einmal erhalten wird". Für die gestellte Frage ist die Antwort eine Zufallsvariable, deren Verteilung gut angenähert werden kann.
Glen_b