Dessinez des entiers indépendamment et uniformément au hasard de 1 à utilisant juste d6?

18

Je souhaite dessiner des entiers de 1 à un spécifique en lançant un certain nombre de dés à six faces justes (d6). Une bonne réponse expliquera pourquoi sa méthode produit des entiers uniformes et indépendants .NN

À titre d'exemple illustratif, il serait utile d'expliquer comment une solution fonctionne pour le cas de .N = 150N=150

De plus, je souhaite que la procédure soit la plus efficace possible: lancer le moins de d6 en moyenne pour chaque numéro généré.

Les conversions du sénaire au décimal sont autorisées.


Cette question a été inspirée par ce fil Meta .

Sycorax dit de réintégrer Monica
la source

Réponses:

12

L'ensemble de résultats identifiables distincts dans rouleaux indépendants d'une matrice avec faces a éléments. Lorsque le dé est juste, cela signifie que chaque résultat d'un lancer a une probabilité et l'indépendance signifie que chacun de ces résultats aura donc une probabilité c'est-à-dire qu'ils ont une distribution uniformeΩ ( d , n ) Ω(d,n)n nd = 6 d=6d ndn 1 / d 1/d( 1 / d ) n : (1/d)n:P d , n .Pd,n.

Supposons que vous ayez mis au point une procédure qui détermine soit résultats d'un dé côté , c'est-à-dire un élément de soit signale un échec (ce qui signifie que vous devrez répéter pour obtenir un résultat). C'est,t tm mc ( = 150 ) c(=150)Ω ( c , m )Ω(c,m)

t : Ω ( d , n ) Ω ( c , m ) { Échec } .

t:Ω(d,n)Ω(c,m){Failure}.

Soit la probabilité que entraîne un échec et notons que est un multiple entier de disonsF Ft tF Fd - n ,dn,

F = Pr ( t ( ω ) = échec ) = N Fd - n .

F=Pr(t(ω)=Failure)=NFdn.

(Pour référence future, notez que le nombre attendu de fois que doit être appelé avant de ne pas échouer est )t t1 / ( 1 - F ) .1/(1F).

L'exigence selon laquelle ces résultats dans soient uniformes et indépendant conditionnel à ne pas signaler des moyens de défaillance qui préserve la probabilité dans le sens que pour chaque événementΩ ( c , m ) Ω(c,m)t t AΩ ( c , m ) ,ttAΩ(c,m),

P d , n ( t A )1 - F =Pc,m(A)

Pd,n(tA)1F=Pc,m(A)(1)

t ( A ) = { ω Ω t ( ω ) A }

t(A)={ωΩt(ω)A}

est l'ensemble des jets de dés que la procédure assigne à l'événementt tA .A.

Considérons un événement atomique , qui doit avoir la probabilitéSoit (les jets de dés associés à ) ont éléments. devientA = { η } Ω ( c , m ) A={η}Ω(c,m)c - m . cm.t ( A )t(A) η ηN ηNη ( 1 )(1)

Nηdn1NFdn=Pd,n(tA)1F=Pc,m(A)=cm.

Nηdn1NFdn=Pd,n(tA)1F=Pc,m(A)=cm.(2)

Il est immédiat que les sont tous égaux à un entierNηNηN.N. Il ne reste plus qu'à trouver les procédures les plus efficaces Le nombre attendu de non-échecs par lancer du dé face est det.t.cc

1m(1F).

1m(1F).

Il y a deux implications immédiates et évidentes. La première est que si nous pouvons maintenir petit à mesure que devient grand, alors l'effet de signaler une défaillance est asymptotiquement nul. L'autre est que pour tout donné (le nombre de rouleaux de la matrice face à simuler), nous voulons rendre aussi petit que possible.F Fm mm mccFF

Examinons de plus près en effaçant les dénominateurs:( 2 )(2)

N c m = d n - N F > 0.

Ncm=dnNF>0.

Cela rend évident que dans un contexte donné (déterminé par ), est rendu aussi petit que possible en faisant égal le plus grand multiple de qui est inférieur ou égal à Nous pouvons écrire ceci en termes de la plus grande fonction entière (ou "étage") commec , d , n , m c,d,n,mF Fd n - N F dnNFc m cmd n . dn.

