[shell] Jeu du pendu

Bonjour,

Citation:

---

Envoyé par disedorgue

J'avais forcé un RANDOM modulo 10 car 32767 * 10 est assez proche de 300 000 (qui est la contenance de son dictionnaire)...

---

C'est malheureusement hors-sujet par rapport au poste initial, mais je n'arrive pas à ne revenir sur le caractère aléatoire d'une distrib calculée avec un modulo.

Supposons une distribution uniforme sur l'intervalle [1:N].
La distribution étant uniforme, chaque entrée a une probabilité 1/N de sortir.

On souhaite maintenant construire une distribution la plus uniforme possible sur un intervalle [1:M], avec M < N.
Dans notre boîte à outils, on ne dispose que d'un générateur aléatoire [1:N] et des opérateurs communs qu'on ne sait utiliser qu'avec des nombres entiers relatifs.
On a par ailleurs N = M * q + r, ou q est le quotient et r le reste de la division euclidienne de N par M.

On construit la distribution comme suit : RANDOM(N)%M+1

Code:

---

1 2 3 4 5 6 7

Soit n issu de RANDOM[1:N], avec 1 <= n <= M probabilité 1/N. On le met dans la distrib [1:M] ---- n ---- -- ------------ ---- M+1 <= n <= 2*M ----------- ---. -- -- --- ---- -- ------- [1:M] [...] [...] [...] ---- n ---- -- ------------ ---- (q-1)*M+1 <= n <= q*M ----------- ---. -- -- --- ---- -- ------- [1:M] ---- n ---- -- ------------ ---- q*M+1 <= n <= N=q*M+r ----------- ---. -- ------ ---- -- ------- [1:r]

---

Donc pour la distribution [1:M], les nombres [1:r] ont une probabilité de sortir de (q+1)/N, et les nombres compris entre [r+1:M] ont une probabilité de sortir de q/N.
C'est à dire :
Les nombres m <= r ont (q+1)/q = 1 + 1/q fois plus de chances que les autres de sortir, ce qui n'est pas très uniforme... Mais plus q est grand, soit plus N est immense devant M, plus l'erreur est moindre.

Si on prend un N trop juste mais dont on a l'impression qu'il est plus calibré pour le problème, tel que M < N < 2M par exemple, comme tu l'avais suggéré, on a q=1. Ca veut dire que les nombres compris entre [1:r] ont... 2 fois plus de chances de sortir que les autres. Peu importe leur nombre au sein de la distribution, l'erreur sur l'uniformité est énorme lors du passage à l'échelle, et si l'aléatoire que l'on met dans le problème est important, c'est rédhibitoire.

Si N > 1000 * M, c'est franchement pas top non plus si l'aléatoire est important, mais au moins, 1.001 fois plus de chances est mieux que 2 fois plus...
En conclusion, il faut raisonner sur l'erreur relative d'uniformité dans la distribution, et non la proportion des cas "non canoniques" de la distribution. En effet, qu'il y en ai peu ou beaucoup, si l'erreur est grande, lors du passage à l'échelle (nombre de tirage -> infini), les problèmes vont se voir plus que le nez au milieu de la figure (même avec un gros nez).
Et pour contrôler au mieux les problèmes d'erreur, réaliser les étapes biaisantes le plus tard possible pour ne pas avoir à réfléchir à la propagation des biais. Donc ici, prendre le modulo une seule fois à la fin.

Pour le pendu, osef, je suis bien d'accord.

Après, si on a vraiment besoin de l'aléatoire, on prend le problème au sérieux et on utilise autre chose que la fonction de RANDOM qui retourne des entiers signés de 16 bits... Et on prend encore moins une distribution obtenue en multipliant deux entiers randoms sur 16 pour simuler une distrib uniforme sur 32 bits (enfin sur 31 bits, car on a un bit de signe dans chaque distrib sur 16 bits, donc un bit de perdu par rapport à des entiers sur 32 bits signés...) (bah oui car, en dehors de la densité odd/even, quid par exemple des nombres premiers supérieurs à l'entier le plus grand codé sur 16 bits ? il n'y en a pas par définition (!), vu qu'on obtient ces nombre par multiplication)

