§ 1 NOMBRES PSEUDO-ALEATOIRES

§ 1.1 Introduction

Etymologiquement, le mot "aléatoire" vient du latin "alea" qui signifie "dé". Un nombre aléatoire est un nombre "tiré aux dés", c'est-à-dire un nombre "au hasard".

L'expérimentation

On peut, en lançant le dé, faire des expériences sucessives et noter les résultats obtenus; par exemple,
	2, 5, 5, 6, 4, ...
Mais, dans une simulation, il faut généralement faire un très grand nombre d'expériences ce qui est très coûteux.

La simulation par des méthodes de Monte-Carlo

Nous montrerons que des algorithmes sont capables de produire des "nombres pseudo-aléatoires" c'est-à-dire des nombres qu'on peut utiliser à la place des nombres donnés par le dé. L'ordinateur étant capable d'effectuer un grand nombre d'expériences en peu de temps, on peut obtenir des résultats plus précis et à meilleur compte qu'avec la méthode d'expérimentation.
Alors que les nombres aléatoires sont engendrés par un phénomène aléatoire (par exemple par tirage à la roulette), les nombres pseudo-aléatoires sont calculés au moyen d'un algorithme; ils offrent néammoins les mêmes caractéristiques que les nombres aléatoires et peuvent avantageusement les remplacer dans les calculs.

On appelle "méthode de Monte-Carlo" toute méthode de calcul utilisant des nombres pseudo-aléatoires. Cette dénomination se réfère à la roulette du célèbre casino de Monte-Carlo. Parmi les applications des méthodes de Monte-Carlo, citons
 *	la programmation de jeux de hasard (dés, cartes, lotto, roulette, ...);
 *	la simulation de phénomènes aléatoires (
			cheminements d'un neutron au sein d'une matière fissile,
			fluctuations de charge d'un central téléphonique,
			longueur de la file d'attente à un guichet, ...).

§ 1.2 La méthode de congruence

La méthode de congruence est utilisée pour produire une suite de nombres pseudo-aléatoires.
Notons (y mod m) le reste de la division de y par m.

Au départ, on choisit judicieusement quatre nombres entiers positifs a, m, c, (Subscript[u, 0]).
On calcule				x0 = ((Subscript[u, 0])/m);
	(Subscript[u, 1])  = (a*(Subscript[u, 0])+c) mod m;	x1 = ((Subscript[u, 1])/m);	
	(Subscript[u, 2])  = (a*(Subscript[u, 1])+c) mod m;	(Subscript[x, 2]) = ((Subscript[u, 2])/m);
	(Subscript[u, 3])  = (a*(Subscript[u, 2])+c) mod m;	(Subscript[x, 3]) = ((Subscript[u, 3])/m);	
	(Subscript[u, 4]) = etc.

La suite (Subscript[u, 0]), (Subscript[u, 1]), (Subscript[u, 2]), ...est constituée de nombres entiers dans l'intervalle [0; m[.

La suite (Subscript[x, 0]), (Subscript[x, 1]), (Subscript[x, 2]), ...est constituée de nombres réels dans l'intervalle [0; 1[.

Voici un exemple:

a=7;m=11;c=0;u[0]=2;

Calculons	u[1] = Mod[a*u[0] + c, m] = Mod[7*2 + 0, 11] = Mod[14, 11] = 3;
		u[2] = Mod[a*u[1] + c, m] = Mod[7*3 + 0, 11] = Mod[21, 11] = 10;
		etc. Plus généralement,

u[i_]:=Mod[a u[i-1]+c,m]
Table[u[i],{i,0,13}]

x[i_]:=N[((u[i])/m)]
Table[x[i],{i,0,10}]

A partir de l'exemple, mettons en évidence certaines propriétés générales des suites engendrées par la méthode de congruence.

Une suite périodique

La suite u[0], u[1], u[2], ... est néssairement périodique et sa période est ≤ m. En effet, les valeurs possibles sont les restes de la division par m, à savoir 0, 1, 2, ..., (m-1). On est donc certain que la liste u[0], u[1], ..., u[m] comporte au moins deux valeurs égales entre lesquelles se déroule un cycle complet. Dans notre exemple, la période est égale à 10:

Show[Graphics[Table[Text[ToString[u[i]],{Cos[((i π)/5)],Sin[((i π)/5)]}],{i,1,10}],AspectRatio->Automatic,PlotRange->{{-1.1`,1.1`},{-1.1`,1.1`}}]]

Pour des valeurs a, m, c, u[0] convenablement choisies, on peut obtenir une suite dont la période est proche de m (dans notre exemple, la période est (m-1)). Dans la pratique, on choisit une grande valeur de m, typiquement m =

(2^32)

Dans ces conditions, même en tirant un million de nombres pseudo-aléatoires, l'utilisateur ne peut pas remarquer que la suite des valeurs tirées est périodique.

Une suite bien mélangée

Pour des valeurs a, m, c, u[0] convenablement choisies, on peut faire en sorte que la partie périodique de la suite est bien mélangée. Dans notre exemple, on peut le remarquer en parcourant le cercle représenté ci-dessus. On peut rapprocher cette propriété de l'opération qui consiste à battre aléatoirement un jeu de cartes.

Une suite distribuée uniformément

Les nombres réels x[0], x[1], x[2], ... sont des nombres pseudo-aléatoires dans l'intervalle réel
[0; 1[. Observons que la suite est distribuée uniformément.

Show[Graphics[Table[Text[ToString[N[x[i],2]],{x[i],0}],{i,1,10}],AspectRatio->Automatic,PlotRange->{{0,1},{-0.05`,0.05`}}]]

Dans la pratique, ce sont les valeurs réelles x[0], x[1], x[2], ... qui sont généralement utilisées en tant que nombres pseudo-aléatoires.

Dans le but d'obtenir une distribution uniforme sur un intervalle [r, s[ queconque, il suffit de considérer la suite

y[i_]:=r+(s-r) x[i]

Par exemple, pour une distribution sur l'intervalle [1, 7[:

r=1;s=7;
Show[Graphics[Table[Text[ToString[N[y[i],4]],{Cos[((i π)/5)],Sin[((i π)/5)]}],{i,1,10}],AspectRatio->Automatic,PlotRange->{{-1.3`,1.3`},{-1.1`,1.1`}}]]

C'est cette dernière image que nous voulons garder d'un générateur de nombres pseudo-aléatoires: celle d'une très longue suite de valeurs réelles bien mélangées et uniformément distribuées sur un intervalle [r, s[.

Pour obtenir une suite de nombres entiers, on peut prendre la partie entière de nombres réels. Par exemple, pour obtenir une suite d'entiers dont les valeurs sont {1, 2, 3, 4, 5, 6}, prenons la partie entière de la suite y[i] calculée ci-dessus:

r=1;s=7;
Show[Graphics[Table[Text[ToString[Floor[y[i]]],{Cos[((i π)/5)],Sin[((i π)/5)]}],{i,1,10}],AspectRatio->Automatic,PlotRange->{{-1.3`,1.3`},{-1.1`,1.1`}}]]

Clear[a,m,c,u,x,r,s,y]

Une suite statistiquement testée

Avant d'être utilisé, un générateur de nombres pseudo-aléatoires est testé. Il doit passer avec succès toute une batterie de tests statistiques et ne dénoter aucun défaut apparent.

§ 1.3 Le générateur de nombres pseudo-aléatoires
de Mathematica

Mathematica n'utilise pas la méthode de conguence, mais une autre méthode qui fait appel à un automate cellulaire (tel que ceux qu'on rencontre dans le jeu de la vie). Traitons maintenant le générateur de nombres psudo-aléatoires comme une "boîte noire": imaginons une suite de nombre pseudo-aléatoires produite par la méthode de congruence, ou par une autre méthode équivalente.

Nombres pseudo-aléatoires réels, uniformément distribués

La fonction Random[] produit un nombre réel pseudo-aléatoire uniformément distribué sur l'intervalle [0, 1[ :

RandomReal[]

La valeur retournée par Random[] est recalculée à chaque appel :

RandomReal[]

RandomReal[{0,1},10]

On peut obtenir une distribution uniforme sur un intervalle réel quelconque; par exemple sur l' intervalle [-1, 3[ puis sur [-(π/2);  (π/2)[  :

RandomReal[{-1,3},10]

RandomReal[{-(π/2),(π/2)},10]

Nombres pseudo-aléatoires entiers, uniformément distribués

La fonction Random[Integer, {1,6}] produit un nombre entier pseudo-aléatoire uniformément distribué sur {1, 2, 3, 4, 5, 6} :

RandomInteger[{1,6}]

La valeur retournée par Random est recalculée à chaque appel :

RandomInteger[{1,6}]

RandomInteger[{1,6},20]

Voici un autre exemple où les nombres pseudo-aléatoires sont uniformémemt distribués sur les nombres entiers de 0 à 36 (comme à la roulette) :

RandomInteger[{0,36},10]

Initialisation

Au démarrage de la session de Mathematica, le générateur de nombres pseudo-aléatoires est initialisé avec le poids faible de l'horloge, par exemple
		u[0] = nombre de millisecondes.
Par conséquent, deux sessions différentes de Mathematica produisent des suites de nombres pseudo-aléatoires presque toujours différentes. Vérifiez auprès de votre voisin que sa liste de nombres aléatoires diffère presque sûrement de la vôtre.

Il est parfois nécessaire de se référer plusieurs fois à la même suite de nombres aléatoires. Par exemple, dans une certaine méthode de cryptage, il faut utliser la même suite de nombres aléatoires pour crypter un message que pour le décrypter.
La fonction SeedRandom[n] permet de fixer la valeur n de l'initialisation 
		u[0] = n.

SeedRandom[987654]
RandomReal[{0,1},10]

On obtient ainsi une suite aléatoire reproductible :

SeedRandom[987654]
RandomReal[{0,1},10]

Exercices

Exercice 1 - 1

Dans le but d'effectuer la simulation suivante : " Tirer 20 nombres réels pseudo-aléatoires uniformément répartis entre 0 et 1 et afficher ceux qui sont compris entre 0.4 et 0.6", un étudiant a écrit le programme suivant :

echant=RandomReal[{0,1},20];

critQ[x_]:=0.4`≤RandomReal[]<0.6`

Select[echant,critQ]

Pourquoi le programme ne donne-t-il pas le résultat escompté ?
Comment le corriger pour qu'il accomplisse la tâche désirée ?