Qualité aléatoire

[invite0899d185]

Bonjour à tous,

Dans le cadre d'un projet de fin d'année, je suis en train de concevoir un générateur de nombres aléatoires quantique basé sur la réception de photons. Je suis à la fin de mon projet et j'essaie de caractériser la qualité des nombres aléatoires générés. Pour cela j'utilise les tests du NIST, les résultats sont bons, tout semble fonctionner.

Cependant quelque chose m’interpelle, dans ma séquence de "1" et de "0" générés (chaque occurrence étant indépendante), j'ai souvent de longues séquences identiques (exemple en fin de post). Alors je sais bien que notre perception de l'aléatoire est erroné, et qu'avoir une suite de plusieurs événements identiques est normale, par exemple lors de mes recherches j'ai vu que sur une suite de 100 pile ou face (ce qui revient à mon expérience de "1" ou "0") on a plus de 80% de chance d'avoir 8 fois le même résultat d'affilé. Cependant dans mon cas je trouve que ça revient quand même souvent. Pour m'en convaincre, je suis donc allé sur un site web d'une université je crois, qui a mis en ligne un générateur de nombres aléatoires quantique en ligne et en live (https://qrng.anu.edu.au/RainBin.php), là aussi on retrouve de longues séquences de même valeur, donc je ça me conforte dans l'idée que je n'ai pas de problème avec mon générateur.

Ma question est, comment peut-on justifier (mathématiquement), qu'il y ait de longues chaines de même valeur, hormis l'argument "notre perception humaine de l'aléatoire est biaisée", avec quel outils probabilistes puis-je montrer ou expliquer ce phénomène ? L'idée étant de l'inclure dans mon rapport et de préparer d'éventuelles questions à l'oral, et aussi pour ma compréhension.

Par avance merci.

Exemple de séquence :
110011111100110101111100010000 000011110010100010101100001100 000000011010000111011000100011 100001011011010011110011100001 001111001011110101001000101001 101011110111101000110101010110 010111110100100110100000000011 000011111000001010000011111111 001110001111000011101101111111 0
-----

[gg0]

Bonjour.

Un petit calcul trop simple, mais qui donne déjà une idée :
Prenons une suite de 300 bits, groupés par 3, donc 100 trios, il y a une chance sur 8 d'avoir pour un trio le résultat 111, et aussi une chance sur 8 d'avoir 000; donc en moyenne un trio sur 4 composé des mêmes bits. On peut donc s'attendre à avoir environ 25 fois la suite 111 ou la suite 000 dans des trios.
Mais attention, le dernier bit du trio précédant un 111 a aussi une chance sur 2 d'être encore un 1, et le premier du trio suivant aussi, ce qui fait apparaître des suites plus longues.

Cordialement.

[invite9dc7b526]

Tu pourrais calculer la probabilité d'observer une suite de k zéros dans une suite de n zéros ou uns et voir que pour les valeurs de n et k que tu observes cette probabilité n'est pas si petite.

[invite9dc7b526]

tu peux aussi simuler un grand nombre de suites et compter celles dans lesquelles tu observes une suite de K zéros consécutifs, pour quelques valeurs de k, et vois si ces statistiques sont compatibles avec les probabilités d'observer k zéros consécutifs.

[A voir en vidéo sur Futura]

[invite0899d185]

Merci à vous deux pour vos idées, je vais essayer de les mettre en application.

Effectivement j'ai pensé juste après avoir posté que la loi binomiale pourrait être adéquate pour calculer la probabilité de voir n occurences consécutives d'un événement pour k bits générés.

Merci !

[gg0]

Heu ... la loi binomiale ne fait pas la différence entre occurrences successives ou pas. je l'ai employé de façon très particulière, en ne traitant pas le calcul de la probabilité d'apparition de séquences de 4 ou 5 bits identique, nettement plus compliqué.
Mais un test classique est de faire tirer aléatoirement de nombreuses séquences de 4 bits et de déterminer les fréquences d'apparition de chacune des séquences possibles (1/16 à chaque fois), ou bien de 5 bits, ou, si on a le temps de 8 bits par exemple. On peut alors utiliser un test du khi-deux d'équiprobabilité.

Cordialement

[Merlin95]

Heu ... la loi binomiale ne fait pas la différence entre occurrences successives ou pas. je l'ai employé de façon très particulière, en ne traitant pas le calcul de la probabilité d'apparition de séquences de 4 ou 5 bits identique, nettement plus compliqué

HS : mais on doit pouvoir y arriver pas si difficilement grâce à des résultats de combinatoire déjà connus (par les mathématiciens ayant un bon niveau en combinatoire, pas par moi .

[gg0]

Effectivement,

les spécialistes de combinatoire connaissent ça. C'est aussi un sujet classique dans certaines prépas. Moi, j'ai toujours trouvé que ça donne des calculs qui insupportent. Donc je ne les conseille pas aux autres. Il me semble que les résultats font parties des suites de Sloane référencées sur OEIS. Mais je peux me tromper.

Cordialement.

[invite0899d185]

Bonsoir,

Effectivement la loi binomiale ne prend pas en compte l'aspect "consécutif", au temps pour moi. Cependant, je suis tombé sur cet article : https://www.mathpages.com/home/kmath341.htm, cette méthode semble prendre en compte cet aspect, par contre pour le moment je n'arrive pas à la mettre en œuvre, et c'est en cherchant des informations complémentaire sur cette méthode que je suis arrivé à la loi binomiale et ça m'a induit en erreur.

J'ai également trouvé sur cette page : http://villemin.gerard.free.fr/Wwwgv...l/PileFace.htm, la formule P = 1 - ( 1 - (1/2^n) )^k , qui semble plutôt bien fonctionner.

Merci

[invite0899d185]

Bonjour,

J'ai fais quelques tests (simulation excel) avec la seconde formule que j'ai donné dans mon précédent post, il s'avère qu'elle ne me parait fonctionner correctement, j'ai des résultats qui me paraissent pas conformes.

J'ai continué à chercher un peu, et j'ai trouvé ce cours : http://testard.frederic.pagesperso-o...tere/cours.pdf

En page 2 on peut voir un théorème (théorème 1.1.1), qui semble être ce que je cherche (et qui ressemble à celui que j'ai vu dans le lien que j'ai donné précédemment), du coup j'essaie de le mettre en oeuvre, mais c'est une fonction récursive et j'ai des difficultés.

Pour calculer une probabilité, est-ce bien n que je dois faire varier de de k+1 à n ? Quel serait le premier terme (p(k,1) ou p(k,k+1)) et comment le calculer ?

Par ailleurs si vous savez si ce théorème a un nom...

Par avance merci

[gg0]

Bonjour.

La formule P = 1 - ( 1 - (1/2^n) )^k définit exactement quelle probabilité ? En tout cas elle ne me semble pas adaptée à des calculs de répétitions de suites.

Cordialement.

[Médiat]

Bonjour,

Je veux juste attirer votre attention sur un point : suppososons que vous ayez trouvé une suite passant tous vos tests, êtes-vous sûr que la concaténation de 2 fois cette suite (qui ne peut être considérée comme aléatoire) ne passe pas les mêmes tests ?

Clifford Pickover avait étudié ce point, mais je ne sais plus dans lequel de ses livres (il utilisait une représentation graphique pour "voir" les défauts).

[gg0]

Mon message étant parti tout seul, je complète :
Pour tester la qualité d'un simulateur d'équiprobabilité, considérer la probabilité d'existence d'une suite de k 1 successifs dans un tirage de n bits est un peu léger, car le test est délicat (si cette probabilité est 10% et qu'en trois essais, ça n'est jamais arrivé, que conclure ??). Il vaut mieux tester des situations relativement fréquentes par des moyennes (on dispose d'outils statistiques efficaces pour cela).

[gg0]

Et pour répondre à la question de Médiat : Effectivement, il y a de gros pièges dans le test du hasard. En pratique, j'ai bien l'impression qu'on ne sait pas vraiment faire. Les générateurs pseudo aléatoires se contentent de suite équiréparties en bases diverses (mais faibles, pour des raisons évidentes), qui tombent dans le piège que tu signales. Il me semble que la qualité essentielle de hasard des générateurs quantiques est plus dans la théorie qui les sous-tend que dans la mesure d'un hasard difficile (par essence) à tester.
Il y a des tests très diférents des tests statistiques, avec le traitement du signal, en essayant de faire apparaître le caractère "bruit blanc" du signal produit. Mais je ne connais pas les méthodes précises.

Cordialement.

[invite0899d185]

La formule P = 1 - ( 1 - (1/2^n) )^k définit exactement quelle probabilité ?

Cette formule est censée définir la probabilité d'btenir une suite de n piles sur k lancées.

Le but n'est pas de tester la qualité de l'aléa généré, pour cela j'utilise la suite de test du NIST qui semble être l'outil adapté. Mon propos est d'essayer d'apporter une "justification mathématique" du fait d'observer des suites de même valeurs ("0" ou "1") car intuitivement on ne s'attend pas à voir ce phénomène dans une suite aléatoire, donc mon idée est de trouver un outil mathématique qui me donne d'avoir la proba d'avoir n "1" ou "0" sur k bits générés, et voir que la proba en fonction de n est plus ou moins grande, et que c'est compatible avec un échantillon que j'ai généré avec mon générateur.

J'espère que c'est assez clair...

[gg0]

"Cette formule est censée définir la probabilité d'obtenir une suite de n piles sur k lancers" ??
Prenons k=3; il y a 8 résultats possibles dont PPF, FPP et à la rigueur PPP donnent une suite de 2 pile. Soit une probabilité de 1/4 ou 3/8.
1-(1-1/2²)^3 = 1-(3/4)^3 = 1-27/64 = 37/64.

Cordialement.

[invite0899d185]

"Cette formule est censée définir la probabilité d'obtenir une suite de n piles sur k lancers" ??
Prenons k=3; il y a 8 résultats possibles dont PPF, FPP et à la rigueur PPP donnent une suite de 2 pile. Soit une probabilité de 1/4 ou 3/8.
1-(1-1/2²)^3 = 1-(3/4)^3 = 1-27/64 = 37/64.

Cordialement.

Oui c'est à peu prêt le test que j'avais fais, j'ai vu que ça concordait pas, donc j'ai abandonné cette formule.

Du coup il me reste l'option de la méthode récursive donné dans ce cours en page 2 comme j'ai mentionné plus haut : http://testard.frederic.pagesperso-o...tere/cours.pdf

Mais je ne parviens pas à la mettre en oeuvre J'essai aussi de m'inspirer de ça http://www.les-mathematiques.net/pho...108453,1108493

Mais en vain aussi pour le moment. Je ne vois pas comment calculer le 1er terme pour ensuite calculer les suivants....

[invite9dc7b526]

Les tests de qualité des générateurs de nombres aléatoires ne prouvent jamais que les suites engendrées par le générateur ont toutes les bonne propriétés, mais seulement qu'elles n'ont pas certaines mauvaises propriétés. En fonction de l'usage qu'on va faire des ces suites on peut choisir un générateur pas trop mauvais.

Il y a un exemple célèbre avec le générateur RAND de FORTRAN : si on utilise les nombres aléatoires un par un ils ont de "bonnes" propriétés, mais si on veut des vecteurs aléatoires et que pour ce faire on tire des suites de k nombres aléatoires consécutifs issus de RAND, les vecteurs sont dans un petit nombre d'hyperplans parallèles, et un ensemble de ces vecteurs a un aspect très peu aléatoire.

[Verdurin]

En fait il est totalement impossible de savoir si une suite donnée est réellement aléatoire.
Mais ici le problème est un peu différent.

On a un mécanisme qui produit des bits avec, j'imagine, des raisons théoriques de croire qu'ils sont aléatoires.
Un test possible est effectivement de regarder si il y a assez de sous-suites constantes dans une suite de longueur N.

Par exemple 38% des suites aléatoires de longueur 1000 contienne une sous-suite constante de longueur supérieure ou égale à 12⁽¹⁾.
Ce qui n'est pas le cas si on copie deux fois une suite aléatoire de longueur 500.

_{(1) sauf erreur de ma part.}

[gg0]

Oui, mais s'il y a seulement 35% de suites de longueur au moins 12 dans un test sur 20 suites de 1000 bits, que fait-on ? On rejette, ou on dit que ce n'est pas grave ?

Cordialement.

[Verdurin]

@gg0
on fait un test sur une loi binomiale de paramètres 20 et 0,38.
Et on se rend compte que 0,35 fait partie des résultats vraisemblables.
On peux même dire que 7/20 est à peu près égal à 0,38 dans ce cadre.

[Médiat]

Par exemple 38% des suites aléatoires de longueur 1000 contienne une sous-suite constante de longueur supérieure ou égale à 12⁽¹⁾.
Ce qui n'est pas le cas si on copie deux fois une suite aléatoire de longueur 500.

1) Pourquoi
2) Le fond du problème n'est pas là (comment reconnait-on qu'une suite a été dédoublé en prenant en compte toutes les méthodes de fusion de 2 suites)
3) Connaissez-vous une méthode qui reconnaisse qu'une suite est aléatoire ou non, quelque soit sa longueur ? Autrement dit connaissez-vous une définition mathématique incontestable de suite aléatoire ?

