générer un nombre/suite aléatoire

[RandomBanana]

Bonsoir,

Il y a des nuits comme ça, ou des questions existentielles me turlupinent...


Alors celle du soir, est dans le titre : est il possible de créer un algorithme qui génère une suite de nombre VRAIMENT aléatoire?

Après avoir fais quelques recherches, j'ai vu qu'en informatique, la plupart du temps, on se contentait du pseudo-aléatoire, mais je suis vraiment curieux de savoir si (au moins théoriquement) l'aléatoire existe en informatique.

Par ailleurs, si vous avez des articles intéressants sur la question, n'hésitez pas à les partager avec moi : même en étant un total noob en informatique, je suis tellement curieux d'avoir une réponse que je ferais l'effort de comprendre



Merci d'éclairer ma lanterne !
Ban'
-----

[CM63]

Bonjour,

Effectivement les algorithmes sur ordinateurs vont fournir une suite de nombres "pseudo-aléatoires", c'est-à-dire que si je fais un nouveau tirage exactement dans les mêmes conditions, je vais toujours ressortir la même suite. Mais tout est dans le "exactement". Ces algorithmes utilisent en générale une "racine", c'est-à-dire un nombre (ou tout autre information) utilisée comme point de départ. Si on calcule cette racine en fonction d'une information qui change tout le temps, comme par exemple l'heure-date: 2017-04-15-10:23 , alors on sera sur de sortir une suite différente à chaque nouveau tirage.

[pm42]

En complément à la réponse de CM63, quand on a besoin de vrai aléatoire, on utilise du matériel spécialisé. Voir par ex https://en.wikipedia.org/wiki/Hardwa...mber_generator

[Dlzlogic]

Bonjour,
D'abord, une parte de la réponse, l'explication de CM63 me plait bien. La suite est dite "pseudo aléatoire" parce que elle a un cycle fini. Les cycles habituels sont de l'ordre de 40000, ce qui me semble déjà pas mal. Avec les nombres de Mersenne on peut avoir des cycles beaucoup plus grands.

Par contre, l'expression "vrai aléatoire" me gène. J'ai parcouru rapidement le début de l'article et il me semble bien que cette méthode donne un résultat conforme aux lois du hasard, s'est à dire que la loi des grands nombres et le TCL s'appliquent. C'est d'ailleurs assez facile à vérifier.
En d'autres termes, en utilisant un très grand cycle, le résultat ne doit pas être très différent.

Pour être complet, j'ai dans ma machine un module produisant théoriquement une suite aléatoire. Ce module a été disponible un moment sur le net, il est possible qu'il ait répondu à un besoin au moment de l'autorisation des jeux (poker) en ligne.

[A voir en vidéo sur Futura]

[LeMulet]

Sinon, il y a aussi un site qui fournit des nombres aléatoires (presque parfaits, je dis bien presque...)

What's this fuss about true randomness?

Perhaps you have wondered how predictable machines like computers can generate randomness. In reality, most random numbers used in computer programs are pseudo-random, which means they are generated in a predictable fashion using a mathematical formula. This is fine for many purposes, but it may not be random in the way you expect if you're used to dice rolls and lottery drawings.

RANDOM.ORG offers true random numbers to anyone on the Internet. The randomness comes from atmospheric noise, which for many purposes is better than the pseudo-random number algorithms typically used in computer programs. People use RANDOM.ORG for holding drawings, lotteries and sweepstakes, to drive online games, for scientific applications and for art and music. The service has existed since 1998 and was built by Dr Mads Haahr of the School of Computer Science and Statistics at Trinity College, Dublin in Ireland. Today, RANDOM.ORG is operated by Randomness and Integrity Services Ltd.

As of today, RANDOM.ORG has generated 1.46 trillion random bits for the Internet community.

https://www.random.org/

[bon prof math]

bonsoir,

Les cycles habituels sont de l'ordre de 40000

c'est donc que tous les algos que je connais sont inhabituels... (ils ont des cycles bien plus grands, aussi grand que l'on veut en théorie pour certains)

