Тестирование ГСЧ (diehard и т.п.)

[xatkaru]

Люди!
Где-нибудь вообще в природе существуют исходники тестов Кнута для генераторов случайных чисел, НЕ НА ФОРТРАНЕ????

[maxal]

Про "батарею Кнута" не знаю, а вот "Diehard Battery of Tests of Randomness" от Марсаглия доступна тут: http://www.stat.fsu.edu/pub/diehard/

[xatkaru]

Хм... Это я уж и сама нашла

[Владимир [unn]]

Вопрос к тем, кто использовал "DIEHARD test battery" для тестирования генераторов случайных чисел:
как интерпретировать результаты теста (p-values)?

[K-3]

Я не знаю, что такое "DIEHARD test battery", но p-value - это вот что.

У вас есть вероятностная гипотеза - так называемая нуль-гипотеза.
Вы выбираете вероятностный уровень значимости $\alpha$ - это вероятность того, что вы отвергнете гипотезу, хотя она верна. Например, $\alpha = 0.01$.

Вероятностный тест вам выдает это самое \mbox{p-value}.
Если \alpha < \mbox{p-value}, то гипотеза отвергается, иначе гипотеза принимается.

В русской литературе, по моим наблюдениям, \mbox{p-value} не любят (Если я не прав, кто-нибудь дайте ссылку), но иногда его называют степенью согласия данных с гипотезой

[Владимир [unn]]

Мне тоже так казалось. Но в этих тестах какая-то другая интерпретация. В доках написано:

Цитата:

Most of the tests in DIEHARD return a p-value, which should be uniform on [0,1) if the input file contains truly independent random bits. Those p-values are obtained by p=F(X), where F is the assumed distribution of the sample random variable X---often normal. But that assumed F is just an asymptotic approximation, for which the fit will be worst in the tails. Thus you should not be surprised with occasional p-values near 0 or 1, such as .0012 or .9983. When a bit stream really FAILS BIG, you will get p's of 0 or 1 to six or more places. By all means, do not, as a Statistician might, think that a p < .025 or p> .975 means that the RNG has "failed the test at the .05 level". Such p's happen among the hundreds that DIEHARD produces, even with good RNG's. So keep in mind that " p happens".

Причем тест детерминированной последовательности (скажем, последовательности единиц) дает p-value=1, т.е. если бы это было степенью согласия с гипотезой, то тест можно считать пройденным.

Фраза же о необходимости равномерности p-значений наталкивает на мысль, что их нужно проверять на равномерность, каким-нибудь Колмогоровым-Смирновым или Пирсоном....

В общем я потерялся

[maxal]

Вот такой ответ дал Ruptor:

Цитата:

Все тесты на случайность ограничены особым параметром - вероятностью, с которой тест "завалит" идеально случайные данные или другими словами хороший генератор. Ограничение на p до не более шести девяток или шести нулей - это значит вероятность один на миллион, что тест по ошибке отличит поток от случайного. Запустите этот тест миллион раз в автомате на совершенно случайных данных и они завалят любой такой тест на случайность. В некоторых случаях даже p=0.9 или p=0.1 - это заваленный тест. Всё зависит от условий их использования и от того насколько регулярно такие значения p видаются. Попробуйте, например, запустить DIEHARD на 10 миллионов самых первых байтов от RC4 для 10 миллионов ключей, потом вторых байтов, третьих - отклонение в p будет регулярное. Регулярное отклонение в p к 0 или к 1 - это и есть заваленный тест.