À quelle fréquence devez-vous lancer un dé à 6 faces pour obtenir chaque numéro au moins une fois?

41

Je viens de jouer avec mes enfants à un jeu qui se résume essentiellement à: celui qui lance chaque chiffre au moins une fois sur un dé à 6 faces gagne.

J'ai finalement gagné et les autres ont fini 1-2 tours plus tard. Maintenant, je me demande: quelle est l'attente de la longueur du jeu?

Je sais que l’attente du nombre de jets jusqu’à ce que vous atteigniez un nombre donné est .n=1n16(56)n1=6

Cependant, j'ai deux questions:

  1. Combien de fois devez-vous lancer un dé à six faces jusqu'à ce que vous obteniez tous les nombres au moins une fois?
  2. Parmi les quatre essais indépendants (c'est-à-dire avec quatre joueurs), quelle est l'attente du nombre maximum de lancers nécessaires? [note: c'est le maximum, pas le minimum, car à leur âge, il s'agit plus de finir que d'arriver au premier rang pour mes enfants]

Je peux simuler le résultat, mais je me demande comment je pourrais le calculer de manière analytique.


Voici une simulation Monte Carlo dans 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
la source
11
Voir aussi le problème du collecteur de coupons - googler vous donnera beaucoup plus de visites et plus d’informations. Essayez aussi de chercher ça ici à stats.SE .
Glen_b -Reinstate Monica
1
@Glen_b: Merci, je ne connaissais pas ce nom!
Jonas
1
@ Whuber: Je ne suis pas sûr que cette question aurait dû être fermée. Il veut le temps de frappe minimum prévu de quatre essais. J'étais sur le point de corriger ma réponse pour la solution de programmation dynamique.
Neil G
2
@whuber: Je vais éditer mon post pour clarifier
Jonas
3
Article math.SE pertinent: Distribution de probabilité dans le problème du collecteur de coupons
Glen_b -Reinstate Monica le

Réponses:

22

Parce qu'une "approche totalement analytique" a été demandée, voici une solution exacte. Il fournit également une autre approche pour résoudre la question sur Probabilité de dessiner une boule noire dans un ensemble de boules noires et blanches avec des conditions de remplacement mixtes .


Le nombre de coups dans le jeu, , peut être modélisé comme la somme de six réalisations indépendantes de variables géométriques avec des probabilités , chacun d'entre eux décalé de (car une variable géométrique ne compte que les rôles précédents un succès et nous devons également compter les rôles sur lesquels des succès ont été observés). En calculant avec la distribution géométrique, nous obtiendrons donc des réponses moins que celles souhaitées et nous devrons donc nous assurer d’ajouter à la fin.X(p)p=1,5/6,4/6,3/6,2/6,1/616 666

La fonction génératrice de probabilité (pgf) d’une telle variable géométrique avec le paramètre estp

F(z,p)=p1-(1-p)z.

Par conséquent, le pgf pour la somme de ces six variables est

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

(Le produit peut être calculé sous cette forme fermée en le séparant en cinq termes au moyen de fractions partielles.)

La fonction de distribution cumulative (CDF) est obtenue ʻa partir des sommes partielles de (en tant que série de puissances en ), ce qui revient à sommer des séries géométriques et est donnée pargz

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

(J'ai écrit cette expression sous une forme suggérant une dérivation alternative via le principe d'inclusion-exclusion.)

On obtient ainsi le nombre attendu de coups dans le jeu (en répondant à la première question)

E(6+X)=6+i=1(1F(i))=147dix.

Le CDF du maximum de versions indépendantes de est (et à partir de là nous pouvons, en principe, répondre à toute question de probabilité relative au maximum que nous aimons, telle que sa variance, son 99ème centile , etc). Avec on obtient une espérance demXF(z)mm=4

6+Σje=1(1-F(je)4)21.4820363.

(La valeur est une fraction rationnelle qui, sous forme réduite, a un dénominateur à 71 chiffres.) L’écart type est de Voici un graphique de la fonction de masse de probabilité du maximum pour quatre joueurs (il a déjà été décalé de ):6.77108.6

Figure

Comme on pouvait s'y attendre, il est positivement asymétrique. Le mode est à rouleaux. Il est rare que la dernière personne à terminer prenne plus de rouleaux (environ ).18500.3%

whuber
la source
Cette méthode de solution s’inspire de l’observation selon laquelle les sommes des variables géométriques sont des mélanges (éventuellement avec des poids négatifs) de variables géométriques ayant les mêmes paramètres. Une relation similaire existe entre les variables gamma (avec des paramètres de taux différents). Je m'excuse pour le travail effectué dans Mathematica, mais je suis sûr que Matlab peut également effectuer ces calculs :-).
whuber
2
C'est la réponse que j'espérais. Merci beaucoup! Je pense que je devrais être capable de calculer les résultats numériques dans Matlab :)
Jonas
Quel est le lien entre et la distribution massique de probabilité de la distribution géométrique? D'où provient le produit ? Je comprends la signification de , mais quelle est la signification de ? F(z,p)=p1-(1-p)zΠje=16F(z,je/6)F(z)g(z)
Sextus Empiricus
1
Je vois maintenant que est la fonction génératrice de probabilité . f(z,p)
Sextus Empiricus Le
@ MartijnWeterings Merci - Je pense que c'est le terme le plus précis et le plus conventionnel. (Vous pouvez dire que j'ai tendance à penser que les fichiers pmf et pgf sont presque identiques, en raison d'une longue habitude d'utiliser des fonctions génératrices.) Je changerai la terminologie utilisée dans cet article.
whuber
13

