Comment simuler un dé avec une bonne pièce

Supposons que l'on vous donne une pièce équitable et que vous souhaitez simuler la distribution de probabilité de lancer à plusieurs reprises un dé équitable (à six faces). Mon idée initiale est que nous devons choisir des entiers appropriés , tels que 2 k = 6 m . Ainsi, après avoir retourné la pièce k fois, nous mappons le nombre codé par la chaîne de bits de longueur k aux sorties du dé en divisant la plage [ 0 , 2 k - 1 ] en 6 intervalles de longueur m chacun . Cependant, cela n'est pas possible, car 2 k en a deux comme seul facteur premier, mais les facteurs premiers de$k,m$$2^k = 6m$$k$$[0,2^k-1]$$m$$2^k$ incluent trois. Il devrait y avoir un autre moyen simple de le faire, non?$6m$

Pour avoir une méthode légèrement plus efficace que celle indiquée par @FrankW mais en utilisant la même idée, vous pouvez lancer votre pièce fois pour obtenir un nombre inférieur à 2 n . Ensuite, interprétez cela comme un lot de m flips, où m est le plus grand nombre de sorte que 6 m < 2 n (comme déjà dit, l'égalité ne tient jamais ici). Si vous obtenez un nombre supérieur ou égal à 6 m, vous devez rejeter la valeur et répéter tous les n flips.$n$$2^n$$m$$m$$6^m < 2^n$$6^m$$n$

Vous pouvez implémenter une fonction qui renvoie un seul jet de dé en effectuant tirages de pièces, puis mettre en cache le résultat pour les m - 1 demandes de jet de dé suivantes.$n$$m-1$

Le point intéressant est que certaines valeurs de sont meilleures que d'autres car elles ont un taux de rejet inférieur. Voici une liste de bonnes valeurs (c'est-à-dire des valeurs qui ont un taux de rejet inférieur aux précédentes):$n$

n m r
3 1 0.25
8 3 0.15625
13 5 0.05078125
44 17 0.0378308072686
75 29 0.0247036782182
106 41 0.0113974522704
243 94 0.00933096248381
380 147 0.00726015308463
517 200 0.00518501504347
654 253 0.00310553931213
791 306 0.00102171682348

obtenu avec les formules: .

La première ligne correspond à la réponse de @FrankW avec un taux de rejet de 25%. Les nombres suivants sont agréables: et n = 13 peuvent tous deux être conservés dans une seule variable statique entière. En particulier, le taux de rejet de n = 13 n'est que de 5%, ce qui est une amélioration sensible par rapport à 25% et en fait un bon candidat pour une éventuelle mise en œuvre.$n=8$$n=13$$n=13$

Ce que vous pouvez faire, c'est utiliser une méthode appelée échantillonnage par rejet :

• Lancez la pièce 3 fois et interprétez chaque flip comme un bit (0 ou 1).
• $[0,7]$
• $[1,6]$
• $0$$7$

$\frac 68$$l$$(1-\frac 68)^l = \dfrac 1{4^l}$

Améliorations:

$0$$7$

@Emanuele Paolini explique comment réduire le nombre de relances si vous avez besoin de plusieurs jets de dé.

Une alternative à l'échantillonnage de rejet (comme décrit dans la réponse de FrankW ) est d'utiliser un algorithme de mise à l'échelle, qui prend en compte une réponse de [7,8] comme s'il s'agissait d'un autre retournement de pièce.

Il y a une explication très détaillée sur mathforum.org , y compris l'algorithme (ce NextBit()serait retourner votre juste monnaie).

Le cas pour lancer un dé avec une pièce équitable (échantillonnage 2 → 6) est plus facile que l'algorithme générique. Vous prenez juste un échec (7 ou 8) comme une autre entrée de pièces et effectuez deux flips supplémentaires.

Une autre approche pour simuler un roulement d'un dN en utilisant un dM (dans le cas de la question spécifique posée un d6 en utilisant un d2) consiste à partitionner l'intervalle [0, 1) en N intervalles égaux de longueur 1 / N, [0, 1 / N), [1 / N, 2 / N), ..., [(N-1) / N, N).