N = d nc m.

N=dncm.

Enfin, il est clair que doit être aussi petit que possible pour une efficacité maximale, car il mesure la redondance en . Plus précisément, le nombre prévu de rouleaux de la à flancs matrice nécessaire pour produire un rouleau de à flancs DieN Nt d ctdc

N × nm ×11 - F .

N×nm×11F.

Ainsi, notre recherche de procédures à haute efficacité devrait se concentrer sur les cas où est égal ou juste à peine supérieur à une puissanced n dnc m .cm.

L'analyse se termine en montrant que pour et donnés il existe une séquence de multiples pour laquelle cette approche se rapproche de l'efficacité parfaite. Cela revient à trouver pour lequel approche dans la limite (garantissant automatiquement ). Une telle séquence est obtenue en prenant et en déterminantd dc , c,( n , m ) (n,m)( n , m ) (n,m)d n / c m1 dn/cm1N = 1 N=1F 0 F0n = 1 , 2 , 3 , n=1,2,3,

m = n log dlog c.

m=nlogdlogc.(3)

La preuve est simple.

Tout cela signifie que lorsque nous sommes prêts à rouler l'original à flancs mourir un assez grand nombre de fois nous pouvons nous attendre pour simuler presque les résultats d'un à flancs meurent par rouleau . De manière équivalente,d dn , n,log d / log c = log c d logd/logc=logcdcc

Il est possible de simuler un grand nombre de rouleaux indépendants d'un à flancs mourir en utilisant un juste à flancs mourir en utilisant une moyenne de lance par résultat où peut être rendu arbitrairement petit en choisissant suffisamment grand.m mc cd dlog ( c ) / log ( d ) + ϵ = log d ( c ) + ϵ Journal( c ) / log( d) + ϵ = log( c ) + ϵϵ ϵmm


Exemples et algorithmes

Dans la question, et oùd = 6 = 6c = 150 ,c = 150 ,

log d ( c ) = log ( c )log ( d )2.796489.

logd(c)=log(c)log(d)2.796489.

Ainsi, la meilleure procédure possible nécessitera, en moyenne, au moins rouleaux de a pour simuler chaque résultat.2.7964892.796489d6d150

L'analyse montre comment procéder. Nous n'avons pas besoin de recourir à la théorie des nombres pour la réaliser: nous pouvons simplement tabuler les puissances et les puissances et les comparer pour trouver où sont proches. Ce calcul de force brute donne pairesd n = 6 n dn=6nc m = 150 m cm=150mc md ncmdn ( n , m )(n,m)

( n , m ) { ( 3 , 1 ) , ( 14 , 5 ) , }

(n,m){(3,1),(14,5),}

par exemple, correspondant aux nombres

( 6 n , 150 m ) { ( 216 , 150 ) , ( 78364164096 , 75937500000 ) , } .

(6n,150m){(216,150),(78364164096,75937500000),}.

Dans le premier cas, associerait des résultats de trois rouleaux de a à Échec et les autres résultats seraient chacun associés à un seul résultat de a . t t216 - 150 = 66 216150=66150d6150d150

Dans le second cas associerait des résultats des 14 rouleaux d'une à l' échec - environ 3,1% de tous - et par ailleurs serait sortie une séquence de 5 résultats d'un .t t78364164096 - 759375000007836416409675937500000d6d150

Un algorithme simple à mettre en oeuvrett étiquettes des faces de la à flancs mourir avec les numéros et les faces de la à flancs mourir par les numéros Les rouleaux de la première matrice sont interprétées comme un nombre à chiffres dans la base Ceci est converti en un nombre dans la base S'il a au plus chiffres, la séquence des derniers chiffres est la sortie. Sinon, renvoie Failure en s'invoquant récursivement. d d0 , 1 , , d - 1 0,1,,d1c c0 , 1 , , c - 1. 0,1,,c1.n nn nd . d.c . c.m mm mtt