la loi des grands nombres et le TCL s'appliquent.

ces deux théorèmes ont essentiellement besoin de variables indépendantes de même loi de probabilité...

j'ai dans ma machine un module produisant théoriquement une suite aléatoire.

... et tu es capable de prouver que les tirages sont indépendants ? Tu as une preuve mathématique ou bien c'est une affirme seulement expérimentale ?

[Dlzlogic]

ces deux théorèmes ont essentiellement besoin de variables indépendantes de même loi de probabilité...

Ben oui, c'est ce qui est écrit dans la doc citée par LeMulet.

Citation Envoyé par Dlzlogic Voir le message
j'ai dans ma machine un module produisant théoriquement une suite aléatoire.

... et tu es capable de prouver que les tirages sont indépendants ? Tu as une preuve mathématique ou bien c'est une affirme seulement expérimentale ?

Ben, justement non. Ce module met en œuvre un algorithme qui respecte strictement, c'est dire à tout moment, le TCL. Ce qui contredit l'expérience faite par LeJeu, il y a quelques années. Ce qui a permis à Nuage de dire que l'expérience de LeJeu n'était pas valable, donc, que j'avais tort. Le gag de l'histoire est que si on utilise ce "générateur" autrement que prévu, alors c'est la cata. Pour info, ce module n'est plus disponible sur le net.
Tu parles un peu légèrement de preuve mathématique. C'est à toi de définir le protocole.

[AbA2L]

En complément à la réponse de CM63, quand on a besoin de vrai aléatoire, on utilise du matériel spécialisé. Voir par ex https://en.wikipedia.org/wiki/Hardwa...mber_generator

Je me souvien que tous les ordinateurs modérnes y sonts équipées.

[Dlzlogic]

Il me semble nécessaire de préciser formellement ce qu'est le "vrai aléatoire", indépendamment de ce qui a été dit sur le "pseudo-aléatoire", point sur lequel (presque) tout le monde est d'accord.

[pm42]

Le primo-posteur n'étant pas revenu, je ne commenterais pas plus que ça le nawak récurrent des suspects habituels mais disons que comme d'hab, c'est hilarant.

[bon prof math]

Tu parles un peu légèrement de preuve mathématique. C'est à toi de définir le protocole.

je te laisse faire des études de mathématique pour mieux appréhender la notion de preuve.

Ce module met en œuvre un algorithme qui respecte strictement, c'est dire à tout moment, le TCL.

Le TCL est un théorème, donc il est prouvé mathématiquement.
Que signifie l'expression << un algorithme qui respecte un théorème >> ? ...ou a contrario, << un algorithme qui ne respecte pas un théorème >> ?

[CM63]

Tient , un petit nouveau dans le nawak

[minushabens]

Il me semble nécessaire de préciser formellement ce qu'est le "vrai aléatoire"

ce n'est pas si évident en effet. Les dispositifs fondés sur l'agitation thermique sont supposés fournir de l'aléatoire "vrai" mais au fond ce n'est qu'une hypothèse de la physique qui n'a aucune valeur en mathématiques. Heureusement les générateurs de nombres pseudo-aléatoires (qui en fait ne sont pas du tout aléatoires) ne sont pas si mauvais.

[pm42]

ce n'est pas si évident en effet. Les dispositifs fondés sur l'agitation thermique sont supposés fournir de l'aléatoire "vrai" mais au fond ce n'est qu'une hypothèse de la physique qui n'a aucune valeur en mathématiques. Heureusement les générateurs de nombres pseudo-aléatoires (qui en fait ne sont pas du tout aléatoires) ne sont pas si mauvais.

Je propose que dlzlogic et toi nous fassiez un petit article pour expliquer les limites de tout ça, la définition correcte du vrai aléatoire et tout.
Il devrait facilement être accepté par Nature et faire la couverture et après, on pourra en parler ici.

[Dlzlogic]