[Verdurin]

Je cite juste le début de mon premier message sur ce fil :

En fait il est totalement impossible de savoir si une suite donnée est réellement aléatoire.

[invite6c250b59]

3) Connaissez-vous une méthode qui reconnaisse qu'une suite est aléatoire ou non, quelque soit sa longueur ? Autrement dit connaissez-vous une définition mathématique incontestable de suite aléatoire ?

Je ne comprend pas l’équivalence entre ces deux questions. Nous n’avons pas de méthode générale qui reconnaisse si une machine de Turing s’arrête ou non. Est-ce que cela signifie que le problème de l’arrêt a une définition mathématique contestable?

[Médiat]

Je ne comprend pas l’équivalence entre ces deux questions. Nous n’avons pas de méthode générale qui reconnaisse si une machine de Turing s’arrête ou non. Est-ce que cela signifie que le problème de l’arrêt a une définition mathématique contestable?

Il me semble que si on connaît une méthode pour reconnaître qu'une suite est ou non aléatoire, il faut une définition de suite aléatoire

C'est une implication pas une équivalence, et donc demander la méthode pour reconnaître revient à demander la définition (entre autres)

[gg0]

Heu ... Jiav,

même si une définition ne donne pas une méthode pour vérifier, le problème ici est la définition de "suite aléatoire". Le "autrement dit" n'est pas ici une traduction d'une équivalence (Médiat connaît le sens du mot), mais le cœur du problème.