Utilisez le dM pour générer une fraction base-M, 0.bbbb ..., dans [0, 1). Si cela tombe dans [(i-1) / N, i / N), prenez i comme le rouleau du dN. Notez que vous n'avez qu'à générer suffisamment de chiffres en base M de la fraction pour déterminer l'intervalle dans lequel elle se trouve.

Une explication peut-être plus simple d'un échantillonnage de rejet amélioré.

Je donne cette explication car elle peut, espérons-le, aider à simplifier la compréhension ou l'analyse des probabilités dans certaines situations.

FrankW suggère d' utiliser l'échantillonnage de rejet, de retourner la pièce trois fois, de conserver le résultat s'il se trouve dans la bonne plage ou de répéter les trois tours autrement, jusqu'à ce qu'il réussisse.

Ángel suggère de sauvegarder un flip à chaque essai, en le remplaçant par un choix binaire restant parmi les deux valeurs inutilisées de l'ensemble précédent de trois.

Cela signifie vraiment qu'un bit d'information a été produit avec les trois premiers flips, qui n'a pas dû être produit. Plus précisément, vous devriez avoir besoin de lancer la pièce seulement deux fois pour savoir si l'ensemble actuel de flips réussira.

Savoir si l'ensemble actuel de flip sera réussi est la seule probabilité qui compte , car interpréter un ensemble de flip réussi est indépendant de la probabilité. Et cela peut être connu avant que tous les flips ne soient terminés pour cet ensemble.

Cela peut être réalisé d'au moins deux manières, ou plus précisément dans deux interprétations différentes des flips. Il peut y en avoir d'autres.

Regroupement des résultats par paires

L'idée est de ne considérer que trois valeurs (1,2), (3,4) et (5,6) représentées par trois configurations à double retournement, disons TT, TH, HT. Ensuite, vous pouvez appliquer un échantillonnage de rejet à double retournement, en répétant chaque fois que vous obtenez la configuration de défaillance HH.

Une fois que vous obtenez l'une des trois configurations réussies, il vous suffit de lancer la pièce une fois de plus pour décider si vous devez prendre la première ou la deuxième valeur de la paire correspondante.

Détection précoce des pannes de flip-set

L'idée est d'utiliser une lecture légèrement différente de la configuration à trois flips. Si Head et Tail sont interprétés comme 1 et 0, alors une configuration doit correspondre à l'interprétation binaire plus un. C'est-à-dire que TTT (ie 000) correspond à 1, HTH (ie 101) correspond 6, HHT (ie 110) et HHH (ie 111) correspond à 7 et 8, ou n'importe quoi en dehors de [1,6].

Ensuite, nous savons que le flip-set réussit ou échoue avec seulement les deux premiers flips. S'ils produisent HH, le jeu de flip échoue indépendamment du dernier flip. Il peut donc être ignoré.

Je pense que la détection précoce peut toujours être utilisée comme explication, mais selon le nombre de visages sur vos dés simulés, la détection d'échec peut se produire après un nombre variable de flips.

Par exemple, pour un dé à 10 faces, vous avez en principe besoin d'un jeu de flips de 4 flips, avec 6 configurations correspondant à l'échec. L'astuce consiste à avoir toutes les configurations de défaillance à l'extrémité supérieure de la séquence de valeurs binaires comme suit:

TTTT  0000   1
HTTT  1000   9
HTTH  1001  10
HTHT  1001  11
HTHH  1011  12
HHTT  1100  13
HHHH  1111  16

Les configurations réussies correspondent à la plage [1, 10] et les échecs à la plage [11,16].

Ensuite, vous échouez lorsque les deux premiers flips donnent HH, ou lorsque les trois premiers donnent HTH, sans même avoir à tenter les flips manquants de l'ensemble.

Si vous n'échouez pas, vous terminez simplement l'ensemble de flips.

Il existe deux approches bien connues à ce sujet. L'un est "l'échantillonnage de rejet". Par exemple, utilisez trois bits pour choisir une valeur sur six, en essayant à nouveau pour les deux échantillons supplémentaires. Ou utilisez 14 bits (8192 valeurs) pour sélectionner 5 valeurs de 1 à 6 (7776 possibilités), réessayez dans 13 cas sur 256.

