Question:
Comment puis-je tester la qualité d'un RNG?
stevenvh
2011-09-14 21:20:17 UTC
view on stackexchange narkive permalink

Sur electronics.stackexchange, nous avions une question sur la construction d'un générateur de nombres aléatoires réels. Puisque la méthode repose sur le bruit, qui n'est pas déterministe, la seule façon de tester la qualité du RNG semble être empirique.
N'étant pas un statisticien, j'ai suggéré de tester une longue séquence de bits pour la normalité, mais je n'ai pas idée quel résultat est acceptable et ce qui ne l'est pas. Par exemple, en comptant des bits simples, je suppose que nous avons un coup de pouce pour une distribution 499500/500500, mais quand le rapport est-il trop biaisé pour être acceptable? Idem pour les séquences de 2 bits et plus.
Bien sûr, si tester la normalité est une mauvaise idée ™, j'aimerais l'entendre, y compris de meilleures alternatives.

modifier
Diehard a été mentionné à quelques reprises, mais je ne suis pas sûr que cela réponde à ma question. Le test de normalité doit donner une distribution normale, avec de meilleures approximations de la courbe en cloche pour des séquences plus longues. Diehard semble également avoir des tests qui devraient aboutir à des distributions normales ou exponentielles. Mais ma question demeure: comment juger des résultats? Juste en regardant la courbe et en discernant une courbe en cloche? Pour revenir à mon premier exemple, une distribution 499500/500500 est définitivement OK, et une distribution 950000/50000 est définitivement un non-non, alors où se produit le basculement?

Avez-vous vu [Diehard] (http://www.stat.fsu.edu/pub/diehard/)?
Si je me souviens bien, le volume 2 de l'Art de la programmation informatique en a beaucoup sur ce sujet, même s'il est peut-être dépassé.
Je crois comprendre que [Dieharder] (http://webhome.phy.duke.edu/~rgb/General/dieharder.php) et [TestU01] (http://simul.iro.umontreal.ca/testu01/tu01.html) sont des suites de tests pour voir si un RNG est raisonnable en remplacement d'une source distribuée * uniformément *.Si l'on part de données censées être normales, il serait peut-être logique d'appliquer une transformation qui prendrait des données normalement distribuées et générerait des données uniformément réparties, puis appliquerait l'une des suites de tests?
Il existe des livres de [Kneusel] (https://www.amazon.com/Random-Numbers-Computers-Ronald-Kneusel/dp/3319776967/ref=sr_1_1?keywords=random+numbers+and+computers&qid=1557632098&s=books&sr=1-1) et [Johnston] (https://www.amazon.com/gp/product/1501515136/ref=ppx_yo_dt_b_asin_title_o05_s00?ie=UTF8&psc=1) qui sont très récents et incluent de nombreuses informations qui n'étaient pas disponibles audate de la 3e édition du chapitre 3 de TAOCP, volume 2, mais une grande partie de TAOCP est toujours pertinente, et il y a de la profondeur aux explications dans TAOCP qui manque sans surprise dans certaines parties des livres récents.J'ai trouvé les trois utiles.
Deux réponses:
#1
+11
Dirk Eddelbuettel
2011-09-14 23:10:28 UTC
view on stackexchange narkive permalink

J.M. déjà mentionné la batterie de tests Diehard originale de George Marsaglia. Pour autant que je sache, cet ensemble de tests n'est plus maintenu.

Robert Brown travaille depuis des années sur DieHarder, qui est

  • une réimplémentation GPL de la suite DieHard
  • plus des tests supplémentaires de la suite NIST
  • plus le développement de nouveaux tests

et vous pouvez trouver DieHarder utile.

[TestU01] (http://simul.iro.umontreal.ca/testu01/tu01.html) mérite également d'être pris en considération.
#2
+6
whuber
2011-09-16 02:17:29 UTC
view on stackexchange narkive permalink

Vous avez raison: les tests sont empiriques. Tout est fait dans un cadre standard de tests d'hypothèses. Différents tests sont appliqués pour évaluer différents comportements alternatifs des RNG. Comme toujours, l ' utilisateur est libre de choisir le niveau de confiance avec lequel chaque test est effectué. Ce niveau détermine la région critique de chaque test, qui est le "basculement" entre un résultat "significatif" et un résultat non considéré comme significatif.

En pratique, le niveau de confiance importe peu, car la plupart des RNG peuvent générer une si longue série de valeurs que tout écart à long terme par rapport au hasard complet, indépendant et équidistribué sera détectable avec une grande confiance. (C'est la raison principale pour laquelle une application correcte de suites de tests comme DieHard nécessite de générer un grand nombre de bits au minimum. Je me souviens - cela fait un moment - que les premières versions exigeaient 80 millions de bits.) En règle générale, un RNG passera de nombreux tests (sinon il n'aurait jamais vu le jour) mais il en souffrira clairement quelques-uns.



Ce Q&R a été automatiquement traduit de la langue anglaise.Le contenu original est disponible sur stackexchange, que nous remercions pour la licence cc by-sa 3.0 sous laquelle il est distribué.
Loading...