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.