next up previous contents index
Next: Récurrences congruentielles de rang Up: Générateurs des nombres au Previous: Le développement historique   Contents   Index


Générateurs uniformes sur

On a vu dans la section précédente que les méthodes actuellement utilisées pour engendrer des nombres aléatoires sont toutes algorithmiques. Par conséquent, les suites obtenues sont purement déterministes. Elles doivent se comporter de manière à vérifier soit tous les théorèmes des probabilités soit certains d'entre eux ; on parle alors respectivement de suites pseudo-aléatoires ou quasi-aléatoires. Toutes les simulations se faisant sur ordinateur, les nombres que l'on peut représenter exactement ne sont qu'un sous-ensemble fini des rationnels. En multipliant ces rationnels par le plus grand dénominateur qui appraît dans la liste de ses réduits, on obtient un ensemble fini d'entiers. Sans perte de généralité, on peut donc se limiter au cas des nombres entiers-machine non-signés représentables sur une architecture à bits ; on note EMR() cet ensemble. Par exemple, pour l'architecture la plus courante à 32 bits, on a avec .

Plus généralement, un générateur algorithmique de nombres au hasard sur est un système dynamique discret , où est un ensemble discret et fini de symboles arbitraires et une application , couplé à une application de normalisation qui à chaque symbole associe un nombre dans . Il faut noter cependant que est un ensemble discret et fini et que l'application est la partie triviale du générateur ; tout l'aspect aléatoire est codé dans l'application . Partant d'un symbole initial , l'application répétée de produit une suite avec , appelée orbite émanant de . Les valeurs vont jouer le rôle de variables aléatoires uniformément distribuées sur . Or l'ensemble étant fini, toute orbite sera inéluctablement périodique et par conséquent les valeurs de la suite vont se répéter à partir d'un certain indice appelé période du générateur.

On récapitule ci-dessous les qualités requises par un bon générateur algorithmique de suites pseudo-aléatoires telles qu'elles sont définies par Brent [#!Bre!#] :

La recherche de nouveaux générateurs a pour but de satisfaire le plus grand nombre de critères de qualité mentionnés ci-dessus. Il s'agit d'un domaine de recherche où des compétences en arithmétique et en théorie probabiliste des nombres sont nécessaires et il est en plein essor actuellement pour répondre aux exigences, toujours plus grandes, de précision dans les prédictions issues de simulations.



Subsections
next up previous contents index
Next: Récurrences congruentielles de rang Up: Générateurs des nombres au Previous: Le développement historique   Contents   Index
Dimitri Petritis 2003-07-03