ThePawn a la bonne idée pour s'attaquer au problème avec une relation de récurrence. Prenons une chaîne de Markov avec les états correspondant au nombre de lancers de dés distincts qui se sont produits. L'état 0 est l'état de départ et l'état 6, l'état d'arrivée. Alors, la probabilité de transition de l’état à lui-même est . La probabilité de transition de l'état à l'état est de . Par conséquent, l'heure d'arrivée de l'état d'arrivée est i i{0,,6}je ii+16-ii6jei+15 Σ i = 0 66-je6

Σje=0566-je=14.7

Pour un maximum de quatre essais, considérons les états quadruples. Vous voulez trouver le temps de frappe attendu pour l'état cible . Le temps de frappe attendu de tout état est la moyenne pondérée pour chaque état source du temps de frappe attendu plus le temps pour passer de à , pondéré par , la probabilité d'arriver à l'état et de passer àj i T i i j p i p i j i j(6,6,6,6)jjeTjejejpjepjejjej. Vous pouvez découvrir les temps de frappe et les probabilités par une programmation dynamique. Ce n'est pas si difficile car il existe un ordre de parcours pour indiquer les temps et probabilités de frappe. Par exemple, pour deux dés: calculez d'abord T et p pour (0,0), puis pour (1,0), puis (1, 1), (2, 0), puis (2, 1), etc.

En 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
la source
1
Vous avez manqué le nombre maximum attendu de lancers dans quatre répétitions indépendantes du match.
Probistislogic
Ah, je viens de remarquer ça. Je pense que vous voulez dire minimum, mais oui.
Neil G
@NeilG: En fait, je veux dire maximum (voir ma question mise à jour), bien que je suppose que la stratégie est la même pour min et max. Pouvez-vous élaborer sur la stratégie de programmation dynamique?
Jonas
@Jonas: mis à jour pour le maximum. J'ai beaucoup de travail, mais je pourrais peut-être le coder pour vous plus tard.
Neil G
2
@NeilG: Merci. J'espérais obtenir une approche complètement analytique, mais le code du PDD est également très instructif.
Jonas
6

Estimation rapide et approximative de Monte Carlo en R de la durée d'une partie pour 1 joueur:

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

Résultats: , , donc un intervalle de confiance de 95% pour la moyenne est . σ =6,24[14,645,14,722]μ^=14.684σ^=6.24[14.645,14.722]