Pour des séquences beaucoup plus longues, vous pouvez trouver des paires appropriées en considérant tous les autres convergents de l'expansion continue des fractions de La théorie des fractions continues montre que ces convergents alternent entre être inférieurs à et supérieurs à lui (en supposant que n'est pas déjà rationnel). Choisissez ceux qui sont inférieurs à( n , m ) (n,m)n / m n/mx = log ( c ) / log ( d ) . x=log(c)/log(d).x xx xx .x.

Dans la question, les premiers de ces convergents sont

3 , quatorze / 5 , 165 / 59 , 797 / 285 , 4301 / 1 538 , 89 043 / 31 841 , 279235 / 99852 , 29036139 / 10.383.070 ... .

3,14/5,165/59,797/285,4301/1538,89043/31841,279235/99852,29036139/10383070.

Dans le dernier cas, une séquence de 29.036.139 rouleaux d'un d6produira une séquence de 10.383.070 rouleaux d'un d150avec un taux d'échec inférieur à pour une efficacité de indiscernable de la limite asymptotique.2 × 10 - 8 , 2×108,2,796492.79649

whuber
la source
2
Incroyable comme toujours, il semble presque que cette réponse a été formatée et préparée avant même que la question ne soit posée!
Łukasz Grad
1
Merci, @ ŁukaszGrad. Cependant, je suis innocent de telles machinations et je suis sûr que les lecteurs aux yeux pointus trouveront des preuves de la hâte avec laquelle j'ai écrit cela, et je m'en excuse à l'avance.
whuber
Ne faut-il pas également tenir compte du fait que lorsque n'est pas premier, l'espace échantillon peut être partitionné en sous-ensembles de probabilité égale? Par exemple, vous pouvez utiliser un d6 comme d2 ou d3, et un espace échantillon avec 162 éléments - plus proche de 150 que 216 est - est alors réalisable avec 4 rouleaux, 1d6 + 3d3. (Cela donne le même nombre de rouleaux attendu que la solution 3d6, mais une variance plus faible.)d Ω ( d , 1 )dΩ(d,1)
Scortchi - Réinstallez Monica
@Scortchi Vous décrivez un cadre légèrement différent dans lequel on a le choix de dés à utiliser pour simuler des tirages à partir d'une distribution uniforme. Une analyse similaire s'applique - vous pourriez trouver amusant de la réaliser.
whuber
7

Pour le cas de , un roulement de d6 trois fois crée distinctement résultats.N = 150 N=1506 3 = 21663=216

Le résultat souhaité peut être tabulé de cette manière:

  • Enregistrez un d6 trois fois de suite. Cela produit les résultats . Le résultat est uniforme car toutes les valeurs de sont également probables (les dés sont justes et nous traitons chaque jet comme distinct).a , b , c a,b,ca , b , ca,b,c
  • Soustrayez 1 de chaque.
  • Il s'agit d'un nombre sénaire: chaque chiffre (valeur de position) passe de 0 à 5 par puissances de 6, vous pouvez donc écrire le nombre en décimal en utilisant(a1)×62+(b1)×61+(c1)×60
    (a1)×62+(b1)×61+(c1)×60
  • Ajoutez 1.
  • Si le résultat dépasse 150, jetez-le et relancez.

La probabilité de conserver un résultat est . Tous les jets sont indépendants, et nous répétons la procédure jusqu'à un "succès" (un résultat en ) donc le nombre de tentatives pour générer 1 tirage entre 1 et 150 est distribué comme une variable aléatoire géométrique, qui a l'attente . Par conséquent, l'utilisation de cette méthode pour générer 1 tirage nécessite de lancer lancers de dés en moyenne (car chaque tentative lance 3 dés).p=150216=2536p=150216=25361,2,,1501,2,,150p1=3625p1=36253625×3=4.323625×3=4.32


Nous remercions @whuber de l'avoir suggéré dans le chat.

Sycorax dit de réintégrer Monica
la source
Je crois que la méthode d'Henry ne produit pas une distribution uniforme. En effet, le recyclage va favoriser certains chiffres. Je ne suis pas complètement sûr de cela parce que je ne comprends pas complètement comment le recyclage doit être effectué.
whuber
1
@whuber AH! Je comprends maintenant votre inquiétude. Je viens d'essayer de m'expliquer le processus et j'ai compris pourquoi mon intuition était défectueuse: la probabilité de lancer un dé supplémentaire peut changer l'attribution des probabilités aux nombres décimaux et la rendre non uniforme parce que nous ne savons pas à l'avance comment de nombreux dés que nous lançons.
Sycorax dit Réintégrer Monica
4