Bonjour minushabens,
Je pose ma question autrement
1- Si on peut parler de "vrai" aléatoire, c'est qu'il existe(rait) un aléatoire "faux". Oui ou non ?
2- Soit une liste donnée, provenant d'un générateur X comment savoir si elle est "bonne" ou "mauvaise" ?
3- Quelles lois devraient satisfaire une expérience (ie générateur) aléatoire ?

@PM42, j'ai cité bon nombre de fois deux livres (M. Rouaud, J. Harthong), leurs approches sont différentes, mais comme ce sont des livres sérieux, ils se complètent. Si tu lis cela, ce sera déjà un bon début. On m'a donne le nom d'un troisième livre, mais je me souviens seulement que c'est un cours de l'Ecole Nationale du Pétrole. J'ai aussi donné un lien sur mon cours, écrit par JJ Levallois, je peux le redonner. Mais dans tous les cas, il s'agit de probabilités et non de génération de nombre aléatoire.

[minushabens]

@pm42: pourquoi persifles-tu? Il y a une définition mathématique de ce que c'est qu'une suite de variables aléatoires i.i.d. et cette définition ne dit rien de comment obtenir pratiquement une réalisation d'une telle suite. La Physique modélise par ailleurs un ensemble de particules (des molécules par exemple) de façon stochastique (le mouvement brownien et toussa) et accepter qu'une suite de mesures d'un système matériel relève du "vrai" hasard est un acte de foi. C'est ce que je voulais dire.

[feanorel]

Bonjour minushabens,
Je pose ma question autrement
1- Si on peut parler de "vrai" aléatoire, c'est qu'il existe(rait) un aléatoire "faux". Oui ou non ?
2- Soit une liste donnée, provenant d'un générateur X comment savoir si elle est "bonne" ou "mauvaise" ?
3- Quelles lois devraient satisfaire une expérience (ie générateur) aléatoire ?

Un petit document en Français qui résume le sujet : http://math.univ-lyon1.fr/~jberard/genunif-www.pdf
En gros il faut distinguer :
- les suites issues de générateurs pseudo aléatoires, qui sont donc parfaitement déterministe dès lors que l'on connait le générateur et la graine. Cela permet de produire des résultats reproducibles.
- les suites issues de phénomènes physiques. On peut sans doute remonter à une modélisation déterministe dans certains cas, mais tellement sensible aux données initiales (qui sont généralement inaccessible) que l'on préfère les voir comme des suites purement aléatoires.
- des suites réellement aléatoire (et aujourd'hui on ne saurait faire cela qu'à l'aide de la MQ, en la supposant valide...)

Dans tous les cas il faut vérifier que les suites que l'on considère ont des propriétés proche de celle qu'aurait une suite aléatoire i.i.d théorique. On peut voir dans le document quelques tests empiriques et théoriques.

@PM42, j'ai cité bon nombre de fois deux livres (M. Rouaud, J. Harthong), leurs approches sont différentes, mais comme ce sont des livres sérieux, ils se complètent. Si tu lis cela, ce sera déjà un bon début. On m'a donne le nom d'un troisième livre, mais je me souviens seulement que c'est un cours de l'Ecole Nationale du Pétrole. J'ai aussi donné un lien sur mon cours, écrit par JJ Levallois, je peux le redonner. Mais dans tous les cas, il s'agit de probabilités et non de génération de nombre aléatoire.

Rappelons juste que les deux livres cité sont des livres plutôt de vulgarisation, l'un d'entre eux ne donnant même la définition d'espérance qu'en note de bas de page.

[RandomBanana]

Le primo-posteur n'étant pas revenu, je ne commenterais pas plus que ça le nawak récurrent des suspects habituels mais disons que comme d'hab, c'est hilarant.

Ce qui ne veut pas dire que je ne lis pas les réponses que l'on me donne

Merci pour vos réponses en tout cas, j'ai un peu de temps cette cette après midi je vais lire plus en détails vos liens !

Bon dimanche.

[Dlzlogic]

Pour info, l'adresse mail de l'auteur du cours mis en lien par feanorel n'est pas valide.
Ce qui signifie que l'auteur n'appartient plus à l'université qui héberge ce document. (vérification faite).

[bon prof math]

Dlzlogic,
le TCL est un théorème, donc il est prouvé mathématiquement.
Que signifie l'expression << un algorithme qui respecte un théorème >> ? ...ou a contrario, << un algorithme qui ne respecte pas un théorème >> ?

(Merci de ne pas me répondre des absurdités incompréhensibles en message privé)

[Dlzlogic]

@ Bon...
C'est assez curieux qu'un mathématicien de ton niveau ne comprenne pas ce que j'ai dit.
Un théorème est constitué d'une hypothèse et d'une affirmation. Parallèlement, ce théorème est démontré, mais ce n'est pas le sujet.
Tu connais le TCL, donc, pas la peine de le citer. L'hypothèse est une expérience répétée et de même loi. La conclusion est les écarts à la moyenne suivent la loi normale.
Il s'agit en l'occurrence de l'utilisation d'un générateur de nombres aléatoires. Si ce générateur est correct, c'est à dire que les résultats suivent la même loi, alors on est dans le contexte du TCL et on peut vérifier que les écarts à la moyenne suivent la loi normale. Il parait évident que la correspondance ne peut pas être exacte, dans le cas d'une expérience honnête.
Le générateur auquel j'ai fait allusion donnait (il n'est plus disponible) un résultat strictement et à tout moment conforme au TCL, ce qui est une anomalie. En effet différents tests ont montré que l'écart entre la répartition observée et la répartition théorique est de l'ordre de 2%.
Pour revenir au sujet posé à l'origine, si on est dans un contexte non sensible, alors les générateurs "ordinaires" sont parfaitement satisfaisants.
Si on est dans un contexte sensible, type cryptographie, je ne suis pas compétent et je doute que les gens compétents exposent leur méthode.
Le cours qui a été cité insiste grossièrement sur la graine. A mon avis c'est un détournement du vrai problème. (Peut-être doit-on dire "biais" à la place de détournement).