Pour déterminer la durée d’une partie à quatre joueurs, nous pouvons regrouper les échantillons en quatre et prendre la longueur minimale moyenne pour chaque groupe (vous avez demandé quelle était la valeur maximale, mais je suppose que vous vouliez dire la durée minimale car, comme je l’ai lu, le jeu se termine lorsque quelqu'un réussit à obtenir tous les chiffres):

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

Résultats: , , donc un intervalle de confiance de 95% pour la moyenne est . σ =2,26[9,411,9,468]μ^=9.44σ^=2,26[9.411,9.468]

Bnaul
la source
1
Je suis arrivé à un résultat très similaire avec une simulation Matlab, mais j'étais curieux de savoir comment résoudre ce problème de manière analytique. De plus, depuis que je joue avec mes enfants, ils veulent tous finir le jeu, peu importe qui gagne, alors je veux poser des questions sur le maximum.
Jonas
5

Que diriez-vous d’une relation récursive en ce qui concerne le nombre restant de côtés que vous devez obtenir pour gagner?m

T m = 1 + 6 - m

T1=6
Tm=1+6-m6Tm+m6Tm-1

Fondamentalement, la dernière relation dit que le nombre de fois où rouler les nombres restants est égal à plus:m1

  • Tm si vous obtenez l'un des nombres déjà obtenus (probabilité )6-m6-m6
  • Tm-1 si vous obtenez l'un des nombres restants (probabilité )mm6

L'application numérique de cette relation donne .14.7

Le pion
la source
Quelque chose ne va pas avec cette réponse. Ne devrait-il pas s'agir d'un résumé à la fin? . Tje=Tje-1+66-je+1
Neil G
1
Oui désolé fait une erreur, je corrige
ThePawn
J'espère que cela ne vous dérange pas que j'ai ajouté une réponse. 14.7 est correct, mais la relation de récurrence est toujours imparfaite…
Neil G
Pas de problème, aurait dû faire attention la première fois :). Votre réponse est géniale.
ThePawn
5

Une explication simple et intuitive à la première question:

Vous devez d'abord rouler n'importe quel nombre. C'est facile, il faut toujours exactement 1 rouleau.

Vous devez ensuite lancer un nombre autre que le premier. La probabilité que cela se produise est de ; il faudra donc en moyenne (1.2).5665

Vous devez ensuite lancer un nombre autre que les deux premiers. La probabilité que cela se produise est de ; il faudra donc en moyenne (1,5).4664

Vous devez ensuite lancer un nombre autre que les trois premiers. La probabilité que cela se produise est de ; il faudra donc en moyenne (2).3663

Et ainsi de suite jusqu'à ce que nous terminions avec succès notre 6ème rouleau:

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

Cette réponse est similaire à celle de Neil G, mais sans la chaîne de markov.


la source
1

la fonction de densité de probabilité (ou son équivalent discret) pour obtenir le prochain nouveau nombre est:

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

où p est la probabilité par rouleau, 1 quand aucun nombre n'a été roulé, 5/6 après 1, 4/6 .. jusqu'à 1/6 pour le dernier nombre

la valeur attendue, mu = somme (i * p * (1 - p) ^ (i - 1), i = 1 .. inf) laissant n = i - 1 et faisant passer p en dehors de la somme,

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

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

La somme des valeurs attendues (mus) pour ps de 1, 5/6, 4/6, 3/6, 2/6 et 1/6 correspond à 14,7 comme indiqué précédemment, mais 1 / p par nombre requis est générale indépendamment de taille de matrice

de même, nous pouvons calculer l'écart type analytiquement

sigma ^ 2 = somme ((i - mu) ^ 2 * p * (1 - p) ^ (i - 1), i = 1 .. inf)

Je vous épargne l'algèbre ici, mais sigma ^ 2 = (1-p) / p ^ 2

Dans le cas de 6, la somme de sigma ^ 2 pour chaque étape est de 38,99 pour un écart type d’environ 6,24, encore une fois, comme simulé

MikeP
la source
-4

La question 1 était:

Combien de fois devez-vous lancer un dé à six faces jusqu'à ce que vous obteniez chaque numéro au moins une fois?

De toute évidence, la réponse correcte doit être «infinie».

Stef van Buuren
la source
6
Cela répondrait à la question "pour garantir avec une certitude absolue d'obtenir chaque numéro au moins une fois". Pour la question qui a été posée, la réponse est une variable aléatoire, dont la distribution peut être très approximée.
Glen_b -Reinstate Monica