Une mesure de l’aléatoire pour les générateurs linéaires congruentiels

Les générateurs linéaires congruentiels de la forme x k+1 = a x k + b modulo n sont très utilisés pour produire des suites pseudo-aléatoires. La question essentielle est : ‘’ De tels générateurs simulent-ils bien le hasard?’’ . Arnold a défini une constante [qui dépend du triplet ( a , b , n )] qu’il propose comme la mesure de l’aléatoire pour une telle suite. Dans le cas particulier des progressions arithmétiques (où a = 1), nous donnons une expression alternative de cette constante d’Arnold en fonction de la paire ( b , n ). Puis nous évaluons, la valeur moyenne de cette constante lorsque le couple ( b , n ) varie dans l’ensemble {( b , n ) : 0 ≤ b ≤ n }. Le résultat est sans surprise: les progressions arithmétiques sont de très mauvais générateurs aléatoires (au sens d’Arnold), mais notre étude permet de quantifier précisément cette mauvaise qualité.

L’exposé est fondé sur un travail commun de Eda Cesaratto, Alain Plagne et Brigittte Vallée. Il sera donné en anglais.