Voici une alternative encore plus simple à la réponse de Sycorax pour le cas où . Puisque vous pouvez effectuer la procédure suivante:N=150N=150150=5×5×6150=5×5×6

Génération d'un nombre aléatoire uniforme de 1 à 150:

  • Faites trois rouleaux ordonnés de 1D6 et les .R1,R2,R3R1,R2,R3
  • Si l'un des deux premiers rouleaux est un six, relancez-le jusqu'à ce qu'il ne soit pas 6.
  • Le nombre est un nombre uniforme utilisant la notation positionnelle avec un radix de 5-5-6. Ainsi, vous pouvez calculer le nombre souhaité comme: (R1,R2,R3)(R1,R2,R3)X=30(R11)+6(R21)+(R31)+1.
    X=30(R11)+6(R21)+(R31)+1.

Cette méthode peut être généralisée à un plus grand , mais elle devient un peu plus gênante lorsque la valeur a un ou plusieurs facteurs premiers supérieurs à .NN66

Réintégrer Monica
la source
1
Pouvez-vous indiquer l'efficacité de cette méthode en termes de nombre attendu de rouleaux par tirage généré, et expliquer pourquoi le résultat est uniforme sur 1,2, ...., 150?
Sycorax dit Réintégrer Monica
La probabilité d'obtenir un résultat qui ne nécessite pas de relance est de , ce qui est le même que dans votre réponse. Pour comprendre pourquoi il est uniforme, notez que vous générez simplement un nombre uniforme en utilisant la notation positionnelle avec le radix 5-5-6 (c.-à-d., Le dernier chiffre est les unités, l'avant-dernier chiffre est le "six" et le troisième -le dernier chiffre est le "trente"). 25/36
Rétablir Monica
1
La méthode n'est en fait qu'une très légère variation de la méthode dans votre réponse. Dans votre réponse, vous créez un nombre uniforme sur l'échelle des nombres 6-6-6 puis supprimez les valeurs invalides, tandis que dans ma réponse, vous supprimez d' abord les valeurs invalides pour générer un nombre sur l'échelle 5-5-6.
Rétablir Monica
3
+1 En pratique, il s'agit d'un algorithme attrayant. Il est intrigant, et peut-être suggérant une analyse plus large, qu'il implémente un automate à états finis entraîné par les dés. Il a quatre états, {Démarrer, A, B, Accepter}. Commencez les transitions vers A lors du roulement 1..5; A passe à B lors du roulement 1..5; et B transitions pour accepter lors du roulement de quoi que ce soit. Chaque transition enregistre la valeur du rouleau qui l'a provoqué, donc en atteignant Accepter, vous sortez cette séquence de trois rouleaux stockés et passez automatiquement au début.
whuber
4
Vous refusez aussi souvent que @Sycorax, mais faites moins de rouleaux en moyenne. Le non attendu. rouleaux par variante est . 65+65+1=3.4
Scortchi - Réintégrer Monica
2

À titre d'illustration d'un algorithme pour choisir uniformément entre valeurs à l'aide de dés à six faces, essayez ceci qui utilise chaque lancer pour multiplier les valeurs disponibles par et rendre chacune des nouvelles valeurs également probable:1506

  • Après lancer, vous avez possibilité, pas assez pour distinguer valeurs01150
  • Après rouleau, vous avez possibilités, pas assez pour distinguer valeurs16150
  • Après rouleaux, vous avez possibilités, pas assez pour distinguer valeurs236150
  • Après rouleaux, vous avez possibilités, assez pour distinguer valeurs mais avec valeurs restantes; la probabilité que vous vous arrêtiez maintenant est321615066150216
  • Si vous ne vous êtes pas arrêté, alors après rouleaux, vous avez possibilités restantes, assez pour distinguer valeurs de deux manières mais avec valeurs restantes; la probabilité que vous vous arrêtiez maintenant est4396150963001296
  • Si vous ne vous êtes pas arrêté, alors après rouleaux, vous avez possibilités restantes, assez pour distinguer valeurs de trois manières mais avec valeurs restantes; la probabilité que vous vous arrêtiez maintenant est5576150964507776
  • Si vous ne vous êtes pas arrêté, alors après rouleaux, vous avez possibilités restantes, assez pour distinguer valeurs de cinq manières mais avec valeurs restantes; la probabilité que vous vous arrêtiez maintenant est6756150675046656

