Simulation (SED) Licence 3 STID 2020-2021 PDF

Simulation (SED) Licence 3 STID: 2020–2021 Y. Boumzaid U de Béjaïa Table des matières 1 Génération de nombres aléatoires et pseudo-aléatoires 5 1.1 Introduction............................

Simulation (SED) Licence 3 STID: 2020–2021 Y. Boumzaid U de Béjaïa Table des matières 1 Génération de nombres aléatoires et pseudo-aléatoires 5 1.1 Introduction....................................... 5 1.2 Nombres aléatoires et pseudo-aléatoires........................ 5 1.3 Méthodes degénération de nombres pseudo-aléatoires................. 6 1.3.1 La méthode de de Von Neumann........................ 6 1.3.2 Méthode des congruances............................ 7 1.3.3 La méthode de congruence avec retard..................... 8 1.3.4 La méthode de l’inverse en congruences.................... 9 1.3.5 Quelques généarteur informatiques....................... 10 1.4 Tests des générateurs de nombres pseudo-aléatoires.................. 11 1.4.1 Run test..................................... 11 1.4.2 Test de chi-deux................................. 12 2 Simulation des variables aléatoires 15 2.1 Introduction....................................... 15 2.2 Simulation de variables aléatoires discrètes....................... 15 2.2.1 Loi de Bernoulli de paramètre p notée B(p).................. 15 2.2.2 Loi binomiale (n, p) notée Bin(n, p)...................... 16 2.2.3 Loi de probabilité discrète sur un ensemble fini................ 16 2.2.4 Loi de probabilité de Poisson.......................... 17 2.3 Simulation de variables aléatoires continues...................... 18 2.3.1 Méthodes d’inversion.............................. 18 2.3.2 Méthode d’acceptation-rejet.......................... 23 2.3.3 Méthode de Box-Müller............................ 26 3 Simulation à événements discrets 29 3.1 Création d’un modèle.................................. 29 3.1.1 Problimatique.................................. 29 3.1.2 Démarche à suivre................................ 29 3.2 Terminologie....................................... 30 3.2.1 Eléments communs............................... 30 3.2.2 Classification des éléments........................... 30 3.3 Classification des modèles de simulation........................ 31 3.4 Les systèmes de files d’attente............................. 31 3.4.1 L’état et les évenements............................ 31 3.4.2 Algorithme de simulation............................ 32 3.4.3 Méthode des tableaux.............................. 33 3.4.4 Premier exemple................................. 34 3.4.5 Deuxième exemple................................ 35 3.4.6 Troisième exemple................................ 35 3.5 Approche de simulation et modèle........................... 35 3 3.5.1 Approche pas évenement............................ 36 3.5.2 Approche par processus............................. 36 1 2 Introduction Avant propos L’objectif de l’enseignement de cette matière L’objectif de l’enseignement de cette matière est d’initier les étudiants à la simulation et particu- lièrement à la simulation à événements discrets en utilisant différentes méthodes d’échantillonnages. Le contenu de la matière Le contenu de cette matière s’étend sur 3 chapitres. Dans le premier chapitre, nous donnons une brève introduction à la Génération de nombres aléatoires et pseudo-aléatoires. Dans le deuxième chapitre, nous abordons la simulation ainsi qu’à la Génération de variables aléatoires suivant diffé- rentes lois de probabilités : Applications aux lois de probabilités classiques. La méthode d’Inversion, de Rejet et de Composition. Méthode Box Muller pour la génération d’une loi gaussienne. Dans le troisième chapitre, nous abordons les diffrents méthodes de la simulation à événement discrets. 3 4 Chapitre 1 Génération de nombres aléatoires et pseudo-aléatoires 1.1 Introduction Les générateurs pseudo-aléatoires ont, à travers le temps, acquis une grande importance dans divers domaines, allant du médical à la sécurisation, et se sont montrés être d’une grande efficacité quant à leurs apports dans ces domaines. — Confidentialité des échanges sur les réseaux sans fil. — Sécurisation des applications web. — Système de chiffrement. — Domaine biomédical. 1.2 Nombres aléatoires et pseudo-aléatoires Pour la simulation d’un modèle non-déterministe, il est nécessaire de disposer d’une source de nombres susceptibles de jouer le rôle des variables aléatoires qui interviennent dans la définition du modèle. Définition 1. Un générateur de nombres aléatoires (G.N.A)est un mécanisme capable de produire une séquence de nombres qui ont l’air d’être choisis complètement au hasard. Exemple 1. — Suite d’entiers de 1 et 100 : 31 45 02 72...... — Suite de nombres réels entre 0 et 1. De vrais nombres aléatoires peuvent être produits par n’importe quel processus naturel considéré comme aléatoire. Une méthode pour générer des nombres aléatoires consiste à tirer d’une urne des billets numérotés de 0 à 9, un billet à la fois, en remettant dans l’urne chaque billet tiré. Le développement de la technologie informatique a toutefois supplanté ce type de générateurs au profit des générateurs de nombres pseudo-aléatoires. Définition 2. Un générateur algorithmiques ou de nombres pseudo-aléatoires (GNPA) est un al- gorithme qui génère une séquence de nombres présentant certaines propriétés du hasard. De sorte que, les nombres générés par cet algorithme sont supposés être suffisamment indépendants les uns des autres, et qu’il est potentiellement difficile de repérer des groupes de nombres qui suivent une certaine règle (comportements de groupe). Cependant, les sorties d’un tel générateur ne sont pas entièrement aléatoires ; elles s’approchent seulement des propriétés idéales des sources complètement aléatoires, comme le faisait remarquer John von Neumann : « Quiconque considère des méthodes arithmétiques pour produire des 5 nombres aléatoires est, bien sûr, en train de commettre un péché ». La raison pour laquelle on se contente de nombres pseudo-aléatoires est que : — Il est difficile d’obtenir un grand échantillon de « vrais » nombres aléatoires. — Les algorithmes générateurs sont particulièrement adaptés à une implémentation informa- tique, donc plus facilement et plus efficacement utilisables. Dans la suite de ce document, un générateur de nombres uniformes sera un algorithme qui permet de produire une suite de nombres aléatoires issu d’une population distribuée selon la loi U([0, 1]) dont les éléments sont indépendants les uns des autres. Autrement dit, un nombre aléatoire généré par cet algorithme peut-être vu comme la réalisation d’une variable aléatoire distribuée uniformément dans l’intervalle [0, 1]. 1.3 Méthodes degénération de nombres pseudo-aléatoires La plupart des algorithmes générateurs de nombres pseudo-aléatoires ont pour but de produire des suites uniformément distribuées. Une classe très répandue de générateurs est fondée sur des congruences. Dans ce cours nous nous contentons par présenter deux méthodes qui permet de générer des nombres pseudo-aléatoires. 1.3.1 La méthode de de Von Neumann Cette méthode, connue dans la littérature aussi sous le nom du carré médian (middle square). Cette méthode a été introduite par John von Neumann en 1951, est considéré comme la première méthode de génération automatique de nombres pseudo-aléatoires. Méthode Cette méthode consiste a génèrer une suite de nombres ayant chacun m chiffres, où m est un nombre pair. Le successeur d’un nombre de cette suite est obtenu en élevant ce nombre au carré puis en retenant les m chiffres du milieu. Ce raisonnement donne lieu à l’algorithme suivant : Supposons que l’on veuille générer n nombres pseudo-aléatoires. 1. initialisation : Pour i = 0, on choisit un nombre x0 à m chiffres et on pose u0 = x0 /10m. 2. itération : Pour i = 0...n, on pose xi+1 = [xi2 /10(m/2) ] mod (10m ) ui+1 = xi+1 /10m où [.] est la partie entière. Algorithme 1 : Méthode du carré médian 1 lire(n); 2 lire(X (1)); 3 U(1) = [X (1)/10m ]; 4 pour i = 2 : n; 5 X (i) = [X (i − 1)2 /10(m/2) ] mod 10m ; 6 U(i) = U(i − 1)/10m ; 7 fin 8 ecrire (X ); 9 ecrire (U); 6  Intuitivement cette méthode paraît donner de bons résultats. Cependant ce n’est pas le cas, car très souvent les nombres s’approchent de 0 pour y rester, ou produisent un cycle trop court de chiffres qui se répète indéfiniment. Exemple 2. Soit x1 = 3792; m = 4. Nous avons 37922 = 14 3792 64, d’ou x2 = x3 = ´´´ = 3792. Dans ce cas la suite ne de nombres généré ne puisse pas être considérée comme aléatoire. Exemple 3. à programmer dans le TP Soit x1 = 1926 et m = 4, la suite se réduit à 0 après 27 itérations, donc on ne peut pas générer plus que 26 nombres pseudo-aléatoires. Cette méthode ne garantit donc pas la production de suites de nombres aléatoires, et c’est pourquoi elle a été abandonnée depuis longtemps. 1.3.2 Méthode des congruances La méthode des congruences repose sur un algorithme simple pour la génération de nombres pseudo-aléatoires. En effet, cette dernière est basée sur la relation de récurrence suivante : Xi = (aXi−1 + b) mod m i = 1, 2,...n − 1, (1.1) où a, b, m et X0 sont des entiers positifs donnés. On dit que a est lemultiplicateur, b est l’incrément, m le modulus, n le nombre des échantiollons à générer et X0 la valeur initiale appellée aussi graine. Le nombre pseudo-aléatoire, Ui , i = 0..n − 1, compris entre 0 et 1, est obtenu par la relation : Ui = Xi /m. La longueur d’une suite quelconque générée par une relation récursive du type (aXi−1 +b) mod m ne peut pas dépasser m puisqu’il y a au plus m nombres différents modulo m.De manière générale, il faut choisir une grande valeur de m. Pour obtenir une suite de longueur maximale, c’est-à-dire de période m. Pour cela, il faut que les conditions du théorème suivant soient vérifiées : Théorème 1. (Hull et Dobell (1962)) Soit k ∈ {0, 1,..., m − 1}. Soient a, b, m, tels que : 1. b et m sont premiers entre eux ; 2. (a − 1) est un multiple de chaque nombre premier qui divise m ; 3. si m est un multiple de 4 alors (a − 1) l’est aussi. Alors la suite définie par : ( X0 = k Xi = (aXi−1 + b) mod m a un cycle de longueur m Remarque 1. Le nombre pseudo-aléatoire compris entre 0 et 1 est obtenu par la relation Xi Ui = (1.2) m 7  Algorithme 2 : Méthode de congruence 1 lire(n); 2 lire(X (1)); 3 lire(a); 4 lire(b); 5 lire(m); 6 U(1) = X (1)/m; 7 pour i = 2 : n; 8 X (i) = (a ∗ X (i − 1) + b) mod m; 9 U(i) = X (i)/m; 10 fin 11 ecrire (X ); 12 ecrire (U); Exemple 4. On pose x0 = 1, a = b = 5 et m = 32, par substitution dans l’équation (1) : xi = (5xi−1 + 5)mod(5), on obtient la suite : x1 = 10 x2 = 23 x3 = 24 x4 = 29 x5 = 22 x6 = 19 x7 = 4 x8 = 25 x9 = 2 x10 = 15 x11 = 16 x12 = 21 x13 = 14 x14 = 11 x15 = 28 x16 = 17 x17 = 26 x18 = 7............ x31 = 12 x32 = 1 x33 = 10... La suite ci-dessus se répète après le 32 ème élément. La longueur du cycle est un indice de qualité de la suite générée et dépend du choix des paramètres a, b et m. La longueur d’une suite quelconque générée par une relation récursive du type (aXi−1 +b) mod m ne peut pas dépasser m puisqu’il y a au plus m nombres différents modulo m. De manière générale, il faut choisir une grande valeur de m. Pour obtenir une suite de longueur maximale, c’est-à-dire de période m, il faut que les conditions du théorème suivant soient vérifiées : (Hull et Dobell (1962)) Soit k ∈ {0, 1,..., m − 1}. Soient a, b, m, tels que : 1. b et m sont premiers entre eux ; 2. (a − 1) est un multiple de chaque nombre premier qui divise m ; 3. si m est un multiple de 4 alors (a1) l’est aussi. Alors la suite définie par : ( X0 = k Xi = (aXi−1 + b) mod m a un cycle de longueur m 1.3.3 La méthode de congruence avec retard Le point faible de la méthode de congruence réside dans la relation de récurrence qui provoque des irrégularités non désirées. Une modification de la règle de récurrence est donnée par : Xi = (aXi−r + b) mod m. 8  0 où r indique le retard et où les premiers termes sont calculés avec la relation Xi = (a Xi−1 + 0 0 0 0 0 b ) mod m , les paramètres a , b et m pouvant être différents de a, b et m. Pour r = 1 on retrouve la méthode de congruence. Algorithme 3 : Méthode de congruence par retard 1 lire(n); 2 lire(X (1)); 3 lire(a); 4 lire(b); 5 lire(m); 6 %%%%%%%%%%%% 7 lire(r ); 0 8 lire(a ); 0 9 lire(b ); 10 %%%%%%%%%%%% 11 pour i = 2 : r + 1; 0 0 0 12 X (i) = (a ∗ X (i − 1) + b ) mod m ; 13 fin 14 %%%%%%%%%%%% 15 pour i = r + 2 : n; 16 X (i) = (a ∗ X (i − r ) + b) mod m; 17 U(i) = X (i)/m; 18 fin 19 ecrire(X ); 20 ecrire(U); Exemple 5. Choisissons les paramètres m = 8, x0 = 1, a = 5, b = 1, r = 2. Les deux premiers termes de la suite sont calculés pour b = 3 : x1 = (5(1) + 3) mod 8 = 0 x2 = (5(0) + 3) mod 8 = 3 ainsi x3 = (5x1 + 1) mod 8 = 1 x4 = (5x2 + 1) mod 8 = 0 x5 = (5x3 + 1) mod = 6 x6 = 1 x7 = 7 x8 = 6 1.3.4 La méthode de l’inverse en congruences La linéarité de la relation de récurrence de la méthode des congruences peut la rendre inutile dans certains problèmes de simulation. La méthode de l’inverse en congruences (Eichenauer et Lehn, 1986) utilise la notion d’inverse multiplicatif modulo m et supprime ainsi la relation linéaire. Rappelons que pour p premier, l’inverse de X mod p noté ~ est défini par la relation X ~X ~ = 1 mod p. Par convention, l’inverse de 0 est 0. La relation de récurrence associée à cette méthode est donnée par : Xi+1 = (aX~i + b) mod p 9  Il est possible de trouver des valeurs de a et b telles qu’on obtient une suite de période p. Exemple 6. La formule de récurrence xi = (2~~ xi−1 + 1) mod 7 où ~~ x est l’inverse (mod 7) de x (voir ci-dessous) : x 1 2 3 4 5 6 ~ x 1 4 5 2 3 6 engendre la suite suivante à partir de x0 = 1 : x1 = (2~ x0 + 1) mod 7 = (2(1) + 1) mod 7 = 3 x2 = (2~ x1 + 1) mod 7 = (2(5) + 1) mod 7 = 4 x3 = 5 x4 = 0 x5 = 1 La théorie statistique démontre que les nombres pseudo-aléatoires issus de la méthode de l’inverse en congruences ont des propriétés de distribution et d’indépendance proches de celles d’une suite de nombres aléatoires. 1.3.5 Quelques généarteur informatiques La plupart des générateurs de nombres aléatoires utilisés par les logiciels et les langage de programmation informatique sont construits à l’aide de la méthode de congruence présentée dans la section précédente. Dans cette sous-section, nous donnons les paramètres de quelques générateurs utilisés en informatique (voir tableau 1.1). Longage/Logiciel Générateur a b M 16 IBM RANDU 2 +3 0 231 Scilab RAND 843314861 453816693 231 Turbo Pascal RANDOM 129 907633385 232 Langage c RAND 103515245 12345 231 Maple RAND 427419669081 0 1012 − 11 Table 1.1 – Générateurs informatique Exemple 7. L’algorithme ci-dessus, génère une suite de nombres aléatoires avec le générateur de Scilab. Algorithme Debut lire(n) ; a = 843314861 ; b = 453816693 ; m = 231 ; X (1) = 0 ; %la graine pour i = 1 : n faire X (i + 1) = (aX (i) + b)mod m ; X (i + 1) U(i) = ; m fin pour ; afficher (U(i)) ; Fin. La figure 1.1 montre la simulation de 1000 tirages de variable aléatoire de loi U([0, 1]) obtenues par le générateur Scilab. 10  Figure 1.1 – Génération des nombres aléatoires 1.4 Tests des générateurs de nombres pseudo-aléatoires Rappelons, qu’il existe beaucoup de tests permettant de s’assurer de la qualité des nombres aléa- toires produits par un générateur algorithmique. Ces derniers permettent de vérifier la stochasticité et l’uniformité des séquences (u1 ,.., un ) générées. Parmis ces tests, on peut citer, le test de khi-deux, le test de Kolmogorov-Smirnov ou encore des tests basés sur l’étude de corrélation entre les termes des séries temporelles ui et (ui−1 ,.., ui−n ). Dans cette section nous nous contentons par donner deux tests statistiques à savoir le Run test et le test chi-deux. Le premier sera utilisé pour vérifier la stochasticité et le second pour vérifier l’uniformité d’un générateur pseudo-aléatoire. Rappelons ici qu’il est nécéssaire d’avoir des connaissance sur les Tests d’hypothèses. 1.4.1 Run test Le run test est un test non paramétrique qui permet de tester la stochasticité d’un générateur pseudo-aléatoire. Principe Il s’agit de tester les hypothèses H0 La séquence est aléatoire H1 La séquence est non aléatoire Ce test est basé sur le nombre de séquences croissantes et décroissantes. Soit S est le nombre de séquences dans l’échantillon de n nombres. Théoriquement, la moyenne et la variance sont données par : (2n − 1) (16n − 29) E[S] = Var (S) = 3 11 90 Règle de décision (S − E[S]) Sous l’hypotese H0 et pour S grand, la statistique S est normale. Soit Z = p. Au seuil Var [S] α = 5%, si |Z | > 1, 96, on rejette H0. Exemple 8. Prenons l’échantillon suivant : 12 − 14 − 65 − 18 − 33 − 77 − 89 − 72 − 76 − 43 − 70 − 81 − 94 − 98 − 3. Les séquences croissants décroissants sont comme suit : ++ − +++ − + − ++++ − Nous avons 8 séquences ; 4 croissantes et 4 décroissantes, donc S = 8. On a (2n − 1) (16n − 29) E[S] = = 9.66 Var (S) = = 2.34 Z = −1, 089 3 90 Donc, on a |Z | < 1.96 donc on accepte H0 , c.à.d au seuil de 5% l’échantillon est aléatoire. 1.4.2 Test de chi-deux Principe Il s’agit de tester les hypothèses H0 : piobs = pitheo H1 : ∃i tq : piobs 6= pitheo On regroupe la série simulée en k classes possibles avec des probabilités pk , puis on calcule la statistique suivante : k X (fi − npi )2 χ2c = ∼ χ2 (k − 1), i=1 np i où fi est la fréquence observée de la classe ci , i = 1,..., k, et npi dénote la fréquence théorique ou attendue. Règle de décision Sous l’hypothèse nulle, la statistique χ2c suit la loi χ2 (k − 1). On accepte H0 si χ2c < χ2α (k − 1) au seuil α. Exemple 9. Reprenant l’exemple précédent : x = (12 − 14 − 65 − 18 − 33 − 77 − 89 − 72 − 76 − 43 − 70 − 81 − 94 − 98 − 3). on place les valeurs en questions dans un tableau i 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 tot fi 12 14 65 18 33 77 89 72 76 43 70 81 94 98 3 845 Si les nombres aléatoires étaient distribuées d’une façon strictement uniforme pour i = 1..15, alors 1 la probabilité p = , d’ou le tableau suivant : 15 i 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 tot fi 12 14 65 18 33 77 89 72 76 43 70 81 94 98 3 845 npi 56.33 56.33 56.33 56.33 56.33.......... 845 12 Nous avons : 15 X (fi − npi )2 χ2c = = 256.31 i=1 npi La comparaison de la valeur calculée avec celle de la table du χ2 correspondant au seuil de signification de 5% et à (15 − 1) = 14 degrés de liberté donne : χ2c = 256.31 > χ2 (0.05, 14) = 23.6848. Donc, on rejette H0 , c.à.d au seuil de 5% les fréquences observées ne sont pas uniformément distribués. 13 14 Chapitre 2 Simulation des variables aléatoires 2.1 Introduction Dans le chapitre précédent nous avons vu comment simuler ou générer des suites de nombres aléatoires distribués de façon uniforme sur l’intervalle[0, 1]. Ceux-ci sont à la base de toute simulation. Dans cette section, nous présentons quelques méthodes de génération de nombres non uniformes. Dans ce cas on parle de la simutaion d’une variable aléatoire qui suit une loi de probabilité quelconque. 2.2 Simulation de variables aléatoires discrètes On présente ici quelques méthodes de simulation de variables aléatoires de lois discrètes 2.2.1 Loi de Bernoulli de paramètre p notée B(p) La loi de Bernoulli est une distribution discrète de probabilité, qui prend la valeur 1 avec la probabilité p et 0 avec la probabilité q = 1 − p. En d’autres termes :    p si x = 1 P(X = x ) = 1 − p si x = 0   0 sinon ou encore P(X = x ) = p x (1 − p)1−x δ(x ) La simulation de la loi de Bernoulli est basée sur la proposition suivante : Proposition 1. Soit X une v.a.d suit la loi B(p), X ∼ B(p), alors l’évènement X ∼ B(p), peut s’écrire comme la fonction indicatrice d’un évènement U ∼ U([0; 1]) avec U ≤ p. Autrement dit : X ∼ B(p) ⇔ X = δU≤p Preuve 1. On montre que X = δU≤p( ⇒ X ∼ B(p) 1 si U ≤ p Soit l’évènement X = δU≤p ⇔ X = 0 sinon p X — Si X = 1 alors P(x = 1) = P(U ≤ p) = 1=p k=1 — Si X = 0 alors P(x = 0) = P(U > p) = 1 − P(U ≤ p) = 1 − p d’ou la preuve de X = δU≤p ⇒ X ∼ B(p). Par réciproque, on en déduit que X ∼ B(p) ⇒ X = δU≤p 15  Algorithme 4 : Simulation de la loi de Bernoulli 1 if (u