Tirage au sort avec un dé

[Médiat]

Il y a certainement une erreur dans mes calculs ... et pas le temps ce soir
-----

[Médiat]

C'est plutôt 6 le coefficient à la place du 2

[Amanuensis]

Comme le nombre de tirs est nécessairement supérieur ou égal à , on a déjà un encadrement de l'espérance entre M et 6M.

Ce qui suit sauf erreur:

L'algo suivant permet d'améliorer la borne supérieure sur l'espérance.

 Cliquez pour afficher

Soit la division euclidienne de 6^M par N, 6^M=n1 N + r1. On tire M dés, tirage qu'on traduit en un nombre entre 0 et 6^M-1, et on alloue les n1 N premières valeurs équitablement aux N joueurs. Reste r1 cas de retirage.

On tire 1 dé de plus, on traduit le résultat combiné avec la valeur résiduelle précédente en un nombre entre 0 et 6r1-1 ; notons la division euclidienne 6r1 = n2 N +r2, on alloue les n2 N premières valeurs équitablement. Et on réitère pour les r2 cas restants, etc.

Exemple avec N=109: 3 tirages donnent 216 cas différents, le processus termine dans 109 de ces cas, il en reste 107 où on tire au moins une fois de plus. En cas de retirage on a 6 fois 107 cas distincts, ce qui permet de finir dans 5 fois 109 soit 545 d'entre eux, reste 97. On tire un dé de plus, cela donne 582 cas, on tire un de plus dans 37 d'entre eux, etc.

L'espérance est alors 3 + 107/216 (1 + 97/642 (1+ 37/582 (1 + ...))), inférieur à 3 + 107/216 (1 + 97/642 (1+ 37/582 (1 + 1))), un peu inférieur à 3.6

Conjecture: c'est toujours plus petit que M+1 (et peut-être bornable par M + k avec k plus petit que 1, mais plus grand que 1/2)

===========

Quant à un algo borné en nombre de tirs, un argument assez simple permet de montrer que c'est impossible pour N=5, simplement parce qu'aucune puissance de 6 n'est un multiple de 5.

[Médiat]

Bonjour,

Je ne suis pas sûr d'avoir compris la méthode d'Amanuensis (en fait je suis sûr de ne pas l'avoir comprise), mais en utilisant l'idée de la division euclidienne, le cas le plus défavorable est dont l'espérance du nombre de répétition est

Clairement majoré par 2.

[Juzo]

Bonjour,
Je n'ai pas d'ordinateur et n'arrive pas à ouvrir les spoilers de mon téléphone, j'ai un peu de mal à suivre.
Si le premier chiffre de l'écriture en base 6 de N est inférieur à 3, on peut attribuer plusieurs numéros à chaque joueur, ce qui fait que la probabilité de devoir tirer à nouveau les dés est toujours inférieure à 1/2.

[Amanuensis]

Je développe un peu...

Ce qui suit sauf erreur:

L'algo suivant permet d'améliorer la borne supérieure sur l'espérance.

Deux "astuces" sont mises en oeuvre comparé à la simple écriture en base 6 et réitération. a) On exploite toutes les valeurs possibles dans l'intervalle 0..n1*N-1, avec n1*N le plus grand multiple de N inférieur à la plus petite puissance de 6 supérieure à N. b) Dans le traitement de l'itération suivante, on utilise le "résidu" (ce qui dépasse de n1*N) du tirage précédent comme "source d'aléa uniforme", en la combinant avec un tir de dé.

L'algo:

Soit N le nombre de joueurs, numérotés de 0 à N-1 ; on note , c'est à dire le nombre de chiffres de N en base 6.

Soit n1, r1 résultat de la division euclidienne de 6^M par N, i.e., 6^M=n1*N + r1.

On tire M dés, tirage qu'on traduit en un nombre k1 entre 0 et 6^M-1 en prenant les résultats comme les chiffres en base 6 du nombre. Si k1 est inférieur ou égal à n1*N-1 (n1*N cas), le joueur choisi est celui de numéro k1 modulo N, et le processus est terminé.