Cordialement.

[invite9dc7b526]

Heu... la question concerne les suites de nombres pseudo-aléatoires, pas aléatoires. La question de savoir si elles sont aléatoires ne se pose pas: elles ne le sont jamais. Si une telle suite (disons de nombres entiers entre 0 et 2^64) ne dépend pas d'entrées extérieures elle est nécessairement cyclique puisque la machine étant finie elle se retrouve tôt ou tard dans l'état initial.

[invite6c250b59]

une implication pas une équivalence, et donc demander la méthode pour reconnaître revient à demander la définition (entre autres)

Ah ok merci (et à gg0). Est-ce que “est aleatoire ce qui est incompressible” répond à cette demande de définition?

Heu... la question concerne les suites de nombres pseudo-aléatoires, pas aléatoires. La question de savoir si elles sont aléatoires ne se pose pas: elles ne le sont jamais. Si une telle suite (disons de nombres entiers entre 0 et 2^64) ne dépend pas d'entrées extérieures elle est nécessairement cyclique puisque la machine étant finie elle se retrouve tôt ou tard dans l'état initial.

Ta réponse suppose que les suites en question sont plus longues que la mémoire de l’ordinateur qui les produit.

[Verdurin]

Pour savoir si une suite est aléatoire il est inutile de regarder la suite.
Il suffit de savoir comment elle est produite.

Par exemple la suite formée par les numéros de la première boule sortie à chaque tirage du loto est une suite aléatoire.
Sauf si on se place du point de vue du démon de Laplace, mais là on est dans la métaphysique.

Maintenant le problème de JulesMhz, si je l'ai bien compris, est :
«J'ai un générateur que je pense ( pour des raisons physiques ) aléatoire. Est-ce bien le cas ?»
C'est ici que les tests statistiques entre en jeu.

[Verdurin]

Pour donner un exemple.
La suite 010000000110 est aléatoire : je l'ai obtenue en lançant quatre fois un dé à 8 faces, avec un codage évident.

On ne peut certainement pas le savoir en regardant la suite.