par Nordine Bernard Toumache
Auteur : Nordine Bernart Toumache
Introduction :
Comment sont conçus les générateurs de nombres « aléatoires », que ce soit celui du tableur Excel « ALEA » ou celui de la « machine » des élèves « Rand » (si elle est en anglais), ou d’autres ? Je crois que c’est « un secret de fabrique », les manuels d’utilisation, à ma connaissance, n’aborde pas le sujet ; ils se contentent de donner les instructions à utiliser. Je ne prétends pas répondre à cette question, qui fait l’objet de recherches très pointues, mais je veux seulement proposer quelques conjectures concernant ces générateurs de nombres « aléatoires ». Il faut dire également que je ne cherche pas à savoir ce qu’est « un nombre aléatoire », d’ailleurs, à ma connaissance, il n’existe pas de définition incontestable, et mon but n’est pas de savoir s’il s’agit de nombres « aléatoires » ou « pseudo-aléatoires » ni quel est le générateur implanté dans la « machine » que j’utilise. Le lecteur curieux pourra consulter à ce sujet « Wikipédia » ou l’article Génération de nombres pseudo-aléatoires - Dubois.
Les machines dont je parle ici sont les calculatrices des élèves (Texas ou Casio), d’une part, dans lesquelles est implanté un générateur de nombres aléatoires « Rand » si elles ont pour langage l’anglais et le tableur (Excel), d’autre part, équipé du générateur « ALEA ».
Le générateur est présent et je veux juste soumettre les échantillons fournis par ce générateur à des tests afin de valider les hypothèses que je formule ici à propos de ces générateurs :
- Première hypothèse : les suites proposées sont équiréparties sur [0 ; 1[ ;
- Deuxième hypothèse : les suites proposées sont nécessairement finies ;
- Troisième hypothèse : une des applications de ces générateurs de nombres « aléatoires » de [0 ; 1[ est de générer, par la procédure « Ent(p*ALEA()) » des entiers « aléatoires » entre 0 et l’entier p-1, p≥2.
Pour cette étude, je choisis de soumettre le générateur de nombres « aléatoires » de [0 ; 1[ du tableur « Excel » aux tests que je vais décrire plus loin ; j’aurais pu choisir le générateur « Rand » de la calculatrice mais ses possibilités sont trop limitées, par rapport au tableur, pour faire ce travail avec des élèves. Par exemple, le programme qui réalise le « test du poker » y travaille pendant plus d’une heure avant de donner sa réponse, si on lui demande un échantillon de taille 10 000.
Cet article fournit également plusieurs sujets d’activités pour travailler avec des élèves de tout niveau du lycée pourvu qu’ils soient un peu familiers du tableur. Cela peut aussi être fait avec leur calculatrice mais c’est beaucoup moins commode comme je l’ai signalé plus haut. Les exercices concernant les calculs des probabilités ne s’adressent qu’aux élèves de terminale S car ils ne sont compréhensibles qu’à partir de ce niveau.
Préliminaires :
A) Définition mathématique d’une suite équirépartie sur [0 ; 1[ :
Une suite $(u_n)$ , $u_n \in [0 ~: ; ~: 1[$ est équirépartie si pour tout élément a et b de [0 ; 1[ tels que $a \leq b$, si on note $q_N$, $N \in \mathbb{N}$, le nombre des $u_p \in [a ~: ; ~: b]$ , $p \leq N$, on a : $ lim \dfrac{q_N}{N}=b-a $ .
Remarque :
On montre que les suites $nx-E(nx)$, E désignant la fonction partie entière et x un nombre irrationnel, sont équiréparties sur[0 ; 1[, il en est de même de la suite $\sqrt n -E(\sqrt n)$ dont le caractère équiréparti se démontre, contrairement aux précédentes, par des « moyens élémentaires », la démonstration étant compréhensible par un élève de terminale scientifique. Voir ce fichier :
B) Les suites engendrées par ces générateurs sont finies :
Plusieurs arguments plaident en faveur de cette hypothèse :
a) Ces suites, qui doivent subir des tests statistiques destinés à voir si elles vérifient certains critères, qu’on leur impose afin qu’elles puissent prétendre à « l’aléatoire », sont par nécessité finies ; les tests ne pouvant s’effectuer que sur un nombre fini de termes.
b) J’extrais ce qui suit d’un article sur les générateurs de nombres « pseudos aléatoires » :
(voir Génération de nombres pseudo-aléatoires-Dubois.)
1) Générateurs congruentiels linéaires
Il s’agit de l’algorithme le plus utilisé pour produire des nombres aléatoires depuis qu’il a été inventé en 1948 par D.H Lehmer.
Ce sont les suites récurrentes : $ x_{n+1} = ( a \times x_n + b) ~: \text {mod} ~: c$
Elles dépendent des constantes $ a, ~: b ~: \text {et} ~: c $ ainsi que du terme initial $ x_0$ (’seed’).
Dans tous les cas les nombres générés (sauf éventuellement le premier) sont compris entre 0 et $c-1 $.
2) Générateurs à congruence additive
C’est une généralisation des suites de Fibonnaci, chaque terme étant obtenu par une addition de deux termes pris parmi les k précédents. On dit aussi suites de Fibonnaci ’lacunaires’.
La méthode nécessite le stockage permanent de k nombres.
Naturellement on combine avec une congruence, donc :
$x_n=(x_{n-1} + x_{n-k}) ~: \text {mod} ~: c $
La méthode est rapide surtout quand c est une puissance de 2.
Mitchell et Moore, après une étude théorique poussée, ont proposé le générateur suivant :
$ x_{n+1} = ( x_{n-24} + x_{n-55} ) ~: \text{mod} ~: c$
Cette suite passe avec succès de nombreux critères de qualité.
En conclusion :
Ces générateurs engendrent des entiers de 0 à $ c-1$ et en divisant par c on obtient le générateur de réels sur [0 ; 1[.
Pour ces générateurs, les suites produites sont périodiques de période c.
Le nombre c est « grand » puisque, au bout d’une quinzaine d’heures de travail, un programme sur « TI83 » n’avait pas encore trouvé un terme égal au premier « Rand » repéré par un compteur F initialisé à 0 ; quand j’ai arrêté le programme le compteur F affichait une valeur supérieure à 1 500 000.
Ces suites sont finies mais dépendent du premier terme.
c) Un troisième argument qui plaide en faveur de cette hypothèse est fourni par la suite $\sqrt n-E(\sqrt n)$ qui est infinie et équirépartie au sens mathématique du terme ; on pourrait donc s’attendre à ce qu’elle passe avec succès tous les « tests de qualité ».
Dans le thème (4) ci-dessous, j’ai soumis la suite de chiffres fournis par la première décimale de « $ u_n $ = ALEA » au « test du maximum » qu’elle passe avec succès ; par contre je fournis, en complément dans ce thème 4, une feuille de calcul qui montre que la première décimale donnée par la suite « $ u_n $ = $ \sqrt n-E(\sqrt n)$ » ne passe pas avec succès ce test.
Les tests de validation de la première et de la troisième hypothèse.
Dans ce qui suit je m’adresse à des élèves du lycée auxquels je demande de réaliser les différents tests décrits ci-dessous. Ceux-ci sont présentés en blocs dépliables et repliables à volonté pour en faciliter la lecture.
1) Thème : tester le caractère équiréparti de la suite $ (u_n)$, $u_n$= ALEA()
Remarque :
L’équirépartition devra être comprise au sens statistique du terme puisque je prétends que les suites concernées sont finies. Vérifier le caractère équiréparti de la suite consiste alors à vérifier que ( $ \dfrac {q_N} {N}$ ) est « proche » de b-a pour des valeurs de N « grandes » dans les limites de la capacité du tableur.
L’exercice consiste à faire une feuille de calcul Excel qui teste le caractère équiréparti de la suite $ (u_n)$, $u_n$= ALEA().
On peut consulter la feuille de calcul ci-dessous (zippée ) :
Celle-ci montre le nuage de points des fréquences de réalisation de $u_p \in [a ~: ; ~: b]$ , $p \leq N$, N variant de 1 à 10 000 , accompagné, sur le même graphique du nuage de points y = b – a.
La copie d’écran suivante donne le graphique décrit ci-dessus pour a=0,54 et b=0,7 ; donc b - a = 0,16 ; a et b sont variables.
Appuyer plusieurs fois sur F9 pour faire fluctuer l’échantillon de taille 10 000.
Pour ce qui est de l’exercice demandé aux élèves, on peut le présenter de différentes manières ; je suggère de leur indiquer des fonctions du tableur à utiliser et de leur laisser l’initiative pour faire cette feuille, la feuille que je propose faisant office de correction.
Fonctions à utiliser éventuellement :
– « ALEA() » qui envoie un nombre « aléatoire » de [0 ; 1[ ;
– « ET »qui va être utilisé dans l’instruction « SI » pour tester la condition « ALEA() est entre a et b » ;
– « SI » qui va envoyer 1 si « ALEA() est entre a et b » est réalisé et 0 sinon.
En calculant les fréquences cumulées des 1 dans l’échantillon de taille 10 000 on obtient la fréquence des réalisations de « ALEA() est entre a et b » pour n variant de 1 à 10 000
« Le nuage de points » de ces fréquences accompagné du nuage « y=b-a » est alors très suggestif.
3) Thème : la suite définie par un = Ent(10*ALEA()) subit-elle avec succès le test du poker ?
Citons Arthur ENGEL dans « Les certitudes du hasard » , page 147 §11.2 :
« Aucun procédé de fabrication de chiffres aléatoires n’est entièrement fiable. Il est donc nécessaire de « mesurer » leur caractère aléatoire. En particulier il ne suffit pas de mesurer la fréquence de chaque chiffre il faut aussi vérifier la fréquence de différents blocs.
Un des tests les plus sûrs est le test dit du poker ». Fin de citation.
Arthur Engel parle aussi du « test du maximum ».
Description du « test dit du poker » : les chiffres sont regroupés par blocs de 5.
La probabilité d’un tel bloc est $10^{ - 5}$ . Ces blocs sont regroupés en 7 catégories dont les probabilités sont calculées. On compare alors ces probabilités avec les fréquences observées.
Le tableau suivant donne la description des 7 catégories, lointainement inspirées du poker (je cite) :
| n° | description | type | exemple | probabilité |
| 1 | chiffres différents | abcde | 34961 | 0,3024 |
| 2 | une paire | aabcd | 29512 | 0,5040 |
| 3 | deux paires | aabbc | 44533 | 0,1080 |
| 4 | un triplet=brelan | aaabc | 60366 | 0,0720 |
| 5 | paire triplet=full | aaabb | 23223 | 0,0090 |
| 6 | Quadruplet=carré | aaaab | 29222 | 0,0045 |
| 7 | quintuplet | aaaaa | 55555 | 0,0001 |
Ce test fourni des sujets d’exercices de calculs de probabilités à tout lecteur qui dispose des moyens théoriques de les résoudre ; ce qui est le cas des élèves de terminale scientifique mais pas des élèves d’autres niveaux du lycée avant le baccalauréat.
L’exercice peut se formuler ainsi : calculer chacune des probabilités données dans le tableau ci-dessus.
Exercice (qui s’adresse à tous les élèves du lycée) :
On admet les probabilités données dans le tableau ; l’exercice consiste alors à faire une feuille de calcul « Excel » qui réalise ce test pour des échantillons de taille 10 000.
Je donne les indications suivantes pour faire cette feuille de calcul, mais la démarche n’est pas imposée et je suis ouvert à toute autre proposition qui exécute la même tache.
– 5 chiffres « aléatoires » sont fourni par « Ent(10*ALEA()) »
– La fonction NB.SI calcule le nombre d’apparition de chacun de ces chiffres parmi les cinq
– Utiliser alors, convenablement, les fonctions MIN, MAX et NB.SI pour repérer sans ambigüité chacun des 7 types décrits dans le test.
– Utiliser la fonction « SI » pour afficher 1 si le type k est réalisé et 0 sinon. Faire ensuite la moyenne des réalisations du type k
– Faire un tableau qui donne les fréquences de chaque type pour l’échantillon donné
– Appuyer plusieurs fois sur F9 pour faire fluctuer l’échantillon qui doit être de taille 10 000.
La feuille de calcul suivante (zippée ) réalise ce travail :
La copie d’écran suivante donne le tableau des différents types définis dans le test du poker, types accompagnés de leur probabilité et de leur fréquence observée dans l’échantillon.
Appuyer plusieurs fois sur F9 pour faire fluctuer l’échantillon de taille 10 000.
4) Thème : la suite définie par un = Ent(10*ALEA()) subit-elle avec succès le test du maximum ?
Description du test :
Trois nombres étant donnés, ils réalisent un maximum si le deuxième est strictement plus grand que les deux autres, exemple : 1 8 2 réalisent un maximum.
Par l’instruction Ent(10*ALEA()), on génère un échantillon de taille n formé de n triplets de 3 chiffres « aléatoires ». On calcule la fréquence des maximums et on compare avec la probabilité d’obtenir un maximum, probabilité qui se calcule et qui vaut 0,285.
Je vois ici un bon exercice de dénombrement qui n’est accessible qu’à un élève de terminale scientifique.
Exercice (qui s’adresse uniquement aux élèves de terminale scientifique) :
Parmi tous les triplets de chiffres, calculer la probabilité d’avoir un maximum.
Exercice (qui s’adresse à tous les élèves) :
On admet, ici, que la probabilité d’un maximum est 0,285, l’exercice consiste à faire une feuille de calcul « Excel » permettant de calculer la fréquence des maximums dans un échantillon de 10 000 triplets de chiffres « aléatoires ».
Indications ( que l’on n’est pas obligé de suivre) :
– Utiliser la fonction « SI » du tableur pour faire afficher 1 si le maximum est réalisé et 0 sinon.
– Le graphique donnant le nuage de points des fréquences des maximums pour n variant de 1 à 10 000 est le bienvenu.
La feuille de calcul suivante (zippée ) réalise ce travail :
La copie d’écran suivante donne le nuage de points cité ci-dessus, accompagné du nuage de points « y=0,285 ».
Appuyer plusieurs fois sur F9 pour faire fluctuer l’échantillon de taille 10 000.
En complément, dans ce thème, je veux mettre en évidence la nécessité de soumettre les suites qui prétendent à « l’aléatoire » à des « tests de qualité ». La suite définie par $ u_n = \sqrt n - E(\sqrt n) $ est un bon candidat puisqu’elle est équirépartie au sens mathématique du terme.
Le « test de qualité » est ici le test du maximum ; plus précisément, je vais soumettre cette suite exactement au même test que la suite « $ u_ n $ = ALEA » vu ci-dessus :
• Par la procédure « Ent(10 $ u_n $ ) », avec $ u_n = \sqrt n - E(\sqrt n) $ , qui est la première décimale de $ u_n $ , on crée un chiffre, on regroupe ces chiffres par blocs de trois et on génère 3 000 blocs ainsi ; on regarde ensuite quels sont les blocs qui sont des maximums.
La feuille de calcul ci-dessous réalise ce travail.
Voici une copie d’écran de cette feuille qui donne le nuage de points des fréquences des maximums parmi ces blocs de trois pour n variant de 1 à 3 000 accompagné du nuage « y=0,285 » qui est la probabilité des maximums parmi tous les triplets de chiffres.
Le graphique est éloquent.
Sur les 3 000 triplets, il y a 3 maximums alors qu’ils devraient être environ 855.
La première décimale de cette suite ne peut donc pas prétendre à « l’aléatoire ».
5) Thème : q étant un nombre entier plus grand que 2, l’instruction Ent(q*ALEA()) envoie des entiers 0123…….q-1 ; ces entiers peuvent-ils prétendre à « l’aléatoire » ?
On sait déjà que la probabilité d’apparition de chacun de ces entiers est $ \dfrac 1 q $ , ceci à été vu au thème 2), mais ce n’est pas suffisant pour prétendre à l’aléatoire. Il faut aussi mesurer la fréquence de différents blocs comme le dit Arthur Engel déjà cité plus haut.
Je propose de soumettre les suites produites aux deux tests : le test du poker et le test du maximum.
Dans cet article, je vais me limiter au test du maximum.
Exercice (qui s’adresse uniquement aux élèves de terminale scientifique) :
- Soit P la fonction polynôme définie par :
$P(x)= \dfrac 1 3 x^3 - \dfrac 1 2 x^2+ \dfrac 1 6 x $.
Vérifier que : $P(x+1)-P(x)=x^2 $ pour tout nombre réel x - En déduire que : $ 1^2+2^2+3^2+……+(q-2)^2+(q-1)^2=P(q)$.
- En déduire que, parmi tous les triplets d’entiers entre 0 et q-1, la probabilité d’un maximum est : $\dfrac {P(q)} {q^3} $.
On peut aussi proposer, comme variante :
Démontrer, par récurrence sur q, que : $ 1^2+2^2+3^2+……+(q-2)^2+(q-1)^2= \dfrac 1 3 q^3- \dfrac 1 2 q^2+ \dfrac 1 6 q $ et passer ensuite à la question 3.
Exercice qui s’adresse à tous les élèves :
On admet, ici, que pour une valeur de l’entier q supérieure à 2 la probabilité d’un maximum est $\dfrac {\dfrac 1 3 q^3- \dfrac 1 2 q^2+ \dfrac 1 6 q} {q^3} $.
L’exercice consiste à faire, sur le modèle de la feuille de calcul Excel faite au 4), une nouvelle feuille de calcul dont la précédente serait un cas particulier, c’est-à-dire : en entrant une valeur de q dans une cellule, la nouvelle feuille doit envoyer le nuage de points des réalisations des maximums pour n variant de 1 à 10 000 ; nuage accompagné du nuage de points « $y= \dfrac {P(q)} {q^3}$ », $\dfrac {P(q)} {q^3}$ étant la probabilité d’un maximum.
Pour q = 10, on doit retrouver la feuille de calculs du 4).
La feuille de calcul suivante, où q est remplacé par p, fait ce travail :
La copie d’écran suivante donne le nuage de points cité ci-dessus pour q = 20 ; dans cette feuille de calcul q est un entier variable.
Faire varier la valeur de q et appuyer plusieurs fois sur F9 pour faire fluctuer l’échantillon.
Conclusion :
Les conjectures énoncées sont-elles validées ? La réponse est très subjective puisque je ne dispose pas de « critères chiffrés »permettant de répondre à cette question. Je laisse le lecteur juge.
Pour ma part, les tests statistiques effectués valident les conjectures énoncées et j’ai le sentiment, en utilisant les générateurs « ALEA » d’Excel ou « Rand » de la calculatrice de ne plus faire une confiance aveugle à un outil que je ne connais pas ; c’était le but de ce travail.