LES GENERATEURS PSEUDO-ALEATOIRES

Introduction :

Le hasard est par définition imprévisible, et ce désordre influe à plus ou moins grande échelle sur chaque mouvement dans l’univers. C’est la raison pour laquelle des modélisations de phénomènes physiques utilisent désormais des systèmes dits aléatoires qui vont essayer de reproduire le désordre que créera la nature dans les conditions réelles afin de vérifier la stabilité d’un système (trajectoires, simulations vols astronautes) Faut-il encore que ces systèmes aléatoires le soient….

Nous allons donc étudier les générateurs de suite pseudo aléatoire

Préliminaires :

Tout d’abord on peut se poser la question :Qu’est-ce qu’une suite pseudo aléatoire ?

  • Première réponse :

    Ca n’existe pas car si c’était le cas alors chaque suite serait entièrement déterminée donc pas aléatoire.

    Deuxième réponse :

    Chaque mathématicien ayant étudie ces suites avait créé sa propre définition. En fait on ne sait pas dire ce qu’est une suite aléatoire mais on sait dire ce qu’elle n’est pas :

    -elle n’admet pas de limite

    -elle n’est pas cyclique

    -elle est équirépartie

  • Toutes ces conditions sont intuitives mais sont communes a tous alors que pour la plupart des définitions mathématiques on peut créer une suite non aléatoire au sens intuitif qui vérifie la définition.
    •

    • Une définition semble convenir à tous depuis 1965 :

    Définition de P.Martin-Löf :Une suite aléatoire ne doit vérifier aucune propriété exceptionnelle qu’on peut réellement tester.

    A.Quelques générateurs :

    a ) Générateur linéaire congruentiel : (a,b,m,U0)Î N 4

    Un+1 = a.Un + b mod m

    Remarque : on ramène cette suite à [0,1] pour utiliser les même

    tests que pour les générateurs suivants

    b ) Suites définies par une fonction :

    U0

    Un+1 = f (Un)

     

    ** fonction pic : f : -----------------------

    Un+1 = f (Un) est définie pour tout U0 Î [0,1]

    **fonction logistique : g :-------------------------

     

     

    B. Tests :

    Les tests servent à "mesurer"le caractère aléatoire d’une suite.

    Ils sont nombreux et complémentaires car une telle suite doit vérifier des propriétés bien distinctes.

    a )Un test qualitatif

    Ce premier test opère sur un fichier binaire contenant les x premiers termes de la suite à étudier. Avec x assez grand :

    Il permet d’avoir une vision globale de la suite en créant une image à partir des x premiers termes.

    Ce test permet de déceler des périodicités trop courtes ou des particularités grossières de la suite.

    b )Des tests quantitatifs

    ** Le test de la moyenne :

    Ce test fait la moyenne des 10000 premiers termes de la suite. Les différentes suites étant à valeurs dans [0,1] la moyenne doit être proche de 0,5.

    **Le test du c 2 :

    Ce test calcule 100 c 2 de 100 termes de la suite par rapport à l’espérance des évènements : ²  être dans [ k/10 , (k+1)/10 [ ² . Il utilise alors 10000 termes de la suite. Ensuite il réalise une moyenne de ces valeurs et la compare à ces valeurs. Le test est dit valide si la moyenne admet plus de 5 % des valeurs pour minorant et plus de 5% des valeurs pour majorant.

    **Le test des intervalles :

    Ce test consiste à vérifier l’équirépartition des termes de la suite : pour une suite de 10000 termes il doit y avoir à peu près 1000 termes dans chaque intervalle [ k/10 , (k+1)/10 [ et ensuite il teste la probabilité que deux termes consécutifs soient dans le même intervalle l’espérance de cet évènement étant de 1/100. Il doit y avoir alors environ 100 réalisations par intervalle.

    **Le test des anniversaires :

    Dans une classe de 23 personnes il y a 1 chance sur 2 que 2 élèves aient la même date d’anniversaire…Le test des anniversaires utilise cette remarque en changeant 365 jours par le nombre de valeurs prises par la suite (il faut tout d’abord le rendre fini) dans le cadre de nos tests nous prendrons 10 4 -1 il faut alors une population de 119 éléments pour que la probabilité d’en avoir 2 identiques soit de 0,5 .Nous vérifions alors si cette probabilité est vérifiée.

     

    C. RESULTATS :

    Les suites utilisées :

    Congru1 :=alea(a,b,m,s) a :=1302, b := 593, s :=8537, m :=200003

    congru2 :=alea(a,b,m,s) a :=98651, b :=4234, s :=331; m :=213456473

    congru3 :=alea(a,b,m,s) a :=1313; b :=210; s:=1732587 ;m:=1024;

    Logi1 :=logistic(10001,0.63)

    Logi2 :=logistic(10001,0.1)

    Pic1 :=suite_pic(10001,0.2354)

    random :=utilisation de rand de maple

     

     

     

    Pic1

    Congru2

    Logi1

    Congru3

    Logi2

    random

    Congru1

    		    

     

     

     

     

     

     

    Création

    Temps/s

    Moyenne

    t/s

    c 2

    t/s

    Intervalles

    t/s

    Anniversaire

    t/s

    Pic1

    12

    0.49993

    0.2

    3.5

    60 en dessous

    3.8

    6.8

    0

    94

    Logi1

    18

    0.504

    0.5

    35.3

    63 en dessous

    4.9

    8.9

    302

    68

    Logi2

    20

    0.5001

    0.6

    35.9

    58 en dessous

    4.8

    8.4

    327

    66

    Congru1

    36

    0.496

    0.5

    9.2

    53 en dessous

    4.9

    8.1

    250

    76

    Congru2

    37

    0.504

    0.5

    8.8

    62 en dessous

    4.7

    8.5

    294

    71

    Congru3

    24

    0.50008

    0.363

    3.25

    51 en dessous

    4.1

    7.2

    0

    93

    Random

    19

    0.498

    0.4

    9.55

    60 en dessous

    4.7

    8.2

    221

    78

     

     

    Conclusion :

    Le générateur congruentiel apparaît donc comme un très bon générateur de suites pseudo-aléatoires. C’est en fait le plus utilisé et en fait même si cela n’apparaît pas avec maple il est très rapide si l’on choisit pour congruence une puissance de 2.

    D’ailleurs ce modèle est juge performant par ses utilisateurs ce qui explique que les recherches sur ce sujet sont maintenant très rares et isolées.

    Bibliographie :