Si vous êtes sur l'une des valeurs restantes après rouleaux, vous êtes dans une situation similaire à la position après rouleau. Vous pouvez donc continuer de la même manière: la probabilité que vous vous arrêtiez après lancers est , après lancers est etc.6617027993681501679616

Ajoutez-les et vous constaterez que le nombre attendu de rouleaux nécessaires est d'environ . Il fournit une sélection uniforme parmi les , car vous ne sélectionnez qu'une valeur à un moment où vous pouvez sélectionner chacun des avec une probabilité égale3.39614150150


Sycorax a demandé dans les commentaires un algorithme plus explicite

  • Tout d'abord, je travaillerai en base avec615010=4106
  • Deuxièmement, plutôt que les valeurs cibles à , je soustrais une valeur pour que les valeurs cibles soient de à164106064096
  • Troisièmement, chaque dé doit avoir les valeurs à , et lancer un dé implique d'ajouter un chiffre de base sur le côté droit du nombre généré existant. Les nombres générés peuvent avoir des zéros non significatifs, et leur nombre de chiffres est le nombre de rouleaux jusqu'à présent06566

L'algorithme est des jets de dés successifs:

  • Lancez les trois premiers dés pour générer un nombre entre et . Puisque vous prenez la valeur générée (qui est aussi son reste sur division par ) si la valeur générée est strictement inférieure à et arrêtez;0006555610006÷4106=16 remainder 15064106100061506=4106

  • Si vous continuez, lancez le quatrième dé pour avoir maintenant généré un nombre entre et . Puisque vous prenez le reste de la valeur générée sur division par si la valeur générée est strictement inférieure à et arrêtez;4100655556100006÷4106=126 remainder 240641061000062406=53206

  • Si vous continuez, lancez le cinquième dé pour avoir maintenant généré un nombre entre et . Puisque vous prenez le reste de la valeur générée sur division par si la valeur générée est strictement inférieure à et arrêtez;5320065555561000006÷4106=1236 remainder 3306410610000063306=552306

  • Si vous continuez, lancez le sixième dé pour avoir maintenant généré un nombre entre et . Depuis vous prenez le reste de la valeur générée sur division par si la valeur générée est strictement inférieure à et arrêtez;5523006555555610000006÷4106=12356 remainder 106410610000006106=5555506

  • etc.

Henri
la source
(+1) Cette réponse serait plus claire si vous expliquiez comment vous mappez les résultats de, disons, 4d6 ou 5d6 à 1,2, ..., 150.
Sycorax dit Reinstate Monica
@Sycorax - J'ai maintenant fourni une cartographie de base6
Henry
1
Les considérations d'entropie indiquent que vous pouvez faire beaucoup mieux que cet algorithme. Il reste également à montrer que votre algorithme produit en fait des valeurs distribuées indépendamment avec des distributions uniformes .
whuber
@whuber - Mon algorithme produit exactement un entier parmi possibilités et le fait uniformément à condition que les jets de dés soient uniformes et indépendants. À chaque étape, si elle est atteinte, chacune des valeurs est également susceptible d'être sélectionnée. Il ne produit pas de valeurs multiples (contrairement à votre réponse)150150
Henry
1
J'ai alors mal compris ce que vous vouliez dire en écrivant "l'algorithme est des jets de dés successifs". (J'aurais dû lire plus attentivement.) Ce faisant, il me semble que votre algorithme ne produit pas une distribution uniforme, mais je ne suis pas sûr car je n'ai pas été en mesure de comprendre à quoi l'algorithme général est destiné être. Il serait bon de voir une démonstration qu'il produit des valeurs uniformes.
whuber