[pm42]

C'est assez curieux qu'un mathématicien de ton niveau ne comprenne pas ce que j'ai dit.

Oh je suis sur qu'il a parfaitement compris ce que tu as dit. Il pointait juste le fait que cela ne signifie pas grand chose.
Petit exemple :

Le générateur auquel j'ai fait allusion donnait (il n'est plus disponible) un résultat strictement et à tout moment conforme au TCL, ce qui est une anomalie.

"Conforme" ne veut rien dire : le TCL parle de limite. Et si tu tires 3 nombres aléatoires, tu vas avoir du mal à construire une gaussienne.

En effet différents tests ont montré que l'écart entre la répartition observée et la répartition théorique est de l'ordre de 2%.

Soit cela ne veut rien dire, soit c'est délirant. Pour tout tirage aléatoire, on va observer la répartition théorique "à la limite", pas une différence de 2%. Et si on parle "en cours de tirage", on peut observer n'importe quel écart.

Bref, le problème, c'est comme que tu ne comprends pas le concept de limite, ce qu'on avait déjà constaté dans un fil récent...

[Dlzlogic]

Bonjour PM42,
Je résume le TCL : Une série d'évènements aléatoires de même loi converge vers la loi normale. Bon OUI ou NON ?
Si c'est pas bon, merci de corriger.

L'exemple des 3 nombres, le TCL dit que la valeur la plus probable est la moyenne arithmétique, puis il donne le calcul de l'écart-type.
Je n'ai jamais dit qu'on pouvait "construire une gaussienne". Où as-tu lu ça ?

Citation Envoyé par Dlzlogic Voir le message
Le générateur auquel j'ai fait allusion donnait (il n'est plus disponible) un résultat strictement et à tout moment conforme au TCL, ce qui est une anomalie.
"Conforme" ne veut rien dire : le TCL parle de limite. Et si tu tires 3 nombres aléatoires, tu vas avoir du mal à construire une gaussienne.

Oui, peut-être que à la place de "conforme" j'airais pu dire "qui respecte".