Je retiens ta dernière objection qui est très bonne.
Le mot d'indice 100213 (par exemple) n'est jamais tiré au sort.
Il faudrait une concatenation textuelle des écritures bianires ou hexadécimales des deux RANDOM pour atteindre l'objectif, ce qui est facile en bash ou awk.


Pour le reste, je crois que tu te compliques la vie. Avec une distribution uniforme sur [1:N] et M<N, il suffit d'ignorer les tirages au-delà de M. Ou qM.
Ainsi tu as une distribution uniforme.

La probabilité de ne tirer que des nombres de [M+1:N] (respectivement [Mq+1:N]) est nulle.

Citation:

---

Envoyé par Flodelarab

Je retiens ta dernière objection qui est très bonne.
Le mot d'indice 100213 (par exemple) n'est jamais tiré au sort.
Il faudrait une concaténation textuelle des écritures binaires ou hexadécimales des deux RANDOM pour atteindre l'objectif, ce qui est facile en bash ou awk.

---

Tout à fait.

Citation:

---

Envoyé par Flodelarab

Pour le reste, je crois que tu te compliques la vie. Avec une distribution uniforme sur [1:N] et M<N, il suffit d'ignorer les tirages au-delà de M. Ou qM.
Ainsi tu as une distribution uniforme.

La probabilité de ne tirer que des nombres de [M+1:N] (respectivement [Mq+1:N]) est nulle.

---

Je critiquais l'utilisation du modulo qui est souvent utilisée pour des distributions d'entiers, et qui n'est pas une bonne méthode. Je soulignais les cas où elle était plus ou moins méchante. Plus particulièrement, je faisais une mise au point sur le raisonnement de disedorgue de 13h26 qui ne me convient pas. Et suis complètement d'accord sur la méthode de rejet (qui est straightforward !).

Bref, j'ai voulu faire un aparté en disant ce qui faisait plus ou moins mal dans l'usage du modulo. J'aurais pu avoir un peu moins la tête dans le guidon et ne pas me limiter à ça en disant ce qu'il était bien de faire en effet...
Avec ton post, c'est chose faite :ccool:.

Je suis conscient de mon erreur sur l'erreur de faire le modulo avant la multiplication.
Pour l'histoire de la distribution, je comprend le raisonnement, mais mon propos était plus pour essayer d'expliquer mon erreur sur le RANDOM*(RANDOM%10)...

Je ne comprends pas ce que vous voulez dire par "une concaténation textuelle des écritures binaires ou hexadécimales des deux RANDOM" et surtout comment on peut la réduire à la taille du dico.

Citation:

---

Envoyé par disedorgue

Je ne comprends pas ce que vous voulez dire par "une concaténation textuelle des écritures binaires ou hexadécimales des deux RANDOM"

---

RANDOM1 + RANDOM2 * 2^15 fait la concaténation en binaire il me semble. Après j'ai acquiescé un peu vite pour "concaténation textuelle ..."

Citation:

---

Envoyé par disedorgue

et surtout comment on peut la réduire à la taille du dico.

---

On a 0 <= N <= 2^30-1=NMAX, M le nombre de mots du dico
on pose Nm = ((int)(NMAX/M))*M = q*M
Si N >= Nm, on rejette le tirage
Sinon, nbligne=N%M+1, et on a une distrib uniforme, comme l'a proposé Flodelarab. (les rejets n'interviennent pas dans les stats, donc on a q/Nm proba pour chaque nombre).

• Pardon pour ma réponse. J'avais sans doute lu trop vite.
  
• De plus, mea culpa, mon exemple est mauvais. Certes, 100213 est premier, mais modulo 300000, il y a 400213 qui se factorise :D
  Donc le mot peut être tiré. (par les cheveux, aussi)
  
