Test d'algorithmes de génération de variables aléatoires

Quelles méthodes sont utilisées pour tester les algorithmes de génération de variables aléatoires?

La suite de tests Diehard est quelque chose de proche d'un standard d'or pour tester les générateurs de nombres aléatoires. Il comprend un certain nombre de tests où un bon générateur de nombres aléatoires devrait produire un résultat distribué selon une certaine distribution connue à laquelle le résultat utilisant le générateur testé peut ensuite être comparé.

ÉDITER

Je dois mettre à jour cela car je n'avais pas tout à fait raison: Diehard pourrait encore être beaucoup utilisé, mais il n'est plus entretenu et n'est plus à la pointe de la technologie. Le NIST a mis au point un ensemble de tests améliorés depuis.

Juste pour ajouter un peu à la réponse de Honk, la suite de tests Diehard (développée par George Marsaglia) sont les tests standard pour PRNG.

Il y a une belle bibliothèque Diehard C qui vous donne accès à ces tests. En plus des tests Diehard standard, il fournit également des fonctions pour quelques autres tests PRNG impliquant (entre autres) la vérification de l'ordre des bits. Il existe également une fonction pour tester la vitesse du RNG et écrire vos propres tests.

Il existe une interface R vers la bibliothèque Dieharder, appelée RDieHarder :

library(RDieHarder)
dhtest = dieharder(rng="randu", test=10, psamples=100, seed=12345)
print(dhtest)

Diehard Count the 1s Test (byte)

       data:  Created by RNG `randu' with seed=12345, 
              sample of size 100 p-value < 2.2e-16

Cela montre que le générateur RANDU RNG échoue au test de distance minimale / 2dsphere.

Pour tester les nombres produits par des générateurs de nombres aléatoires, les tests Diehard sont une approche pratique. Mais ces tests semblent un peu arbitraires et on peut se demander si d'autres devraient être inclus ou s'il existe un moyen de vraiment vérifier le caractère aléatoire.

Le meilleur candidat pour une définition d'une séquence aléatoire semble être le caractère aléatoire de Martin-Löf . L'idée principale de ce type de caractère aléatoire, magnifiquement développée dans Knuth, section 3.5 , est de tester l'uniformité pour tous les types de sous-séquences de la séquence de nombres aléatoires. Obtenir ce type de définition de sous-séquences s'est avéré très difficile, même lorsque l'on utilise des notions de calculabilité.

Les tests Diehard ne sont que quelques-unes des sous-séquences possibles que l'on peut considérer et leur échec exclurait le caractère aléatoire de Martin-Löf.

Vous ne pouvez pas prouver, car c'est impossible; vous ne pouvez vérifier que s'il n'y a pas d'autocorrélations ou de perturbations de distribution embarrassantes, et en effet Diehard est une norme pour cela. C'est pour les statistiques / physique, les cryptographes vérifieront également (entre autres) principalement à quel point il est difficile d'adapter le générateur aux données pour obtenir les valeurs futures.

Petite correction au post de Colin: le package CRAN RDieHarder est une interface avec DieHarder , la réécriture / extension / refonte Diehard effectuée par Robert G.Brown (qui me présente gentiment comme co-auteur basé sur mes wrappers RDieHarder) avec une contribution récente de David Bauer.

Entre autres choses, DieHarder inclut la batterie de tests NIST mentionnée dans le post de Mark ainsi que de nouveaux. Il s'agit d'une recherche en cours qui dure depuis un certain temps. J'ai donné une conférence à useR! 2007 sur RDieHarder que vous pouvez obtenir auprès de ici .

Il est rarement utile de conclure que quelque chose est "aléatoire" dans l'abstrait. Le plus souvent, vous voulez tester s'il a un certain type de structure aléatoire. Par exemple, vous voudrez peut-être tester si quelque chose a une distribution uniforme, avec toutes les valeurs dans une certaine plage également probables. Ou vous pouvez tester si quelque chose a une distribution normale, etc. Pour tester si les données ont une distribution particulière, vous pouvez utiliser un test d'adéquation tel que le test du chi carré ou le test de Kolmogorov-Smirnov.

Le test d'un générateur de nombres aléatoires comporte deux parties. Si vous souhaitez uniquement tester un générateur uniforme, alors oui, quelque chose comme la suite de tests DIEHARD est une bonne idée.

Mais souvent, vous devez tester une transformation d'un générateur uniforme. Par exemple, vous pouvez utiliser un générateur uniforme pour créer des valeurs exponentiellement ou normalement distribuées. Vous pouvez avoir un générateur d'uniforme de haute qualité - disons que vous avez une implémentation fiable d'un algorithme bien connu tel que Mersenne Twister - mais vous devez tester si la sortie transformée a la bonne distribution. Dans ce cas, vous devez effectuer une sorte de test de qualité d'ajustement tel que Kolmogorov-Smirnov. Mais pour commencer, vous pouvez vérifier que la moyenne et la variance de l'échantillon ont les valeurs que vous attendez.

La plupart des gens n'écrivent pas - et ne devraient pas - écrire leur propre générateur de nombres aléatoires uniforme à partir de zéro. Il est difficile d'écrire un bon générateur et facile de vous faire croire que vous en avez écrit un bon alors que vous ne l'avez pas fait. Par exemple, Donald Knuth raconte dans le volume 2 de TAOCP un générateur de nombres aléatoires qu'il a écrit et qui s'est avéré horrible. Mais il est courant pour les gens d'avoir à écrire leur propre code pour produire des valeurs aléatoires à partir d'une nouvelle distribution.

Le NIST publie une liste de tests statistiques avec une implémentation de référence en C.

Il y a aussi TestU01 par des gens intelligents, y compris le chercheur respecté de PRNG, Pierre L'Ecuyer. Encore une fois, il y a une implémentation de référence en C.

Comme l'ont souligné d'autres commentateurs, ceux-ci servent à tester la génération de bits pseudo aléatoires. Si vous transformez ces bits en une variable aléatoire différente (par exemple, la transformation de Box-Muller de l'uniforme à la normale), vous aurez besoin de tests supplémentaires pour confirmer l'exactitude de l'algorithme de transformation.