Binarisation d'une séquence de nombres aléatoires

Bien le bonjour à tous,

Je m'étonne de n'avoir rien trouvé de concluant sur ce sujet, mais enfin bon...

Pour l'étude d'un générateur de nombres aléatoires, j'ai besoin, de binariser une séquence de nombres obtenus (transformer la séquence en suite de 0 et 1 quoi...).

Je précise que je ne sais rien du générateur, je suppose juste que celui-ci est à peu près aléatoire, et les nombres obtenus appartiennent à l'intervalle [0,1[, comme 0,3986675887...

A priori, pour binariser la séquence, il me suffirait juste d'affecter 0 aux nombres dont la première décimale est paire, 1 aux autres...
Ou bien encore les nombres < 0,5 envoyés sur 0 et ceux >= 0,5 envoyé sur 1Mais ces méthodes ne me plaisent pas :

Imaginons un générateur dont la probabilté d'obtenir un nombres compris entre 0 et 0,1 soit la même que celle d'obtenir un nombre compris entre 0,9 et 1, mais que celles-ci soient plus forte que celle d'obtenir un nombre entre 0,1 et 0,9.

Ma méthode de binarisation gommerais ce défaut et je pourrais arriver à conclure que ce générateur produit une séquence aléatoire !

Comment donc trouver une méthode qui soit relativement "neutre" par rapport aux résultats, et qui permette de laisser passer les erreurs (où du moins le plus d'erreurs possibles) ???

Je vous remercie par avance de toute l'aide que vous pourrez m'apporter :ccool:

Citation:

---

Imaginons un générateur dont la probabilté d'obtenir un nombres compris entre 0 et 0,1 soit la même que celle d'obtenir un nombre compris entre 0,9 et 1, mais que celles-ci soient plus forte que celle d'obtenir un nombre entre 0,1 et 0,9.

---

Il s'agit à mon avis d'un problème mal posé.
Soit le générateur d'origine est uniforme, soit il ne l'est pas.
S'il l'est la probabilité pour un tirage d'être entre 0 et 0.1 doit être environ 1/10, de même que celle d'être entre 0.9 et 1, mais la proba d'être entre 0.1 et 0.9 devrait être de 8/10 et ne peut en aucun cas être sensiblement égale aux deux autres. Nous partons donc d'une 'supposition' forcément vraie.
Il semble que le but de cette 'binarisation' soit de faire un pile ou face équitable. Si c'est le cas, il est préférable à mon avis de partir avec des suites pseudo-aléatoires d'entiers dont on peut 'mesurer' le défaut voir par exemple:
http://fr.wikipedia.org/wiki/G%C3%A9...l%C3%A9atoires

Merci de ta réponse ;)

Je cherche à VERIFIER si mon générateur est aléatoire ou non.

Les tests que je compte mettre en oeuvre sont des tests qui s'applique sur des sorties binaires. Or mon générateur à tester renvoi des sorties non-binaires.

En faisant une mauvaise binarisation, j'ai peur de tester autre chose que ce que je veux. Dans mes exemples je teste soit la distribution des nombres paires ou impairs, soit la distribution par rapport à 0,5.

Et partant de la, je ne peux rien dire quand à la réelle qualité de mon générateur, et des nombres décimaux qu'il renvoi.

D'ou comment faire pour que la binarisation réflète les défauts du générateurs.

A moins que ce soit impossible, du fait que la binarisation n'est pas bijective ?

Merci encore :)

Citation:

---

Envoyé par cs_ntd

Les tests que je compte mettre en oeuvre sont des tests qui s'applique sur des sorties binaires. Or mon générateur à tester renvoi des sorties non-binaires.

---

Un type de donnée qui n'est pas représenté en binaire ? sur un ordinateur ? 8O

Arf...
Si bien sur pseudocode :aie:...

Nous somme bien d'accord que les nombres sont représenté en machine sous leur forme binaire, mais ils sont obtenus sous une forme décimale (faut imaginer une série de donnée sous excel ou autre hein ^^).

