[SON] [AUDIO_VIDE] Bonjour à tous, nous allons commencer une série de séances consacrées à la simulation aléatoire, cette première séance sera consacrée à une introduction générale. Quel est le but que nous allons poursuivre? C'est celui de simuler le hasard avec un ordinateur. Il y a d'innombrables applications à cela, j'en signale quelques-unes et on en abordera donc certaines. Il y a la simulation de phénomènes physiques, méthode de Monte-Carlo pour le calcul d'intégrales, études de tests statistiques, simulations de fonctionnement de réseaux, cryptographie, qui est devenue d'une importance très grande de nos jours, l'imagerie, les algorithmes probabilistes, les gens passent et des meilleurs. Donc, la première chose que vous devez vous demander, c'est pourquoi on parle de simuler? Alors la réponse est en fait simple, c'est que, si vous utilisez un ordinateur, tout ce qu'il est capable de faire c'est exécuter un algorithme. Un algorithme, si on le dit simplement, c'est une suite d'opérations qui sont parfaitement déterministes. Dans ces cas-là on se demande bien comment on va pouvoir simuler ou créer du hasard, ça a l'air d'être complètement antinomique, complètement contradictoire. En fait, l'idée est de produire une suite de nombres qui va être complètement imprévisible, et qui va imiter une suite de v.a. indépendantes, uniformes dans l'intervalle [0, 1]. Ca va être ça l'idée sous-jacente. Alors, comment les gens s'y sont pris? Donc, tout ordinateur qui se respecte a, tout langage de programmation banal a une fonction que j'appelle random, qui peut s'appeler rand, par exemple, et ce qu'lle fait, basiquement, c'est produire une suite de nombres par une relation de récurrence de cette forme, donc a et c et n ce sont des paramètres, que je vais discuter dans un petit instant, et l'idée, c'est de calculer, de proche en proche, cette série. On appelle ça une suite concurrentielle, parceque comment on la calcule? On prend Xn, on le multiplie par a, on lui ajoute c, on regarde le résultat de la division euclidienne par M, et ça devient la nouvelle valeur, Xn + 1. Et on recommence. Une fois qu'on a cette suite de nombres, pour qu'ils soient compris entre 0 et 1 on divise tout simplement par M. Alors pour prendre un exemple concret, qui est le langage de programmation Scilab, qui est un logiciel libre, qui est beaucoup utilisé, et que vous pouvez trouver sur internet, dans cet exemple précis, M ici c'est 2 puissance 31, a, c'est ce nombre que je ne voulais pas énoncer mais qui est assez grand, c, est donné ici. Evidemment ces nombres ne sont pas du tout choisis au hasard, c'est le cas de le dire, et donc pour l'instant je ne discute pas pourquoi ils ont été choisis, je vais y revenir dans un instant, mais comme vous vous en doutez, on a une suite définie par récurrence, il faut bien dire par quoi on commence, et donc il faut donner X0 tout simplement. Et on appelle ça dans le jargon, la graine. Seed en anglais. Donc dans Scilab, si vous ne faites rien, vous appelez la fonction random, ça vous fait tout simplement une graine qui vaut 0. Et ensuite on calcule. Si on ne change pas la graine, on obtient toujours la même suite. L'ordinateur calcule de façon toujours déterministe. Ca peut paraître étrange au premier abord, mais en fait, c'est très pratique si vous voulez avoir des simulations reproductibles. Si vous voulez tester votre simulation n'oubliez pas que chaque fois que vous recommencez, la suite change. Biensûr vous avez envie, une fois que votre programme est stable, de pouvoir changer la graine, donc d'avoir différentes suites de nombres (Un) et ça, ça peut s'automatiser. Je ne vais pas insister là-dessus, mais on peut utiliser par exemple des nombres donnés par l'horloge de l'ordinateur, et ça c'est tout-à-fait standard. Mais le petit soucis de la suite (Un) que nous avons définie, c'est qu'en fait il n'est pas difficile de voir qu'elle est périodique. Périodique signifiant qu'à partir d'un rang n0, vous retrouvez toute votre suite et elle va se répéter tous les n0. Tous les blocs de taille n0. Et donc, c'est un ça peut paraître un peu étrange donc, de vouloir simuler le hasard avec des suites périodiques, et c'est inévitable de considérer un nombre fini de nombres, puisque l'ordinateur a une mémoire finie. C'est pour ça qu'on prend ces suites définies avec ces congruences, on finit par revenir au point de départ. Donc la conséquence immédiate, c'est que la période doit être plus grande que le nombre de termes que vous utilisez. Et par exemple, pour revenir à Scilab, on peut montrer, à cause des choix qui ont été faits pour a, n et c, on peut vérifier, croyez-moi sur parole ce n'est pas important, que la période, donc le rang à partir duquel vous revoyez la suite telle quelle, c'est exactement M, et donc c'est de l'ordre de 2 milliards. Donc si vous appelez moins de 2 milliards de fois, vous faites une suite où il y a moins de 2 milliards de termes, une suite (Un), vous n'allez pas retourner au point de départ. Donc la conclusion, qu'il faut retenir de cette petite introduction, c'est qu'un ordinateur, il génère une suite de nombres qu'on qualifie de pseudoaléatoire, compris entre 0 et 1, c'est tout ce qu'il est capable de faire, et la question naturelle que vous pouvez vous poser c'est : quelle est la qualité du générateur que vous avez à votre disposition? Qualité c'est un terme vague pour comprendre que vous voulez comprendre quel est l'écart qu'il a par rapport à un hasard qui serait parfait, si on avait vraiment une vraie suite de nombres aléatoires indépendants dans [0, 1]. Donc ça c'est tout un art de mettre en place des tests et vérifier que vous avez un bon générateur pseudoaléatoire. Et dans ces séances, nous allons nous placer en aval de ce problème, nous allons supposer que nous avons un bon générateur de nombres pseudoaléatoires (Un), on va faire comme si c'était vraiment des variables indépendantes, et qui ont toutes une loi uniforme dans [0, 1], et quelle est la question fondamentale? C'est est-ce qu'à partir de ça, vous pouvez construire une v.a. de loi donnée? C'est la question de base, et tous les développements que vous pouvez avoir sur la simulation du hasard, reposent là-dessus à la base. Biensûr après on peut faire et on fera des choses plus raffinées, mais il faut commencer par cette question fondamentale. Avant de continuer, je voudrais faire une petite parenthèse sur les histogrammes, pour celles et ceux qui ne seraient pas familiers avec cet objet. Donc un histogramme, vous l'avez sans doute quand-même vu, c'est un outil d'exploration de données empiriques, et on pense biensûr à des données qui sont aléatoires, et l'idée de base est très simple, c'est que, on répartit les valeurs des données en classes, en général on prend des classes de largeurs identiques, des intervalles de largeurs identiques, et la hauteur de chaque colonne qu'on va mettre dans ce diagramme, est déterminée par le nombre de valeurs qui tombent dans la classe correspondante. Et donc, dans l'esprit de la vision fréquentiste des probabilités si on interprète ça comme des données générées par un certain processus aléatoire, on normalise de telle sorte, que l'aire totale des colonnes soit égale à 1. Donc ça a, à peu près cette tête. Là j'ai mis un exemple complètement arbitraire. On a donc ces colonnes et il y a un certain nombre de classes, ou d'intervalles, qui supportent ces colonnes. Biensûr, une question qui vient immédiatement à l'esprit, si vous avez des données qui viennent de v.a. qui ont des valeurs réelles, donc qui sont continues, ce qu'on est en train de faire là, c'est approximer, discrétiser, les valeurs que prennent ces v.a. Donc, la question qui se pose, tout-de-suite, c'est évidemment, on a envie de prendre des classes de largeurs très petites, pour pouvoir au mieux coller aux variables qu'on est en train d'observer, et donc séparer les deux variables voisines, qui sont faites, vraiment, de valeurs différentes. Et donc, pour illustrer ce problème, un petit exemple : imaginez que vous tiriez 10000 variables gaussiennes centrées réduites, indépendantes, il est évident que si à fauche vous vous amusiez à mettre seulement, là j'ai, 1, 2, 3, 4, 5 colonnes, là vous voyez on représente la courbe en cloche, donc pas de soucis, ça approxime extrêmement mal cette courbe, et donc on a envie de prendre plein d'intervalles pour avoir plein de colonnes, et ici on fait l'extrême inverse, c'est-à-dire qu'il y en a tellement que, c'est aussi mauvais. Donc, il faut un compromis, et comme vous vous en doutez, si on a un certain nombre de données, ce compromis, il va dépendre du nombre de données, donc du nombre de valeurs que vous avez, parcequ'évidemment, si vous avez trop peu de données et que vous mettez trop de colonnes, ça va être mauvais, et donc, l'idéal que l'on essaie d'adopter en pratique, je ne justifierai pas ce critère maintenant, c'est de prendre le nombre de colonnes donc, qui est de l'ordre de la racine du nombre de données, donc du nombre de racines carrées du nombre de valeurs que vous avez. Donc, nous allons passer à la première partie de notre programme, qui est : Simuler des Variables Aléatoires Je vous rappelle le but : c'est de générer une v.a. X, à partir d'une v.a. uniforme. On suppose que ça on sait le faire. Et on se pose cette question : comment je vais faire, si je me donne une v.a. a priori quelconque? Et dans un premier temps, nous allons commencer par la simulation de v.a. discrètes. Donc, qui prennent des valeurs entières. Je vous montrerai deux choses, c'est, premièrement, des méthodes particulières pour des lois usuelles, donc, qui tirent parti, vraiment, des caractéristiques de ces lois, et je vais vous montrer aussi, une méthode générale. Commençons par la plus simple des lois discrètes, qui est la loi de Bernoulli de paramètre p, ce que j'annonce, c'est que, si vous prenez une v.a. U qui est uniformément distribuée dans l'intervalle [0, 1], donc la notation que l'on utilise en Couramment, c'est ce signe-là, pour dire que U est distribué, suit une loi uniforme dans l'intervalle 0, 1. Alors, si vous introduisez l'indicatrice que cette variable U soit plus petite ou égale à p, donc vous appelez ça X, en fait, on va vérifier tout de suite que X suit une loi Bernoulli de paramètre p. Donc si vous faites un petit dessin, imaginez j'ai l'intervalle 0, 1, je vais découper en deux morceaux, un morceau de longueur p et un morceau de longueur 1 mois p et l'idée, c'est que je tire une variable uniforme et je regarde si elle tombe là ou là. Et plus formellement, on l'a bien, cette propriété, parce que si on calcule la probabilité que X vaille 1, qui est, par définition, la probabilité que U soit plus petit ou égal à p, c'est l'intégrale de 0, 1 de l'indicatrice que U soit plus petit ou égal à p et on obtient immédiatement p. Donc c'est assez simple. Donc la loi qui nous vient immédiatement à l'esprit, c'est la loi binomiale, une fois qu'on a fait la loi Bernoulli. Donc elle a deux paramètres, n et p, le nombre de tirages et le paramètre p, qui représente la probabilité de succès. Et ce que je dis, c'est que si vous avez U 1 etc. U n, n variables uniformes qu'on tient en 0, 1 indépendantes, alors si vous prenez la somme des indicatrices U 1 plus petit ou égal à p plus U 2 plus petit ou égal à p etc. jusqu'à U n plus petit ou égal à p. C'est variable aléatoire que j'appelle X, cette somme, suit une binomiale de paramètres n, p. Et c'est assez immédiat, puisqu'on vient de voir que chacune de ces variables aléatoires est Bernoulli de paramètre p. Elles sont indépendantes et donc, ça correspond exactement à la définition d'une loi binomiale. On fait n lancers, n tentatives, et on compte combien on a de succès. Et le succès, c'est un U avec une probabilité p et c'est quand on a un 1. Une autre loi tout à fait fondamentale est la loi géométrique de paramètre p et donc on peut l'interpréter comme la loi du premier temps de succès dans une suite d'expériences aléatoires indépendantes, ayant comme probabilité de succès p. On a envie de poser N, une variable aléatoire qui va suivre la loi géométrique, en disant tout simplement que c'est le premier essai à partir duquel on a notre variable uniforme qui est plus petite ou égale à p. Et donc, par définition même de la loi géométrique, N va suivre une loi géométrique de paramètre p. Le défaut de cette simulation, le défaut de l'avoir comme ça, c'est que vous pouvez vérifier que le nombre moyen de variables uniformes utilisées est égal à 1 / p, puisque c'est tout simplement l'espérance d'une loi géométrique de paramètre p. Et si p est petit, donc si vous avez une petite chance de succès, 1 / p est très grand, donc a priori, vous devriez utiliser un grand nombre de variables uniformes U i pour espérer voir se réaliser une loi géométrique. Donc il y a une méthode astucieuse avec une seule variable aléatoire uniforme, qui consiste en la chose suivante : vous prenez une uniforme dans 0, 1 donc, et vous construisez la variable aléatoire suivante : 1 plus la partie entière du logarithme népérien de U divisé par le logarithme népérien de 1- p. Et je prétends que cette variable aléatoire suit la loi géométrique de paramètre p. Alors, E(x), c'est la notation pour la partie entière, donc je rappelle ici que c'est l'entier qui satisfait cette inégalité, donc on prend l'entier le plus grand possible proche de x par en dessous, comme ça. Alors pourquoi c'est vrai? On va vérifier par un petit calcul. Donc j'appelle X cette variable aléatoire, qui est 1 plus la partie entière de ce rapport de logarithme, je prends un entier non nul et je calcule la probabilité que X vaille k. Donc là, j'ai juste réécrit ce que ça veut dire, en faisant passer la 1 de l'autre côté. Cette partie entière vaut k- 1. J'utilise la définition de la partie entière, donc c'est la probabilité que ce quotient soit entre k- 1 et k, l'inégalité étant large et ici stricte. Et je développe simplement, je multiplie l'inégalité par cette quantité qui est négative, donc ça inverse le sens de l'inégalité. J'obtiens cet encadrement et je réécris tout simplement cette chose-là comme ça et cette chose-là comme ça, donc là j'ai vraiment rien fait de particulier. Il reste à constater que par définition de la loi uniforme, le fait qu'elle soit comprise entre ça et ça, c'est exactement la distance qui sépare ces deux points, celui-là et celui-là, donc c'est (1- p) puissance k- 1 moins (1- p) puissance k. Et ça fait (1- p) k- 1 fois p, qui est exactement la probabilité qu'une variable aléatoire géométrique prenne la valeur k, si vous vous souvenez de la définition d'une loi géométrique. On peut terminer cette séance par une méthode pour simuler une variable aléatoire qui suit une loi discrète quelconque. Pour l'instant, je vous ai montré des exemples où on tirait vraiment partie des propriétés des lois. On peut se demander s'il y a une manière systématique de le faire. Et donc, supposé que vous ayez une variable aléatoire qui prend des valeurs x i, a priori un nombre infini de variables possibles, pensez à la loi de Poisson, et que donc la probabilité qu'entre x i soit p i, donc on a assez de suites. Les p i donc, c'est des nombres positifs ou nuls et leurs sommes font 1. Et donc l'idée, c'est qu'avec une seule variable uniforme sur 0, 1, si on pose X égal x 1 fois l'indicatrice que U soit plus petit ou égal à p plus x 2 l'indicatrice que p 1 est plus petit que U 1, est plus petit ou égal que p 1 plus p 2 etc., on va tout simplement simuler la variable aléatoire en question. L'idée, c'est qu'on a une variable aléatoire U compte uniforme, on regarde si elle tombe dans cet intervalle ici, qui est défini par ces deux valeurs. Et si c'est le cas, on attribue à X la valeur x i. On peut tout de suite voir le petit souci de cette méthode. Pensez, par exemple, à la loi de Poisson où donc on a effectivement un nombre infini de valeurs prises par les x i, qui sont les entiers. Cette méthode risque d'être très lente, si vous voulez explorer des grandes valeurs de X. Et cette lenteur est vraiment liée tout simplement à la vitesse à laquelle la série de terme général p i converge. Donc, dans le cas de la loi de Poisson, on verra dans la séance suivante, qu'il y a une façon plus astucieuse de le faire, plutôt que de faire comme ça, mais au moins ça a l'avantage de montrer que, conceptuellement, on peut toujours se ramener à ça. Et le cas particulier, évidemment, c'est si vous avez un nombre fini de valeurs possibles, donc cette somme est finie, vous avez aussi une manière systématique générale pour simuler une variable aléatoire discrète. Donc ceci achève cette première séance.
