Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

L’aléatoire et les ordinateurs Pierre-André Zitt 17 janvier 2017 Random number

L’aléatoire et les ordinateurs Pierre-André Zitt 17 janvier 2017 Random number generation is too important to be left to chance. R. Coveyou Any one who considers arithmetical methods of producing random digits is, of course, in a state of sin. J. von Neumann Objectifs — Comprendre les objectifs de la génération de nombres aléatoires — Comment tester un générateur ? — Comprendre l’exemple du générateur linéaire. 1 Introduction : l’expérience du nombre de séries. On demande à N personnes de « simuler » 15 tirages de pile ou face successifs. Question pratique Le tirage est-il raisonnable ? Ressemble-t-il à ce qu’on obtiendrait en lançant une pièce équilibrée 15 fois de suite ? Pour répondre à cette question, on peut : 1. Choisir une certaine quantité dépendant des tirages : nombre de piles, longueur de la première série de piles, nombre de séries, ... 2. Calculer sa distribution théorique (quand les tirages proviennent de pile ou face équilibrés consécutifs), 3. Comparer la distribution théorique et la distribution observée. Prenons un exemple simple. Pour i = 1, ..., N on note Li = 1 la longueur de la plus longue suite de piles consécutifs dans le tirage proposé par la ie personne : pour le tirage FPPPFPFPPFPPFPF par exemple, la plus longue suite est de longueur 3. La quantité Li prend ses valeurs entre 0 et 15. Si le tirage provient d’une pièce équilibrée on peut déterminer la loi de Li en calculant les probabilités d’obtenir chaque valeur. On obtient le tableau suivant : ℓ ≤2 3 4 5 ≥6 P [L = ℓ] 0.32 0.30 0.19 0.10 0.09 1 Question mathématique Comment comparer la distribution observée et la distribution théorique ? Le meilleur résultat serait obtenu en utilisant un test statistique d’adéquation comme le test du χ2. En première approche, remarquons simplement que d’après le tableau, il y a une probabilité p ≈0.62 que la plus longue suite soit de longueur inférieure ou égale à 3. Cette proportion est-elle respectée sur les N individus, modulo les ﬂucutations d’échantillonage ? On note Xi = 1 si Li ≤3, Xi = 0 sinon, et Sn = P Xi. Si les tirages sont parfaits, Xi suit une loi de Bernoulli de paramètre p. Soit α un niveau de risque (par exemple 0.05) et zα le quantile d’ordre 1 −α/2 de la loi normale : si Z suit une loi normale alors P [|Z| ≤zα] = 1 −α. Théorème Un intervalle de ﬂuctuation Soit e = zα p p(1 −p)/ √ N. Alors P [SN/N ∈[p −e, p + e]] ≈1 −α. Application numérique : pour N = 30 personnes, on trouve les intervalles suivants. α 0.05 0.01 Intervalle sur les proportions [0.45, 0.80] [0.40, 0.86] Intervalle sur les eﬀectifs [13, 24] [12, 26] Autrement dit, dans 95% des cas, au moins 6 tirages sur les 30 donnent une série de longueur supérieure ou égale à 4. Dans 99% des cas, au moins 4 tirages sur les 30 sont dans ce cas. En pratique les êtres humains ont tendance à produire des suites « trop réparties » : en équilibrant trop les piles et les faces, en les alternant trop souvent, ... — Nous sommes de très mauvais générateurs de nombres aléatoires ; — ce manque de qualité peut se mettre en évidence par des tests statistiques. 2 Pourquoi l’aléatoire ? L’ordinateur est habituellement vu comme une machine entièrement déterministe (un programme répété dans les mêmes conditions donnera le même résultat). Dans quels cadres peut-on avoir besoin que l’ordinateur produise des résultats aléatoires ? La simulation De nombreux phénomènes réels, même quand ils sont déterministes, sont trop compliqués pour être représentés ﬁdèlement dans un modèle informatique. Il est alors naturel de prendre un modèle aléatoire. Si l’on veut étudier le modèle il faut savoir le simuler. Exemples : dynamique moléculaire ; modèles économiques multi-agents ; modèles de croissance (de villes, d’arbres, ... ) pour des univers virtuels, pour de la génération de textures... L’optimisation combinatoire Pour répondre à des questions déterministes il peut être utile de faire des choix aléatoires. : pour savoir si un grand entier est premier ou non, pour savoir si une position est bonne ou non dans un jeu (go, jeu de cartes, ...), pour résoudre approximativement des problèmes d’optimisation combinatoire (voyageur de commerce, ...) 2 Le calcul déterministe pour des problèmes complexes Dans le même ordre d’idées, une des applications les plus courantes des générateurs aléatoires est l’utilisation de méthodes de Monte-Carlo pour calculer des intégrales / des espérances de quantités aléatoires (en ﬁnance, en physique, ...) La cryptographie C’est un domaine omniprésent : chaque communication entre appareils électroniques utilise de nombreux protocoles cryptographiques. Les algorithmes de chiﬀrement et déchiﬀrement sont déterministes mais la quasi totalité de ces algorithmes nécessite d’engendrer des nombres aléatoires. En pratique, on procède toujours en deux étapes : 1. on construit un générateur de nombres (pseudo-)aléatoires uniformes : une fonction rand qui renvoie un nombre « aléatoire » dans un ensemble continu (souvent l’intervalle [0, 1]) ou discret (souvent l’ensemble {0, 1}). 2. À partir d’une source de hasard uniforme, on la transforme pour simuler la variable aléatoire d’intérêt. Ici on ne s’intéressera qu’à la première étape. Question pratique Comment programmer un ordinateur pour qu’il renvoie une suite (pseudo)-aléatoire uniforme ? 3 Les sources aléatoires uniformes en informatique 3.1 Les deux modèles de hasard « uniforme » Les deux modèles usuels d’aléatoire uniforme sont : — la loi uniforme discrète ; dans le cas le plus simple où il n’y a que deux possibilités c’est la loi du jeu de pile ou face équilibré ; — la loi uniforme continue (sur [0, 1]). Rappelons que les nombres réels peuvent être écrits en base 2 plutôt qu’en base 10 (on parle de développement dyadique) : Théorème Écriture dyadique Soit u ∈[0, 1). Il existe une unique suite (xn)n≥1 qui vériﬁe les conditions suivantes : 1. xn ∈{0, 1}, 2. xn n’est pas constante égale à 1 à partir d’un certain rang, autrement dit xn prend la valeur 0 une inﬁnité de fois, 3. u = P n xn2−n. La suite xn est appelée décomposition dyadique de u, c’est l’écriture du réel u en base 2. On note u = (0.x1x2 · · · xn · · · )2. Fixons un début de développement binaire, par exemple (0.00101)2. Les réels dont le développement dyadique commence ainsi sont ceux compris entre (0.00101)2 = 1/8 + 1/32 et (0.00110)2 = 1/8 + 1/16. La probabilité pour une loi uniforme de tomber dans cet intervalle est 1/32 = 1/25. Ce raisonnement est valable pour toute suite de 5 symboles dans {0, 1} : 3 autrement dit, en regardant les 5 premiers chiﬀres du développement dyadique d’un réel pris uniformément dans [0, 1], chacune des 25 suites possibles est choisie avec la même probabilité. Ceci donne plus généralement une correspondance remarquable entre l’aléatoire discret et l’aléatoire continu : Théorème Soit U une variable aléatoire de loi uniforme sur [0, 1]. Soit (Xn)n∈N la réprésentation dyadique de U. Alors (Xn)n∈N est une suite de variables de Bernoulli indépendantes de paramètre 1/2. Réciproquement si (Xn)n∈N est une suite iid de Bernoulli de paramètre 1/2, alors la série P n Xn 2n converge presque sûrement vers une variable U = (0.X1X2 · · · )2, dont la loi est uniforme sur [0, 1]. Cette correspondance théorique parfaite entre les deux modèles d’aléatoire élémentaires discrets et continus ne se traduit malheureusement pas par une correspondance pratique : les générateurs de bits aléatoires usuels ne donnent pas nécessairement de bons réels aléatoires, et réciproquement. 3.2 Ce qu’on peut attendre d’un générateur de nombres aléatoires Un bon générateur aléatoire devrait être indistingable du générateur idéal (la « suite de variables de Bernoulli indépendantes »). Cela se traduit par le fait qu’il devrait vériﬁer les propriétés suivantes : Équirépartition Pour tout intervalle [a, b] ⊂[0, 1], la fraction du nombre de points qui tombe dans [a, b] doit « converger » vers b −a. 1 n n X k=1 1ui∈[a,b] ≈(b −a). Équirépartition d’ordre supérieur Pour toute pavé P = QD i=1[ai, bi], 1 n X 1(unD+1,...,unD+D)∈P ≈ Y i (bi −ai). Et plus généralement... Pour tout k et toute fonction « test » f : [0, 1]k →R, on peut comparer f(U1, ..., Uk) pour le générateur aléatoire et pour une vraie suite de variables uniformes pour obtenir un test du générateur. Notons que ces propriétés idéales ne seront jamais vraiment atteintes. La formulation de l’équirépartition écrite ci-dessus n’est par exemple jamais vériﬁée si on interprète ≈comme une limite quand n tend vers l’inﬁni, puisqu’un générateur informatique ne peut renvoyer qu’un nombre ﬁni de valeurs possibles, donc certains intervalles [a, b] ne seraont jamais visités. On demandera alors plutôt que chacune des valeurs possibles apparaisse avec la même fréquence. Pour certaines utilisations en cryptographie on demande également : Imprévisibilité Même en ayant accès à tous les nombres (u1, ..., un), il n’est pas possible de prévoir un+1. Naturellement vériﬁer ces critères peut demander des algorithmes plus complexes uploads/s3/ alea-info.pdf