Ce que je veux c'est trouver une méthode de représentation binaire de la séquence de nombres décimaux obtenus, qui ne fausse pas cette séquence.
C'est à dire que si ma séquence de nombres décimaux présente un certaine périodicité par exemple, cela doit pouvoir se retrouver dans la séquence binaire...
La binarisation doit gommer au minimum (le mieux étant pas du tout bien sûr) les imperfections de ma séquence...

Citation:

---

Envoyé par cs_ntd

Ce que je veux c'est trouver une méthode de représentation binaire de la séquence de nombres décimaux obtenus, qui ne fausse pas cette séquence.
C'est à dire que si ma séquence de nombres décimaux présente un certaine périodicité par exemple, cela doit pouvoir se retrouver dans la séquence binaire...
La binarisation doit gommer au minimum (le mieux étant pas du tout bien sûr) les imperfections de ma séquence...

---

Pourquoi faire intervenir la "binarisation" dans ton problème. :koi:

De toutes façons, représenter une séquence de chiffres (0...9) sous forme de séquence binaire, en total bijection, nécessiterait de faire des paquets de 3,32192809... bits. :aie:

Enfin, mettons que tu as cette fameuse séquence binaire, comment l'utiliserais tu pour en déduire que ton générateur est "aléatoire" ?

Citation:

---

Je cherche à VERIFIER si mon générateur est aléatoire ou non.

---

J'ai la réponse!
Il ne l'est pas...
car aucun ne l'est.
On ne sait pas produire le hasard en machine. On sait seulement produire des séries de nombres pseudo aléatoires par un des algorithmes que tu trouveras sur le wiki.
Maintenant si tu veux tester la qualité d'un générateur pseudo aléatoire 'ready-made' devant générer une distribution de tel ou tel type (uniforme -Gauss- Poisson, etc...) il existe un outil statistique pour cela c'est le test dit du Khi-deux.
http://fr.wikipedia.org/wiki/Test_du_%CF%87%C2%B2
Ce test de permettra de valider ton hypothèse (par exemple d'uniformité) avec un certain seuil de tolérance prédéfini. Cette binarisation ne me semble d'aucune utilité.

Citation:

---

Envoyé par pseudocode

représenter une séquence de chiffres (0...9) sous forme de séquence binaire, en total bijection, nécessiterait de faire des paquets de 3,32192809... bits. :aie:

---

Moué ou alors on pourrait imaginer, comme un nombre en info n'a pas un developpement décimal infinis, de mettre a la suite la valeur binaire de chaque chiffre, m'enfin bon... je suis pas sur que ça sois très représentatif de ma séquence décimale...

Citation:

---

Envoyé par pseudocode

Enfin, mettons que tu as cette fameuse séquence binaire, comment l'utiliserais tu pour en déduire que ton générateur est "aléatoire"

---

Ya tout une batterie de tests... Equiprobabilité d'appartion des 0 et des 1 sur la séquence entière, sur plusieurs morceaux de la séquence, nombres de "run" (nombres de 0 ou de 1 consécutif), rang de matrices binaire construite avec la séquence binaire, tests de "compressibilité" (compression possible sans perte de données)......

Citation:

---

Envoyé par Zavonen

J'ai la réponse!
Il ne l'est pas...
car aucun ne l'est.

---

:aie: Oué désolé j'ai eu la flemme de mettre "pseudo" devant chaque aléatoire x)

Ceci dit, le test du chi² n'ets pas suffisant en soit si je me rappelle bien, on ne peut pas vérifer l'existence de période dans la séquence elle même il me semble... On ne test que la fréquence d'apparition de certaines valeurs.

Par exemple on peut montrer qu'en prenant une décimale de Pi au hasard, tous les chiffres de 0 à 9 ont la même chance d'apparaitre. Mais même si Pi s'écrivait 3,45678901234567890 on aurait trouvé un résultat positif au test... Me trompe-je ?

De plus il me semble que le test du chi² est plus fait pour les valeurs discrètes que les valeurs continue comme moi...

Merci encore à vous deux :)

Citation:

---

Envoyé par cs_ntd

Moué ou alors on pourrait imaginer, comme un nombre en info n'a pas un developpement décimal infinis, de mettre a la suite la valeur binaire de chaque chiffre, m'enfin bon... je suis pas sur que ça sois très représentatif de ma séquence décimale...

---

