Universite des Sciences et Technologies de Lille U F R de Mathematiques Pures et Appliquees Bat M2 F Villeneuve d'Ascq Cedex
45
pages
Français
Documents
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
45
pages
Français
Documents
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
Niveau: Supérieur, Master, Bac+5
Universite des Sciences et Technologies de Lille U.F.R. de Mathematiques Pures et Appliquees Bat. M2, F-59655 Villeneuve d'Ascq Cedex Simulation Charles SUQUET Agregation Externe 2005–2006
Voir
Universite des Sciences et Technologies de Lille U.F.R. de Mathematiques Pures et Appliquees Bat. M2, F-59655 Villeneuve d'Ascq Cedex Simulation Charles SUQUET Agregation Externe 2005–2006
- meme probabilite
- simulation de vecteurs aleatoires par transformation
- loi uniforme
- lois gaussiennes
- independantes de loi uniforme
- vecteur gaussien de covariance donnee
- variables de bernoulli independantes de meme parametre
- loi discrete par rejet
Agr´egationExterne
Universit´edesSciencesetTechnologiesdeLille U.F.R.deMathe´matiquesPuresetApplique´es Bˆat.M2,F-59655Villeneuved’AscqCedex
Simulation
Charles SUQUET
2005–2006
2
Ch.Suquet,Simulation
Tabledesmatie`res
1 2 3 4 5
6
Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . M´thodeth´eoriquepoursimulerunev.a.r.. . . . . . . . .. . . . . . . . e M´ethodesparticulie`respourloisusuelles. . . . . . . . . .. . . . . . . . 3.1Loisdiscre`tes`asupportfini. . . . . . . . . . . . . . . . . . . . . 3.2 Lois binomiales et multinomiales. . . . . . . . . . . . . . . . . . 3.3 Lois de Poisson. . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4Loisg´eom´etriques. . . . . . . . . . . . . . .. . . . . . . . . . . . 3.5 Lois gaussiennes. . . . . . . . . . . . . . . . . . . . . . . . . . . . Algorithmes de rejet. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.1 Simulation de lois uniformes par rejet. . . . . . . . . . . . . . . . 4.2Simulationdeloisa`densite´parrejet. . . . . . . . . . . . . . . . 4.3Simulationd’uneloidiscre`teparrejet. . . . . . . .. . . . . . . . Simulationdevecteursale´atoirespartransformation. . . . . . . . . . . . 5.1 Loi uniforme par transformation affine. . . . . . . . . . . . . . . 5.1.1 Principe. . . . . . . . . . . . . . .. . . . . . . . . . . . 5.1.2Loiuniformesurunparall´elogramme. . . . . . . . . . . 5.1.3 Loi uniforme sur un triangle ou un polygone. . . . . . . 5.1.4 Loi uniforme sur un simplexe deRd. . . . . . . . . . . . 5.1.5 Loi uniforme sur un ellipso¨ıde. . . . . . . . . . . . . . . 5.2Vecteurgaussiendecovariancedonne´e. . . . . . . .. . . . . . . Me´thodepolaire. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
5 6 9 9 11 13 15 17 17 18 21 26 28 29 29 29 30 31 33 34 36
4
Ch.uSuqte,iSumlation
Simulation de variables et vecteurs ale´atoires
1 Introduction Lasimulationinformatiqueduhasardademultiplesapplications:simulationdeph´e-nome`nesphysiques,m´ethodesdeMonte-Carlopourlecalculd’int´egrales,e´tudedetests statistiquesoud’estimateurs,simulationdefonctionnementsder´eseauxoudesyst`emes complexes, cryptographie, imagerie, algorithmes probabilistes,. . . Th´eoriquement,lag´en´erationdenombresal´eatoiressuivantuneloidonn´eeseram`ene `alage´n´erationdesuitesdevariablesale´atoiresind´ependantesdeloiuniformesur[0,1]. Si lesXiariablessontdesvemsdmeˆendpeteaniille´dneBeduonrer`mteaparp= 1/2, la v.a.U:=Pk=+∞1Xk2−ksuit la loi uniforme sur [0,obpreml`eres`eamodena`cnLe].1 lagene´rationd’unesuitede«bits»´endsiretsanndpeptnavuophcerdneracunlae´taio ´ lavaleur0oulavaleur1avecmˆemeprobabilit´e1/2. En d’autre termes, il suffirait de realiserunjeudepileoufaceinfiniavecunepi`eceparfaitemente´quilibr´eee-´1. Cette m´ thoden’est´evidemmentpasre´alisteetenpratiqueonarecoursa`l’informatiquepour «simuler»une telle suite. Pourquoi employer ici le mot«simuler»? Parce qu’une suite denombresg´en´ere´eparunalgorithmen’estpasvraimental´eatoire.Sionconnaˆıtles valeursd’initialisationetl’algorithme,onpeutcalculer(etdoncpre´voir)lestermesdela suite.Ne´anmoinsonconsid`ereraquel’onaunbonge´n´erateurdenombresal´eatoiression neparvientpasa`distinguerlasuitedenombrespseudoaleatoiresproduited’unesuite ´ ve´ritablementale´atoire.Lasignificationpr´ecisedecettephrasedemanderaittoutund´e-veloppementamenant`as’interrogersurlanotionmˆemedehasard.Onpourrautilement consultera`cesujet[2en statistique, nous nous contenterons de dire]. Pour l’utilisation qu’ung´en´erateurestacceptables’ilpasseavecsucce`sunebatteriedetestsstatistiques courants. Les fonctionsrandomdes principaux langages de programmation ou logiciels sont baˆtiessurdesalgorithmesarithm´etiquesdontleplussimplecorrespondaug´ene´rateur congruentielline´aire.Ils’agitdeg´e´esuitednombres(Xn)n≥1nautrefiiv´en nerer un e relationder´ecurrence Xn+1=aXn+cmodM(1) 1. Sip6= 1/2, la loi deUpantsiansa’aynoitunmertitioncnder´epaoitcnofa`ere`ilungsioielunste dedensite´parrapporta`lamesuredeLebesgue.
5
etd’end´eduireunesuite(Un)n≥1a valeurs dans [0,1[ en prenantUn=Xn/M. Par ` exemple la fonctionrandde Scilab utilise (1) avecM= 231,a 314 861= 843 et c= 453 816 693. La suite (Uneeitcostonicrustdtneete´`lpmmete)iasnp´e-,caristermin riodique.Cependantsape´riodeesttellementgrandequ’onpeutenpratiquelaconsi-d´erercommeunesuiteale´atoire,dumoinspourdesbesoinsstatistiquecourants(son usageestde´conseill´eencryptographie).Remarquonsd’ailleursquemˆemesiUn´etait iciale´atoire,sesvaleursseraientdelaformek2−31et on obtiendrait la loi uniforme discrete surD31={k2−31; 0≤k <231}au lieu de la loi uniforme sur [0,1[. Ceci ` n’estpastropgˆenantpourlesdeuxraisonssuivantes.D’unepartlaloiuniformeµnsur Dn={k2−n; 0≤k <2n}e´rtreegocvnlolarsventmeteoi0[rusemrofinui,1[ quandn tend vers l’infini2esrdmnese´tnapenihcadta’tuerebromr´esrtpasnlerperese´sleetnos rationnels dyadiques de la formek2−jlsuo´rseslee[ed,desquetortek2−j,(k+ 1)2−j[ sont confondus. Danscedocument,nousnoussituonsenavalduproble`medelaconstructiond’un ge´ne´rateurdenombresale´atoires.Onsupposequel’onsaitg´ene´rerunesuitei.i.d.(Un) devariablesal´eatoiresdeloiuniformesur[0,1]. On se propose de construire et de justifier math´ematiquementdesalgorithmespermettant`apartirdel`adesimulerunevariable al´eatoireouunvecteural´eatoiredeloidonne´e.Ondonneraunetraductiondecertains decesalgorithmesenScilaba`titred’illustration.
2M´ethodeth´eoriquepoursimulerunev.a.r. SoitXntioiaptrree´oidnctonefedlleer´reiotae´laelbairavuneFriepa´efin,d F(x) :=P(X≤x).(2) Rappelons queFtniopucga`aeeuttoenhea`rdioetteilim´tissante,continueseorct deRiu´ttnniatpuseseledesembiscosesdne’leuq,lbeebmare´onuldstqueFa pour limite 0 en−∞et 1 en +∞naD.oru`ieulicrtpaasecslFest continue et strictement croissante sur toutRtionijecde,seliebunleelear´Rsur ]0,1[ et admet donc un inverse F−1:]0,1[→Rau sens classique. SiUestunevarialbae´laeotrideleunoiorifsume0r],1[, alorsY:=F−1(U)iolemeˆmaqueXlecifafieri´eevnlO.nctioafonnaltclluneacemtn der´epartitiondeY: ∀x∈R,P(Y≤x) =P(F−1(U)≤x) =P(U≤F(x)) =F(x).(3) Danscettesuited’e´galit´es,ladeuxi`emereposesurlacroissancedeFet deF−1qui le´gitimentl’´equivalenceF−1(U)≤x⇔U≤F(x´egelatie´sedteuuaacc)l.lLuaderni`er delafonctionder´epartitiondelaloiuniformesur]0,1[ (qui co¨ıncide sur [0,1] avec l’identite´)etaufaitqueF(x)∈[0,1]. 2. L’erreur commise sur la f.d.r. deµnmrofruseolalinuid.f.der.tpanlaarerpmalc¸neal[0,1] estmajor´eepar2−net 2−31'4,7×10−10est suffisamment petit pour un usage courant de cette approximation.
6
Ch.Suquet,Simulation