Citation Envoyé par Dlzlogic Voir le message
En effet différents tests ont montré que l'écart entre la répartition observée et la répartition théorique est de l'ordre de 2%.
Soit cela ne veut rien dire, soit c'est délirant. Pour tout tirage aléatoire, on va observer la répartition théorique "à la limite", pas une différence de 2%. Et si on parle "en cours de tirage", on peut observer n'importe quel écart.

Si tu fais la moindre simulation de tirage aléatoire avec un générateur "ordinaire", dès que le nombre est assez grand, tu observes que le résultat de chaque issue tend vers la limite prévue, supposons un dé à 50 faces. On a vérifié la loi des grands nombres.
A tout moment, chaque issue présente une différence avec la valeur théorique. Le TCL dit que la répartition de ces écarts est conforme (pardon respecte) à la loi normale. Il est bien évident que au début de l'expérience, les différences seront plus grandes. Lorsque c'est stabilisé, disons pour un grand nombre, alors mes essais ont donné un écart d'environ 2%.

[pm42]

Lorsque c'est stabilisé, disons pour un grand nombre, alors mes essais ont donné un écart d'environ 2%.

Donc tes essais ont donné un résultat qui diffère de la valeur théorique et c'est normal ?

[Dlzlogic]

Soit le jeu Pile ou Face.
Ce n'est un secret pour personne que les chances de Pile = les chances de Face = 1/2.
J'ai fait 100 tirages et admettons que les résultats soient 50P et 50F. Ce satisfait exactement et rigoureusement la valeur théorique, dont, tout va bien.
Je fais 1 tirage supplémentaire, j'aurai donc 51/50. C'est bon, ou faux, ou normal, ou prévisible, compte tenu des lois de probabilités et de ce qui a été dit.

Tu sais des essais, j'en ai fait des centaines, avec des générateurs, avec des résultats réels (trajet d'un tracteur agricole piloté par gps), avec l'utilisation de grands nombre, avec une méthode indépendante de toute chose etc. Alors inutile d'essayer de me faire dire ce que je n'ai pas dit.

Pour mémoire, l'auteur du cours cité par feanorel n'appartenant plus à la faculté citée dans ses référence, le mail que je lui ai envoyé n'aura pas de réponse. Peut-être que feanorel pourra répondre à sa place :

Bonjour,

J'ai lu avec beaucoup d'intérêt votre cours Fiche 1 Nombres pseudo-aléatoires ISTIL3A.
Je n'ai pas très bien compris comment un générateur de nombres pourrait passer les tests pour certains modèles et pas pour d'autres.
Cela impliquerait qu'il existe plusieurs aléatoires différents.
Sauf distraction de ma part, je n'ai pas lu que vous parliez de test de répartition d'écarts par rapport à la moyenne, c'est à dire l'application directe du TCL.

Pour certaines démonstrations, j'adopte la méthode suivante :
On tire avec un générateur quelconque suivant le jeu de Pile ou Face.
On groupe les sorties par mots de 6 (par exemple) résultats successifs.
On attribue à Pile le chiffre 0 et à Face le chiffre 1.
On obtient ainsi des nombres en binaire de 0 à 31.
Bien-sûr, la méthode est coûteuse, mais le résultat est parfaitement indépendant du générateur utilisé.
Ceci pour éviter toute contestation sur le générateur.

Cordialement.

[minushabens]

Bonjour PM42,
Je résume le TCL : Une série d'évènements aléatoires de même loi converge vers la loi normale. Bon OUI ou NON ?
Si c'est pas bon, merci de corriger.

C'est NON, à la fois quant à la conclusion (c'est leur moyenne qui converge en loi vers la loi normale) et quant aux hypothèses : il n'est pas nécessaire que les variables aléatoires suivent la même loi, mais en revanche il faut une condition d'indépendance, soit l'indépendance stochastique (ordinaire quoi) soit une condition de mélange. De plus les lois doivent avoir leurs deux premiers moments finis.

[pm42]

J'ai fait 100 tirages et admettons que les résultats soient 50P et 50F. Ce satisfait exactement et rigoureusement la valeur théorique, dont, tout va bien.

