PICSI

Après avoir conçu un générateur que l’on pense aléatoire (ou pseudo aléatoire) il faut le tester. En effet personne ne doit pouvoir prévoir de quelques manières que ce soit les valeurs générées. Il faut donc s’assurer qu’il n’y a aucune redondance dans la suite construite, que la suite construite est effectivement aléatoire. Pour cela on utilise des tests statistiques. Ces tests prennent en paramètre l’ensemble sur lequel on veut vérifier la propriété (ici la suite dont on veut savoir si elle est ou non aléatoire). Dans la pratique on considère deux hypothèses : la première, souvent notée H₀ représente le caractère à tester (ici le caractère « est aléatoire ») et le second, souvent notée H_a représente le contraire de H₀ (ici le caractère « n’est pas aléatoire »). D’un point de vue théorique, on s’appuie sur la loi mathématique de tendance vers la loi Normale et sur le test du Chi₂.

La première difficulté est qu’un test statistique ne peut pas valider l’hypothèse H₀ mais seulement conclure qu’elle n’est pas contradictoire avec l’observation (par contre il peut rejeter H₀ et valider H_a). Par exemple une de caractéristique de la propriété « est aléatoire » est l’équiprobabilité, c’est-à-dire que chaque valeur de la suite apparaît avec la même fréquence (dans notre cas 0 et 1 apparaissent avec une fréquence  1/2). Un premier test consiste donc à vérifier ce point.

Cependant conclure que la suite est aléatoire si elle passe ce test avec succès est absurde : en effet une suite du type 0101010 etc. passe ce test sans problème, mais ne peut en aucun cas être considéré comme aléatoire. Il est donc nécessaire de prévoir plusieurs tests complémentaires (i.e avec les mêmes hypothèses H0  et Ha mais avec des objectifs différents, par exemple le calcul de la fréquence et la recherche de chaînes périodiques dans la suite).

Par ailleurs un second problème spécifique au test de « est aléatoire » est justement qu’on test quelque chose qui doit être aléatoire : de ce fait il est nécessaire qu’une certaine proportion de tests conduise à des échecs, ce sera par exemple le cas dans le test en fréquence par blocs. Dans ce test, la suite est découpée en blocs sur lesquels un test en fréquence simple est effectué. Même si cela est peu probable un bloc constitué à 70% de 0 (ou de 1) peut apparaître dans la mesure où on test des suites de longueur largement supérieure au million (parfois même de l’ordre du milliard). L’interprétation des résultats est donc particulièrement complexe : il faut que les tests réussissent de manière générale mais il faut aussi qu’une partie échoue, sans toutefois que les échecs soient trop nombreux !