Épreuves empiriques sur les suites pseudo-aléatoires

Dans le chapitre , on a vu certaines méthodes permettant d'engendrer sur ordinateur de nombres pseudo-aléatoires de manière à maximiser la période du générateur. Certains constructeurs d'ordinateurs installent des programmes très efficaces de génération de nombres aléatoires mais omettent parfois d'indiquer l'algorithme utilisé. Il est alors utile de posséder des épreuves objectives qui permettent de détecter la présence de sous-périodes.

Deux autres caractéristiques importantes de la suite générée sont son uniformité et son écart par rapport à une suite idéale. Des épreuves arithmétiques permettent de décider objectivement si une suite est convenable.

Ni la période, ni l'uniformité de la distribution ne sont cependant les seuls critères de qualité pour un générateur. Prenons l'exemple du générateur . Pour toute valeur de , le générateur avec a comme période . Pour , et , on obtient la suite qui de toute évidence ne possède pas les caractéristiques que l'on attend intuitivement d'une suite aléatoire. Selon l'utilisation que l'on se propose de faire de la suite, on doit attacher plus d'importance à l'uniformité de la distribution ou aux propriétés statistiques. Durant les dernières années, des méthodes dites quasi-aléatoires ont été dévelopées. Pour les suites quasi-aléatoires, on privilégie l'aspect de l'uniformité et de faible écart au détriment de toute considération statistique. On obtient ainsi des suites pour lesquelles les moyennes ergodiques convergent très rapidement vers l'espérance théorique mais où les autres théorèmes de la théorie des probabilités ne sont pas vérifiés. L'utilisation de ces suites donne de très bons résultats pour l'étude de systèmes relativement simples mais reste totalement inadaptée à l'étude de grands systèmes. Par ailleurs, une suite bien adaptée à un certain problème peut s'avérer totalement inadaptée à un problème légèrement modifié. Pour cette raison, l'étude de méthodes quasi-aléatoires n'est qu'effleurée dans ce cours consacré essentiellement à l'étude de systèmes complexes. On donne juste quelques épreuves arithmétiques pour l'étude de l'uniformité et de l'écart.

Pour les grands systèmes complexes, les méthodes pseudo-aléatoires, utilisant des suites qui, quoique déterministes, se comportent de telle manière que tous les théorèmes des probabilités soient vérifiés sont les seules adaptées. Ce livre est consacré presque exclusivement à leurs étude et utilisation. Pour les suites pseudo-aléatoires, on introduit des épreuves statistiques objectives qui permettent de décider des qualités statistiques des générateurs. Certaines des méthode utilisables sont exposées dans les paragraphes suivants.