Quel est le nombre de fois que vous devez lancer un dé jusqu'à ce que chaque camp apparaisse 3 fois?
Cette question a été posée à l'école primaire en Nouvelle-Zélande et elle a été résolue à l'aide de simulations. Quelle est la solution analytique à ce problème?
Réponses:
Supposons que tous les côtés ont des chances égales. Généralisons et trouvons le nombre attendu de rouleaux nécessaires jusqu'à ce que le côté 1 apparaisse n 1 fois, le côté 2 apparaisse n 2 fois, ..., et le côté d apparaisse n d fois. Parce que les identités des côtés n'ont pas d'importance (elles ont toutes des chances égales), la description de cet objectif peut être condensée: supposons que i 0 côtés ne doivent pas du tout apparaître, i 1 des côtés doivent apparaître juste une fois, ... et i nré= 6 1 n1 2 n2 d nd i0 i1 in des côtés doivent apparaître fois. Soit i = ( i 0 , i 1 , … , e ( 0 , 0 , 0 , 6 ) : i 3 =n=max(n1,n2,…,nd) désigner cette situation et écrire e ( i ) pour le nombre attendu de rouleaux. La question demande
Une récurrence facile est disponible. Au rouleau suivant, le côté qui apparaît correspond à l'un des : c'est-à-dire que nous n'avions pas besoin de le voir, ou nous devions le voir une fois, ..., ou nous devions le voir n plus fois. j est le nombre de fois que nous avons eu besoin de le voir.ij n j
Quand , nous n'avions pas besoin de le voir et rien ne change. Cela se produit avec la probabilité i 0 / d .j = 0 je0/ d
Lorsque nous devions voir ce côté. Maintenant, il y a un côté de moins qui doit être vu j fois et un autre côté qui doit être vu j - 1 fois. Ainsi, i j devient i j - 1 et i j - 1 devient i j +j > 0 j j - 1 jej jej- 1 jej - 1 . Soit cette opération sur les composantes de i désignée i ⋅ j , de sorte quejej+ 1 je i ⋅j
Cela se produit avec la probabilité .jej/ d
Nous devons simplement compter ce jet de dé et utiliser la récursivité pour nous dire combien de rouleaux de plus sont attendus. Par les lois de l'espérance et de la probabilité totale,
(Comprenons que chaque fois que , le terme correspondant dans la somme est zéro.)ij=0
Si , nous avons terminé et e ( i ) = 0i0=d e(i)=0 . Sinon, nous pouvons résoudre pour , en donnant la formule récursive souhaitéee(i)
Notez que est le nombre total d'événements que nous souhaitons voir. L'opération ⋅ j réduit cette quantité par une pour tout j > 0 fourni i j > 0 , ce qui est toujours le cas. Par conséquent, cette récursivité se termine à une profondeur de précisément | je | (égal à 3 ( 6 ) =
Je calcule que
Cela me semblait terriblement petit, alors j'ai exécuté une simulation (en utilisant32.669 : la différence entre cette moyenne et la valeur théorique est insignifiante, confirmant l'exactitude de la valeur théorique.0.027
R
). Après plus de trois millions de lancers de dés, ce jeu avait été joué jusqu'à son terme plus de 100 000 fois, avec une longueur moyenne de . L'erreur type de cette estimation estLa distribution des longueurs peut être intéressante. (Évidemment, il doit commencer à , le nombre minimum de rouleaux nécessaires pour collecter les six côtés trois fois chacun.)18
la mise en oeuvre
Bien que le calcul récursif de soit simple, il présente certains défis dans certains environnements informatiques. Le plus important d'entre eux est le stockage des valeurs de e ( i ) lors de leur calcul. Ceci est essentiel, sinon chaque valeur sera (redondante) calculée un très grand nombre de fois. Cependant, le stockage potentiellement nécessaire pour un tableau indexé par i pourrait être énorme. Idéalement, seules les valeurs de i réellement rencontrées lors du calcul devraient être stockées. Cela nécessite une sorte de tableau associatif.e e(i) i i
Pour illustrer, voici lei i⋅j opération est implémentée comme
R
code de travail . Les commentaires décrivent la création d'une simple classe "AA" (tableau associatif) pour stocker les résultats intermédiaires. Les vecteurs sont convertis en chaînes et ceux-ci sont utilisés pour indexer dans une liste qui contiendra toutes les valeurs. L' i ⋅ jE
%.%
.Ces préliminaires permettent la fonction récursivee de définir assez simplement d'une manière parallèle à la notation mathématique. En particulier, la ligne
est directement comparable à la formule ci-dessus. Notez que tous les index ont été augmentés de 1 car commence à indexer ses tableaux à 1 plutôt qu'à 0(1) 1 1 0 .
R
Le timing montre qu'il faut seconde pour calculer0.01
e(c(0,0,0,6))
; sa valeur estL'erreur d'arrondi à virgule flottante accumulée a détruit les deux derniers chiffres (qui devraient être
68
plutôt que06
).Enfin, voici l' implémentation originale de Mathematica qui a produit la réponse exacte. La mémorisation est réalisée via l'
e[i_] := e[i] = ...
expression idiomatique , éliminant presque tous lesR
préliminaires. En interne, cependant, les deux programmes font les mêmes choses de la même manière.la source
La version originale de cette question a commencé sa vie en demandant:
Répartition du nombre de rouleaux requis ... de sorte que chaque face apparaisse 3 fois
Laisser:N= min { n :Xje≥ 3∀je} . est: P( N≤ n )=P( X∀je≥ 3∣∣n )
ie Pour trouver le cdfP( N≤ n ) , calculez simplement pour chaque valeur de n = { 18 , 19 , 20 , … } :
Voici, par exemple, le code Mathematica qui fait cela, commen passe de 18 à 60. Il s'agit essentiellement d'un vol simple:
... qui donne le cdf exact commen augmente:
Voici un tracé du cdfP( N≤ n ) , en tant que fonction de n :
Pour dériver le pmfP( N= n ) , commencez simplement par différencier le cdf:
Bien sûr, la distribution n'a pas de limite supérieure, mais nous pouvons facilement résoudre ici autant de valeurs que cela est pratiquement nécessaire. L'approche est générale et devrait fonctionner aussi bien pour toute combinaison désirée de côtés requise.
la source