Il reste r1 cas de retirage (r1 peut être nul si N divise 6^M, auquel cas le processus s'arrête), pour k1>=n1*N. On note s1 = k1 - n1*N, nombre compris entre 0 et r1-1 (le "résidu", un tirage uniforme entre 0 et r1-1).

Retirage :

On tire 1 dé de plus, de résultat x entre 1 et 6 ; on construit le nombre k2 = (x-1)*r1+s1, qui est compris entre 0 et 6*r1-1, 6*r1 possibilités. Et k2 est traité comme l'a été k1. Et on réitère jusqu'à terminaison.

Exemple avec N=109: 3 tirages donnent 216 cas différents, le processus termine dans 109 de ces cas, il en reste 107 où on tire au moins une fois de plus. En cas de retirage on a 6 fois 107 cas distincts, ce qui permet de finir dans 5 fois 109 soit 545 d'entre eux, reste 97. On tire un dé de plus, cela donne 582 cas, on tire un de plus dans 37 d'entre eux, etc.

L'espérance est alors 3 + 107/216 (1 + 97/642 (1+ 37/582 (1 + ...))), inférieur à 3 + 107/216 (1 + 97/642 (1+ 37/582 (1 + 1))), un peu inférieur à 3.6

Conjecture: c'est toujours plus petit que M+1 (et peut-être bornable par M + ε avec ε plus petit que 1, mais plus grand que 1/2)

[Amanuensis]

Note 1: la première étape est différente des suivantes. Une réitération ne consiste pas à tirer de nouveau un nombre de N chiffres en base 6, mais seulement un seul dé.

Note 2: Un point que je n'avais pas vu ; il ne change pas l'algo (il me semble), mais affecte le calcul de l'espérance.

Il se peut qu'une itération ne soit pas productive (c'est ce qui change et complique le calcul de l'espérance). C'est le cas pour 6^M=1 modulo N. Prenons par exemple N=35, M=2. Dans la première étape, 35 des 36 cas terminent, et un retirage est nécessaire dans un cas. Le résidu est alors nécessairement s1=0. L'itération suivante donne un nombre k2 entre 0 et 5, ce qui ne produit rien ; mais s2=k2. L'itération suivante donne un nombre k3 entre 0 et 35, ce qui est productif dans 35 cas sur 36.

Dans ce cas l'algo est identique à une itération avec tirage complet d'un nombre de N "sixales".

On va donc se retrouver avec une espérance de tirage dont le terme dominant est en x(N)M, avec x>1 (donc moins bien que ce que j'ai indiqué), et le pire cas pour N sera de ce genre. Dans le cas N=35 ci-dessus, x = 36/35, sauf erreur. Je n'ai encore réfléchi à ce pire cas, peut-être celui déjà indiqué? Ou peut-être pour 6^M = N-1 modulo N. À suivre

[Amanuensis]

Note 3: L'algo termine en p tirs pour N diviseur de 6^p (avec p le plus petit possible). Il serait intéressant de calculer l'espérance.

Prenons par exemple N=32.

On tire 2 dés, dans 32 cas sur 36, terminé. Dans les 4 restants, on tire un dé plus, donnant 4x6 =24 cas différents, non productif. On tire un nouveau un dé, donnant 6x24 = 144 cas différents, et cela finit dans 128 d'entre eux. Dans les 16 restants on tire un dé, donnant 96 cas et l'algo est terminé.

On a donc bien 5 tirs au maximum, comme attendu, et une espérance de, sf erreur, 2 + 4/32 (2 + 16/144), soit 2 + 19/72, approx. 2.26

[Juzo]

Bonjour,
Soit d1 le plus grand diviseur de N inférieur ou égal à r1. Il est possible de définir N/d1 gagnants sur d1 valeurs situées entre n1*N et 6^M, ce qui réduit le tri pour la suite. (et complique les calculs ; ))

[Amanuensis]

Je ne suis pas sûr de comprendre.

J'essaye un exemple, N=32

On tire 2 dés, dans 32 cas sur 36, terminé. Reste 4 cas (r1=4), 4 est un diviseur de 32. On a divisé au préalable les 32 en 4 groupes de 8, et on limite à un des groupes, restent alors 8 candidats. Un tir supplémentaire ne suffit pas. Deux tirs de plus donnent 36 cas, cela finit pour 32 d'entre eux, restent 4 cas, un tir supplémentaire termine.

C'est bien une application de l'idée ?

[Juzo]

Oui, ça donne 4 tirs maximum au lieu de 5 dans l'exemple donné plus haut.

[Juzo]

Oui, ça donne 4 tirs maximum au lieu de 5 dans l'exemple donné plus haut.

Ah non 5 aussi. Je n'ai pas le bouton pour modifier mon message.

[Amanuensis]

Erreur ...

[Amanuensis]

Hmm, désolé, mon message précédent est ambigu, je m'en rends compte trop tard. J'avais écrit un message que j'ai ensuite effacé en le remplaçant par le texte. L'erreur était mienne, toute autre interprétation est due à l'ambiguïté que j'ai laissée par inadvertance.

[Amanuensis]

Sinon, après vérifications, tous les cas que j'ai étudiés donnent le même résultat (max et moyenne) avec ou sans la variante proposée. Ce n'est pas une preuve générale, néanmoins. Avantage de la variante: cela permet de travailler sur des nombres plus petits, et simplifie les calculs! Entre autres en permettant de réutiliser des calculs déjà faits sur les diviseurs de N.

(Par exemple, N=8 moyenne de 2+1/9 -> N=32 moyenne 2+4/36 (2+1/9)

[Au passage, correction d'une erreur:

On a donc bien 5 tirs au maximum, comme attendu, et une espérance de, sf erreur, 2 + 4/32 (2 + 16/144), soit 2 + 19/72, approx. 2.26

C'est 2 + 4/36 (2 + 16/144), soit 2 + 1/9 (2+1/9), approx. 2.2346

]

[Verdurin]

Bonsoir Amanuensis.
Je ne suis pas d’accord avec l'affirmation qu'il y a un nombre de tirages maximum avec ton algorithme.

Pour prendre un exemple simple : avec 5 joueurs il revient à lancer le dé tant qu'on a pas un résultat entre 1 et 5.
La loi suivie par le nombre de lancers est une loi géométrique de paramètre 5/6. Et elle n'est pas bornée.

[Amanuensis]

Conjecture: L'espérance du nombre de tirs de l'algo proposé est au plus M+3/5, celle valeur étant approchée d'aussi près qu'on veut, avec M assez grand, pour les N = 1 + 1/2 6^M

Assertion assez "empirique", je ne vois pas trop comment la démontrer!

===

Une piste pourrait venir de la remarque suivante.

Prenons N=19, l'espérance se calcule comme une série de la forme:

2 + 17/36(1+7/102(1+4/42(1+5/24(1+...

Dans la suite de fractions, le dénominateur est égal à six fois le numérateur de la précédente. En série additive, cela devient donc

2 + 17/6^2 + 7/6^3 + 4/6^4 + 5/6^5 + ...

Qu'on peut réécrire, ce qui absorbe le "M" initial

1 + 6/6^1 + 17/6^2 + 7/6^3 + 4/6^4 + 5/6^5 + ...

En notant a_i les numérateurs, on a a_{i+1} = 6 x a_i mod 19, avec a_0=1

D'où en toute généralité, pour N>1,



avec ,


Comme le nombre de valeurs modulo N est finie, la suite des a_i est cyclique à partir d'un certain rang, et la somme est rationnelle.

Peut-être qu'un bon matheux (pas moi, donc) peut démontrer une majoration de cette somme?

===

Sur ce, bye, et merci pour ce problème intéressant!

[polo974]

Question: Y-a-t'il une solution en un nombre borné de tirages ne serait-ce que pour N=5?

Quelque soit N, il suffit de N tirages au grand max.
Il "suffit" de compter en "base 1" (on compte les traits) (1,2,3=>0 et 4,5,6 => 1) et faire la somme qui ira forcement de 0 à N-1.

Auparavant, on peut gagner sur les nombre divisibles par 6, 2 ou 3.

bref,
un tirage par division exacte par 6 (à répéter autant que peut),
un tirage par division exacte par 3 ou (exclusif) 2 (à répéter autant que peut),
un tirage par N restant.

[invite51d17075]

Quelque soit N, il suffit de N tirages au grand max.

là je suis d'accord.
pour le reste , je comprend ton principe, mais j'ai du mal à voir ou est l'équiprobabilité parfaite.

[polo974]

là je suis d'accord.
pour le reste , je comprend ton principe, mais j'ai du mal à voir ou est l'équiprobabilité parfaite.

en gros, il faut réduire N en 6^a * 3^b * 2^c * d tel que:
d n'est multiple ni de 2 ni de 3
et b*c = 0

la question était:

Quelle est la méthode la plus économe en nombre de lancers de dé, pour tirer au sort équitablement un joueur parmi N joueurs avec un dé à 6 faces, et quelle sera une estimation du nombre de lancers nécessaires ?

c'est juste à cette question que je répondais.

[Verdurin]

Quelque soit N, il suffit de N tirages au grand max.
Il "suffit" de compter en "base 1" (on compte les traits) (1,2,3=>0 et 4,5,6 => 1) et faire la somme qui ira forcement de 0 à N-1.
[ . . . ]

Le problème de cette méthode est que la somme suit une loi binomiale, et non une loi uniforme.

Si on prend le cas N=5, les joueurs étant numéroté de 0 à 4, on lance 4 fois le dé et on a
P(0)=P(4)=1/16
P(1)=P(3)=4/16
P(2)=6/16
où P(k) désigne la probabilité de choisir le joueur numéro k.

On est assez loin de l’équiprobabilité.

[Verdurin]

@ Amanuensis.
Je crois que ton algorithme est optimal.
Je ne crois pas qu'il soit possible de donner une « formule simple » permettant de calculer l’espérance du nombre de tirage en fonction de N.

À titre d'exemple j'ai calculé l'espérance du nombre de lancers de dé pour N=31.
J'ai trouvé


Avec une méthode de rejet simple on a une espérance de
.

On voit que le bénéfice est petit, mais réel.

[Amanuensis]

En tous cas, je ne trouve pas moyen d'améliorer...

Un petit point, la formule que j'ai donnée message #47 pour l'espérance peut se réécrire de manière plus concise comme:

En toute généralité, pour N>1,



et se généralise pour toute valeur de dé autre que 6...

[CM63]

C'est l'espérance du nombre de tirage (et non pas l'espérance de N, qui est le nombre de joueurs) ?

[invite51d17075]

C'est l'espérance du nombre de tirage (et non pas l'espérance de N, qui est le nombre de joueurs) ?

Oui, bien sur.
Mais il s'agit bien de l'espérance, pas du nb total qui assurerait à coup sûr ( avec méthodologie ad hoc ) un tirage totalement équiprobable.
Concernant ce dernier le seul chiffre ( énorme ) que je pourrais avancer dans un cas totalement général est le PPCM de 6 et N.
donc sans cas particulier des congruences de N.

Je ne suis pas sur d'avoir saisi le calcul d'Amanuensis concernant l'espérance, et j'avoue avoir du mal à être certain que la méthode proposée soit elle aussi équiprobable.
Certainement du à une mauvaise compréhension de ma part.

[Médiat]

Après réflexion, je n'ai plus de doutes sur l'équiprobabilité : à chaque fois que l'on lance 1 (ou plusieurs dé), c'est pour écrire un nombre supérieur ou égal à N chacun ayant une probabilité égal à 1/6^M.

D'autre part cette méthode utilise, à chaque étape, tous les dés déjà utilisés, un raisonnement entropique montre que c'est certainement la meilleure espérance possible dans le cas général (sans exclure la possibilité que dans certains cas particuliers on puisse trouver un peu mieux)

[invite51d17075]

edit : reflexion en cours

[invite51d17075]

OK, pigé:
grâce à l'élimination des tirages "non affectables" , les probas restent identiques, même si leur somme ne vaut pas 1 ( ce qui n'importe pas )

[Amanuensis]

Il y a peut-être moyen de démontrer l'optimalité. Une piste pourrait venir de la propriété suivante:

Aucun algorithme ne peut terminer en i tirs mieux que dans (6^i-(6^i mod N)) cas sur les 6^i.

Cela se montre, il me semble, à partir de l'idée que l'équité implique que le nombre de cas où l'algo termine est nécessairement un multiple de N.

Une deuxième étape, plus conjecturelle, serait l'idée qu'un algorithme A a une espérance (du nombre de tirs lorsqu'il termine) strictement plus faible qu'un autre B que si et seulement si il existe au moins un i tel qu'à l'étape i, A termine dans strictement plus de cas que B

[Idée: si c'est égal à tout i, alors l'espérance est la même.]

(Si cette conjecture était vérifiée, alors l'algo proposé est optimal en espérance, puisqu'il a la propriété d'avoir à toute étape la plus grande proportion possible de cas de terminaisons.)

[Amanuensis]

PS: [Tout ce qui suit "Sauf erreur de ma part"] La variante proposée par Juzo message #39 donne aussi des algos optimaux, mais cela ne change pas la proportion des cas terminant suffisamment loin après application ; cela donnerait donc des algos équivalents, présentant quelques avantages comme mentionnés #45. Le calcul de l'espérance est le même, une fois ramenés les formules au N originel.

Un exemple élémentaire est celui des N de la forme 6N', avec N' premier avec 6. Une variante est un alors un premier tir utilisé pour choisir un sous-ensemble de N' candidats, et l'algorithme ensuite est celui de base, sur N' candidats.

Dans mes interventions depuis le message #45, ces variantes sont incluses quand je parle de "l'algo".