et inversement... un motif dans une séquence binaire ne signifie rien en base dix: 10110011100011110000 (b2) == 735472 (b10)

Citation:

---

Ya tout une batterie de tests... Equiprobabilité d'appartion des 0 et des 1 sur la séquence entière, sur plusieurs morceaux de la séquence, nombres de "run" (nombres de 0 ou de 1 consécutif), rang de matrices binaire construite avec la séquence binaire, tests de "compressibilité" (compression possible sans perte de données)......

---

ah... les tests diehard... Et qu'est-ce qui empêche de faire ces tests sur des séquences de 10 symboles, au lieu de 2 ?

Ah! je ne savais pas qu'ils avaient un nom ! en réalité j'ai suivis les recomandations du NIST (http://csrc.nist.gov/publications/ni...800-22rev1.pdf attention pdf de 7Mo en anglais).

Ceci dit, je ne comprend pas ce que tu veux dire par

Citation:

---

Et qu'est-ce qui empêche de faire ces tests sur des séquences de 10 symboles, au lieu de 2 ?

---

Apparement certains de ces test se font sur des séries de nombres entre [0,1[ (ce qui me convient parfaitement), mais les autres sur des séquences binaires.... D'où mon problème...

Aurais-tu par hasard de la doc à ce sujet ? je ne trouve rien d'autre qu'une vague explication sur wikipédia, et des tas de liens vers un CD-ROM permettant d'appliquer les tests... Je ne peux pas vraiment utiliser ce CD-ROM étant donné que ce que je fais est dans le cadre d'un projet scolaire, donc je peux pas me contenter de dire : "j'ai utilisé un CD-ROM je sais pas ce qu'il fait mais il teste mon générateur la" :aie:

Mais a priori, j'ai toujours le problème de la binarisation........

Edit: Je crois que je vais re-détailler ce que je veux...
J'ai en sortie de générateur la séquence :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

... 0,294360294 0,323349156 0,046526746 0,831296434 0,677631175 0,748389738 0,341808364 0,77219635 0,412166183 0,518728289 0,338760577 0,669503571 0,804110788 ...

---

Et je souhaite déterminer si cette séquence est aléatoire ou non... Si je veux appliquer les tests du nist, ou ceux de diehard, qui ont l'air assez similaires, j'ai besoin d'obtenir une séquence binaire, comme

Code:

---

...11001110101001100110100011...

---

qui soit représentative des défauts de ma sortie décimale, et sur laquelle je pourrais appliquer ces tests...
C'est peut-être imossible je ne sais pas...
En réalité je préfèrerais faire des tests directement sur ma sortie décimale, mais le problème est que je n'en trouve pas des tests..........

A la limite il y aurait bien le test du chi², en vérifiant que mon générateur passe les tests lorsqu'on fait tendre vers 0 l'intervalle de discrétisation, mais ça reste un peu de l'invention et je ne sais pas trop si ça "prouve" ce que je veux... Et je ne sais pas si les tests du chi² sont suffisants...

Je suis un peu coincé :x et donc encore merci pour votre aide :ccool:

Citation:

---

Envoyé par cs_ntd

Si je veux appliquer les tests du nist, ou ceux de diehard, qui ont l'air assez similaires, j'ai besoin d'obtenir une séquence binaire, comme

Code:

---

...11001110101001100110100011...

---

qui soit représentative des défauts de ma sortie décimale, et sur laquelle je pourrais appliquer ces tests...
C'est peut-être imossible je ne sais pas...

---

Ton convertisseur "décimal/binaire" va forcément modifier la séquence d'origine, et tu vas devoir prouver que cette modification ne fausse pas le test.

Il te faut donc analyser le test et construire un convertisseur décimal/binaire spécialement adapté pour ce test. Ou alors, ce que je trouve plu simple, modifier le test pour l'appliquer sur la base 10.

Autre solution : virer la partie décimale et convertir binaire en passant par l'octal :
0,294360294 (Réel)
=> 294360294 (b10, 9 chiffres max)
=> 2142712346 (b8, 10 chiffres max)
=> 0001 0001 1000 1011 1001 0100 1110 0110 (b2, 30 bits max).

Les deux bits supérieurs (30 et 31) sont donc à exclure de ta binarisation, car non significatifs et ils vont donc perturber ton analyse.

Salut à tous et merci de vous occuper encore de moi :mouarf:

Désolé pour le retard, j'été pas trop là ces jours-ci :?.

Donc oui Mac LAK, c'est pas une mauvaise idée, les seuls trucs qui me dérangent, c'est que 1) je comprend pas ce que tu fais :aie:
2) je ne cherche pas à vérifier la qualité du développement décimal, mais la qualité de plusieurs nombres décimaux.

Si je suis ta méthode, j'aurais donc plein de morceaux du genre 0001 0001 1000 1011 1001 0100 1110 0110, mais qu'en faire en suite ?

Pourquoi pas les mettres bout a bout... Mais je ne sais plus trop ce que ça représente...

Dans le même genre, il existe l'expansion binaire (c'est ptet le même truc en fait :roll:) Je vais peut-être partir sur un des 2 trucs alors...

