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!#] :

• Uniformité. La suite doit passer avec succès les épreuves d'uniformité de distribution (cf. chapitre ). La plupart de générateurs utilisés des nos jours, passent ces tests.
• Indépendance. L'orbite complète et des sous-orbites particulières doivent être indépendantes. Les générateurs les plus utilisés de nos jours remplissent cette condition pour toutes les sous-orbites du type pour des valeurs raisonnables de ().
• Longue période. Les programmes de simulation qui tournent sur des superordinateurs ont besoin de nombres aléatoires par seconde. Sachant que les programmes typiques ont des temps d'exécution allant de quelques heures à quelques mois, ils ont besoin de à nombres au hasard. Ceci impose une borne inférieure à la période des générateurs.
• Reproducitbilité. Pour pouvoir vérifier les programmes lors de leur développement, on doit être capable de reproduire exactement la suite de variables aléatoires générées.
• Portabilité. Encore pour des raisons de vérification, il est parfois nécessaire de faire exécuter le programme sur des machines différentes, éventuellement avec des longueurs de mots différentes. Si, par exemple, on transporte un programme développé sur une machine avec architecture de 32 bits sur une machine avec une architecture de 64 bits, il faut que les orbites émanant de la même racine soient identiques dans les deux cas.
• Sous-suites disjointes. Si une simulation est effectuée sur une machine multi-processeur ou si le calcul est distribué à travers un réseau, il faut que les sous-suites utilisées par chaque sous-tâche du programme soient indépendantes.
• Efficacité. Étant donné que l'appel à la routine du générateur s'effectue un très grand nombre de fois, il faut que son programme soit le plus simple possible, avec un minimum d'opérations nécessaires.

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.