L'autre utilise la partie décompression d'un algorithme de compression / décompression: avec le codage arithmétique, une séquence de valeurs aléatoires de 1 à 6 peut être compressée sans presque aucune redondance. Générez la séquence compressée au hasard et décompressez-la. C'est beaucoup plus compliqué, mais ne nécessitera pratiquement pas de nombres aléatoires supplémentaires.

Désolé à l'avance si l'explication est superflue. Je n'étais pas sûr de la quantité de détails à entrer ou de la facilité de compréhension du concept.

Disons que vous avez trois pièces (des pièces justes). Si vous attribuez progressivement une valeur à chaque côté de chaque pièce, vous aurez six valeurs.

Comme ceci: sur la première pièce, les têtes sont 1 et les queues sont 2. Sur la deuxième pièce, les têtes sont 3 et les queues sont 4. Sur la troisième pièce, les têtes sont 5 et les queues sont 6.

Faire tourner les pièces vous laissera un ensemble de trois nombres, votre ensemble actuel. Maintenant, votre ensemble actuel deviendra votre ensemble précédent et vous répéterez le processus pour obtenir un nouvel ensemble de trois nombres.

Continuez ainsi jusqu'à ce qu'un seul et unique numéro corresponde de votre ensemble actuel à l'ensemble précédent. Voilà votre numéro.

Donc, si vous avez [têtes, queues, têtes] pour l'ensemble actuel, ce serait [1, 4, 5]. Maintenant, vous les retournez à nouveau et votre ensemble actuel est [2, 4, 5]. Deux matchs. Pas bien. Essayez à nouveau. Vous obtenez [2, 3, 6]. Un seul match. Votre numéro est deux.

Il y aura une chance égale qu'un numéro donné apparaisse, mais ce n'est pas particulièrement rentable, étant donné qu'il n'y a qu'un changement de 3/32 pour qu'une paire d'ensembles donnée réussisse (une seule correspondance). Donc, en moyenne, l'algorithme devrait répéter une dizaine de fois. De plus, il n'est pas facilement généralisable aux dés impairs.

À tout le moins, c'est peut-être matière à réflexion. Question très intéressante.

Je lancerais la pièce trois fois et interpréterais le résultat comme un nombre binaire, rejetant les résultats hors de portée.

Par exemple, laissez les têtes être un 1 et les queues 0. Si vous le retourniez trois fois et obteniez des têtes, des queues, des têtes, vous auriez le binaire 101, qui est 5 en décimal. HHT = 110b = 6. TTT = 000b = 0 et HHH = 111b = 7, qui sont tous les deux hors de portée et seraient rejetés, et vous refléteriez pour tous les chiffres.

Malheureusement, on ne peut pas (fidèlement) simuler un dé (juste) en utilisant des (séquences de) pièces justes.

$6$$2$

Mais on peut le faire avec un "tri-coin" juste (si un tel terme peut être utilisé). Ce qui signifie une pièce avec 3 résultats. Et une simple pièce de 2 pièces, donc l'espace commun de ces 2 pièces correspond exactement à l'espace d'événement du dé.

L'échantillonnage de rejet (comme mentionné dans certaines réponses) peut effectivement fournir une simulation approximative . Mais il y aura toujours une quantité d'erreur ou de mauvaise correspondance des probabilités (en temps fini). Donc, si l'on veut réellement faire correspondre les espaces événementiels de ces 2 systèmes, il y aura des cas où cela ne fonctionnera pas.

En simulation probabiliste (dont l'échantillonnage de rejet est un exemple), les séquences typiques générées présentent en effet les probabilités élémentaires relatives (dans ce cas l'espace événementiel d'un dé). Cependant (comme mentionné dans les commentaires), chacune de ces séquences typiques peut contenir des sous-séquences arbitrairement longues d'exactement les mêmes résultats. Cela signifie que pour utiliser l'échantillonnage de rejet (dans certains cas), cela peut prendre un temps arbitraire ou la distribution générée sera biaisée (c'est-à-dire pas juste mourir), en raison de la surreprésentation ou de la sous-représentation de certaines parties de son espace d'événements. . si ce n'était pas le cas, alors un algorithme déterministe serait possible qui correspondrait exactement aux espaces d'événement d'un dé et d'une pièce (qui ne correspondent pas par dimensionnalité).