Sinon pseudocode, l'idée de modifier les tests :lol: ça risque d'être un peu chaud, les stats c'est pas vraiment mon domaine hein ^^. Et puis même si les tests ne sont pas très complexes à programmer, ils font intervenir du materiel assez conséquend question formule (genre la fonction d'erreur des trucs comme ça), et à moins de bien comprendre comment et pourquoi ça marche (ce qui n'est pas mon cas :oops:), il n'est pas vraiment question que je touche à ça !

Donc Mac LAK si tu pouvais m'expliquer ce que tu fais c'est super :ccool:, et si quelqu'un à encore une idée il est le bienvenu :)

Citation:

---

Envoyé par cs_ntd

Donc oui Mac LAK, c'est pas une mauvaise idée, les seuls trucs qui me dérangent, c'est que 1) je comprend pas ce que tu fais :aie:
2) je ne cherche pas à vérifier la qualité du développement décimal, mais la qualité de plusieurs nombres décimaux.

Si je suis ta méthode, j'aurais donc plein de morceaux du genre 0001 0001 1000 1011 1001 0100 1110 0110, mais qu'en faire en suite ?

---

Ça, j'en sais rien, c'est toi qui disait avoir besoin d'une séquence binaire pour tes tests !!! :mrgreen:

Mais effectivement, tu vas avoir 30 bits émis pour chaque nombre pseudo-aléatoire généré, mais le résultat dépend de tes algos de tests, que je ne connais pas : je ne peux donc pas savoir si ça conviendra exactement à ton besoin.

Par contre, ce qui est sûr, c'est que la méthode que je t'indique ne produira normalement pas de bits parasites.

Le "truc", c'est qu'un chiffre décimal (0..9) occupe, comme il a été dit, 3.3 bits environ, ce qui n'est pas pratique. Par contre, en base octale (0..7), chaque chiffre occupe très exactement 3 bits.
En éliminant la virgule dans tes nombres générés (=> tu obtiens un entier), et en convertissant le chiffre maximal en octal (999.999.999 (b10) => 7.346.544.777 (b8)), tu observes deux choses :
1) Le premier chiffre octal de poids fort est le 7 : on parcours donc bien l'intégralité de la plage 0..7 pour ce chiffre, il n'y a pas (trop) de "scories".
2) On ne dépasse pas 10 chiffres en octal, d'où les 30 bits (10 x 3).

Ce serait parfait si l'on avait comme plage octale 0 => 7.777.777.777, ce qui correspond à 1.073.741.823 (b10), mais ce n'est pas le cas : il faudra faire avec cette légère approximation, ou trouver une meilleure binarisation.

Re,

Ok ! j'ai compris ce que tu faisais ^^ merci :)

Bon il va donc falloir que je réflechisse à ce qui a le plus de sens. Je pense que je vais effectivement pouvoir me débrouiller avec plusieurs séquences de 0-1, et je pense que cela reste relativement représentatif de ma sortie décimale.
Soit l'expansion binaire, soit la conversion décimal->octal->binaire je crois que je vais voir en fonction des résultats :aie:

Bien donc merci à tous :)

Edit : J'ai finis par trouver des tests valables pour des valeurs continues : http://www.math-info.univ-paris5.fr/...urs/ts/ts.html