• En ce qui concerne le tirage aléatoire:
  
  On tire r1 et r2, 2 randoms, entre 0 et 32767 = 2**15-1
  La multiplication ne fonctionne pas car elle ne donne pas tous les entiers entre 0 et 2**30-1. Il manque les nombres premiers.
  
  La concaténation n'est ni la multiplication, ni l'addition, mais le fait d'écrire à la suite l'un l'autre (d'où la commande cat)
  
  10011
  11100
  ->
  1001111100
  
  Dans ce cas, tous les nombre sont atteints de manière uniforme.
  C'est facile à imaginer.
  Il n'y avait aucunement de réflexion sur ce qu'on n'en fait après.
  
  Par contre, je suis allé vite en disant que c'était facile à programmer, car écrire une variable en binaire n'est pas forcément facile.
  (C'est du binaire/héxa vers le décimal qui est facile)
  
  Code:

  ---

  1 2	$ echo $((2#11100)) 28

  ---

  De plus, il y a un bit de signe a faire sauter.

A ce que je comprend, on peut faire ceci (puisque l'hexa et le binaire, c'est un peu la même chose et la conversion en hexa se fait simplement):

Code:

---

1 2	$ printf "%X%X" $RANDOM $RANDOM 52E57884

---

et pour revenir en décimal:

Code:

---

1 2	$ echo $((16#$(printf "%X%X" $RANDOM $RANDOM))) 1685206995

---

Merci disedorgue! C'est exactement ce que je pensais mais mon neurone broutait au moment de trouver la syntaxe.
N_BaH avait déjà donné cette façon de convertir avec printf, si je ne m'abuse.

OK pour la concaténation, mais en quoi r1 + r2*2^15 = r1 + r2*32768 ne serait-il pas tout simplement suffisant pour faire ce taf ?
Plus besoin de s'occuper du bit de signe ni rien.

Citation:

---

Envoyé par Flodelarab

N_BaH avait déjà donné cette façon de convertir avec printf, si je ne m'abuse.

---

Exact, plusieurs fois même (ainsi que pour la conversion de l'heure en format hexa) :ccool:

Citation:

---

Envoyé par xflr6

OK pour la concaténation, mais en quoi r1 + r2*2^15 = r1 + r2*32768 ne serait-il pas tout simplement suffisant pour faire ce taf ?
Plus besoin de s'occuper du bit de signe ni rien.

---

Ici, je ne comprends pas tout mais si le but est de trouver le même résultat que la concat, la formule est du type:
r1*2^16 + r2 = r1*65536 + r2 que l'on peut ecrire en bash:

Code:

---

$(((r1<<16)+r2))

---

Si on doit laisser le bit manquant du quartet le plus à gauche, dans ce cas on doit bien utiliser ta formule qui en bash donnerait donc au final:

Code:

---

$(((RANDOM<<15)+RANDOM))

---

Citation:

---

Envoyé par disedorgue

Code:

---

1 2	$ printf "%X%X" $RANDOM $RANDOM 52E57884

---

et pour revenir en décimal:

Code:

---

1 2	$ echo $((16#$(printf "%X%X" $RANDOM $RANDOM))) 1685206995

---

---

Euh.... ici, il y a une grave erreur ici, la concat sera fausse si la valeur du random est inférieur à 16. donc la bonne syntaxe est:

Code:

---

echo $((16#$(printf "%02X%02X" $RANDOM $RANDOM)))

---

Euh... non mais en fait, seul la solution de xflr6 fonctionne.
Il faut le faire numériquement.

Le second random doit prendre la place des 16 bits (ce qu'il ne fera pas pour un petit nombre).
Et même si on le force, il y aura des espaces.
Et même si on remplit de 0, il y aura un bit en trop (signe).

Et si on ne fait rien, il va tirer plusieurs fois le même nombre (12 13 = 1213 = 1 213 = 121 3)

Une bonne petite galère.

Bon, donc on corrige et on synthétise:
concat textuel (comme on est sur 16 bit):

Code:

---

$ N=$((16#$(printf "%X%04X" $RANDOM $RANDOM)))

---

ou numériquement qui reste comme précédemment:
concat textuel

Code:

---

$ N=$(((RANDOM<<16)+RANDOM))

---

concat binaire:

Code:

---

$ N=$(((RANDOM<<15)+RANDOM))

---

Pour calculer le M,et Nm:

Code:

---

1 2	$ M=$(grep -c '......' dico.txt) $ Nm=$(((((1<<30)-1)/M)*M))

---

Reste plus qu'à vérifier que N ne soit pas >= Nm car sinon, on calcul un nouveau N.
Et on calcul:

Code:

---

$ nblignes=$(((N%M)+1))

---

Puis l'on récupère la ligne en conséquence par un truc du genre:

Code:

---

$ grep -m $nblignes '......' | sed '$!d'

---

Bon, bien sur, M et Nm ne se calcul qu'une seule fois sauf si le dico change.

Juste pour information, il est possible de faire une concatenation binaire sur des nombre de 15 bits en passant uniquement par la conversion de base:
Exemple par le calcul:

Code:

---

1 2	$ echo -e $(((25<<15)+33)) 819233

---

Le même par la conversion de base:

Code:

---

1 2	$ echo -e $[8#$(printf "%05o%05o\n" 25 33)] 819233

---

[CHIPOTAGE (une fois n'est pas coutume...)]

Citation:

---

Envoyé par disedorgue

En fait, selon le "pseudo-raisonnement" que je viens de donner, le meilleur choix serait:

Code:

---

($RANDOM%600)*($RANDOM%500)

---

Et qui d'ailleurs n'est autre que le modulo du nombre de mots mais répartie sur l'ensemble des randoms...

---

Citation:

---

Envoyé par xflr6

J'ai l'impression que pour le choix du mot, ce qu'il faut faire est clairement dit dans l'énoncé : multiplier 2 random d'entiers sur 16 bits pour simuler une distribution uniforme sur 32
j'ai de sérieux doutes sur l'uniformité de la distribution, rien que pour la densité des pairs et impairs, mais bon...

---

Comme l'a très justement fait remarquer xflr6, j'ai aussi de sérieux doutes quant à la parité du résultat:
La formule $RANDOM%600 fournit, en moyenne, autant d'entiers pairs que d'entiers impairs.
La formule $RANDOM%500 fournit, en moyenne, autant d'entiers pairs que d'entiers impairs.
Or (et non "hors" (comme je le vois trop souvent écrit)) il suffit que l'un des 2 entiers soit pair pour que leur produit le soit aussi!
Le produit de ces 2 entiers aléatoires est donc 3 fois plus souvent pair qu'impair!

On peut par ailleurs remarquer que, si les nombres premiers inférieurs à 400 sont susceptibles d'être tirés (lorsque l'un des 2 randoms est "1"), je ne vois pas très bien comment les nombres premiers supérieurs à 400 auraient la moindre chance d'être tirés!!!

Pour ma part (en temps que mathématicien chipoteur), je préfèrerais une formule du genre:

Code:

---

(($RANDOM%600)*600)+($RANDOM%500)

---

qui a l'avantage de permettre le tirage de tous les nombres entre 0 et 299999
tout en n'oubliant pas qu'il reste quand même un léger biais du fait que $RANDOM%600 n'est pas complètement uniforme sur [0 .. 599] (comme l'a très clairement indiqué Disedorgue post #15)
[/CHIPOTAGE]

Edit:
Oops! J'arrive un peu après la bataille (je n'avais pas vu qu'il y avait une 2ème page et j'ai donc zappé les messages #21 à #34...) :oops:

Ouf, sauvé, je ne dis pas que des bêtises :lol: