Résumé de la thèse de
François Panneton
Mots-clés :
Générateurs de nombres aléatoires,
récurrence linéaire, Monte Carlo, quasi-Monte Carlo,
simulation, ensembles de points uniformes, équidistribution,
réseau polynômial, uniformité.
Dans cette thèse, nous nous intéressons au
développement de nouveaux générateurs de nombres
pseudo-aléatoires qui utilisent une récurrence
linéaire dans un corps fini de caractéristique 2. Nous
utilisons aussi ces récurrences pour définir de
nouveaux ensembles de points qui peuvent être utilisés par
les méthodes
quasi-Monte Carlo.
Tout d'abord, nous définissons les critères avec lesquels
nous choisissons les paramètres de nos
générateurs. Parmi ces
critères, on retrouve l'équidistribution et la distance
minimale entre deux points d'un ensemble P_n de n points
dans [0,1)^t. Pour ce dernier, nous développons un nouvel
algorithme qui permet de trouver la distance minimale entre deux points
de P_n en temps moyen O(n).
Ensuite, nous définissons de nouveaux générateurs
qui utilisent une récurrence linéaire dans F_{2^w}, le
corps fini avec 2^w éléments. Ces
récurrences sont aussi utilisés pour définir de
nouveaux ensembles de points qui peuvent être utilisés
dans des applications quasi-Monte Carlo. La grande
majorité des projections en deux dimensions des nouveaux
ensembles de points construits avec ces récurrences ont la
propriété
d'être parfaites par rapport à l'équidistribution.
Nous développons également une autre famille de
générateurs, les générateurs WELL, qui
possèdent d'excellentes propriétés. En effet,
l'équidistribution est presque parfaite pour plusieurs
générateurs et le nombre de coefficients non nuls du
polynôme caractéristique est près de
k/2 où k est son degré. La vitesse d'exécution de
ces nouveaux générateurs
est comparable aux plus rapides des générateurs
disponibles.
Nous concluons cette thèse en analysant une famille de
générateurs proposé par G. Marsaglia [1]. Nous
effectuons une analyse théorique de ces
générateurs et cherchons les meilleurs du point de vue de
l'équidistribution. Malgré que ces
générateurs ont, en général, une bonne
équidistribution, la récurrence est trop simple pour
produire de bons
générateurs comme le démontre leurs nombreuses
faiblesses aux différents tests statistiques que nous leurs
avons fait
passer.
Bibliographie
[1] G. Marsaglia. Xorshift RNGs. Journal of Statistical Software, 8(14)
:1 6, 2003. Voir http://www.jstatsoft.org/v08/i14/xorshift.pdf.