C'est faux. Il n'y a pas de valeur théorique. C'est la même erreur que plus haut quand tu crois qu'un générateur se conforme à un théorème ou équivalent.

Je fais 1 tirage supplémentaire, j'aurai donc 51/50. C'est bon, ou faux, ou normal, ou prévisible, compte tenu des lois de probabilités et de ce qui a été dit.

Ca ne veut rien dire.

Tu sais des essais, j'en ai fait des centaines, avec des générateurs... Alors inutile d'essayer de me faire dire ce que je n'ai pas dit.

Je fais simplement remarquer, comme d'autres que ce que tu dis est faux.

[Dlzlogic]

Bon, très nettement, il est inutile de continuer.
Une somme ou une moyenne ne peut pas converger vers une fonction. La moyenne des valeurs (qui suivent une même loi) est une moyenne, c'est à dire une valeur. Suivant le postulat de la moyenne, c'est la valeur la plus probable.
Ce qui converge vers la loi normale, c'est la distribution des écarts à la moyenne arithmétique.
Tous les énoncés sont tout à fait d'accord sur cette définition.
Par ailleurs, si les variables ne suivent pas la même loi, alors ce théorème n'est pas applicable.
Je sais que certains ont cru bon de rajouter "en moyenne" ou "à la limite".
De toute façon, si on n'accepte pas ce point fondamental, aucune justification de générateur de nombres aléatoires n'est possible. Et cette discussion est sans objet.

@ pm42, essaye d'être un peu positif et de dire ce que j'aurais dû écrire. Pour les démonstrations éventuelles, on verra après.

[bon prof math]

Je sais que certains ont cru bon de rajouter "en moyenne" ou "à la limite".

C'est hilarant.
Oui, on se demande bien pourquoi... Peut-être parce qu'ils savent de quoi le TCL parle vraiment... Et que ces personnes donnent des preuves mathématiques... On se demande même pourquoi ils appellent ça un théorème.

Bon, très nettement, il est inutile de continuer.

En effet, tu as fait la preuve de ton incompréhension des probabilités (tes affirmations et tes résumés du TCL sont calamiteux comme te l'ont fait remarquer les autres intervenants).
Pourquoi ne lirais-tu pas sérieusement le TCL dans un livre, par exemple celui de J. Harthong puisque tu sembles l'avoir en main ?

[feanorel]

Bonjour PM42,
Je résume le TCL : Une série d'évènements aléatoires de même loi converge vers la loi normale. Bon OUI ou NON ?
Si c'est pas bon, merci de corriger.

NON. Si tu lis (pour une fois) le TCL tu verras qu'il parle de la moyenne de tirages.

Je te le redonnes (en version simple) :
Si est une suite de variable aléatoire i.i.d alors sa moyenne empirique définie par
"ressemble pour N grand" à une loi normale d'espérance
celle de $X_1$ et d'écart-type celui de $X_1$ divisé par racine de N.

Pour être plus précis que "ressemble pour N grand" il faut parler de convergence en loi.
On ne peut rien dire sur la suite elle même.

Exemple : je prends un truc qui me donne un nombre (réalisation de X_i) de manière aléatoire. Peu importe sa loi (tant qu'elle admet une variance finie).
(Exemple : poids d'un poisson pêché, taille d'un individu pris au hasard,
valeur de la face d'un dé, truc qui vaut 1 si la pièce vaut pile 0 sinon, gain à la machine à sous...)
Je fais 1000 tirages de ce truc. J'en prends la moyenne, qu'on note M_1
Je re-fait 1000 tirages de ce truc. J'en prends la moyenne, qui sera M_2.
etc...

Pour chaque paquet de 1000 tirage j'ai une réalisation de la moyenne empirique que j'ai noté là haut $\bar{X}_{1000}$.
Si je fais un histogramme des M_i j'aurais une belle courbe en cloche qui ressemble à une Gaussienne (centrée sur l'espérance de X_i).
Si je fais un histogramme des réalisation du trucs (les X_i) j'aurais l'histogramme de la loi de $X_i qui n'a aucune raison d'être une gaussienne.