Комментарии 22
Не понял какая связь между P-значением и вероятность ошибки первого рода. Почему P-значение сравнивают именно с α? Можете прояснить этот момент?
И почему альфа выбирается такой маленькой. Т.е. если P-значение равно всего 0.02, то последовательность все-равно считается случайной несмотря на такую низкую вероятность?
И еще одно у вас в тексте написано:
В дальнейшем P-значение сравнивается с α, и если она меньше α, то нулевая гипотеза принимается и последовательность признается случайной.
это опечатка, и следует читать «и если она больше α»?
Если мы задаем такой низкий уровень строгости, то по элементарной логике (возможно ложной) создается впечатление, что 99 последовательностей из 100 пройдут тест.
Интуитивно просто кажется, что такое маленькое значение было бы оправдано, если бы последовательность принималась в случае если P<α, а не наоборот.
И поэтому я так понял, что тесты отбраковывают только самые очевидно неправильные последовательности, пропуская остальные. Это так? Или все-таки там какой-то подвох в матане?
Поток у аппаратных генераторов, как правило, хилый
Наиболее реально, это всяческие шумящие диоды и их лавинные пробои. Вот они дают «кошерные» числа. Например как тут: holdenc.altervista.org/avalanche/
Есть исходники, может кому интересно будет: Random-Sequence-Analysis (также там реализованы другие простые тесты).
P.S. На хабре все-таки не хватает поддержки либы для отрисовки математических формул, например MathJax. Представляю, как могло быть муторно делать все это в виде картинок.
Для тех кто, решит использовать этот пакет:
1. Программные коды представленные на сайте NIST далеко не оптимальны по скорости и памяти. Лучше реализовать самостоятельно.
В моем случае ускорение измеряется десятками раз. Для меня это критично, ибо объемы данных у меня таковы, что их реализацией будет считаться около двух лет, а мой оптимизированный вариант считает 1-2 недели. Думаю разница очевидна.
Причем ускорение достигается элементарными оптимизациями кода.
2. некоторые тесты содержат ошибки (в реализации на сайте ниста). То есть если ваши последовательности не проходят тест, не спешите с выводами — проверьте реализацию.
3. Там для вычисления вероятностей значимости в некоторых тестах используется функция igamc. Сравнивал полученные значения с данными Maple — погрешность составляла до 0,1. Последний факт сильно искажает результаты тестирования, распределение вероятностей значимости не проходит проверку на равномерность.
4. Поищите дополнительные публикации. Например, тест преобразования Фурье с ростом длины последовательностей начинает давать ошибку (так как реальное распределение статистик начинает отличаться от используемого приближения)
статья вызвала у меня неоднозначные чувства. с одной стороны - монументальный труд, явно выходящий за рамки простого обзора. Чего стоят только формулы, выложенные в виде картинок (да. Тогда еще хабр не позволял вставлять формулы - автор, мягко сказано, знатно помучился). При внимательном чтении все вроде бы сходится. Но при попытке реализовать самостоятельно тесты по описанным алгоритмам, сразу бросаются в глаза грубые опечатки с первой же главы. Например решил я реализовать Частотный блочный тест. и впал в ступор. а как рассчитываются числа pi?
считаю так - не сходится, считаю по-другому - не сходится. нарыл исходники тестов с сайта nist.gov - стало чуть понятнее, но не сильно. и подобных косяков в статье море. чтобы все их вскрыть, потребуется писать новую отдельную и не менее монументальную статью. я не готов, сорян.
И да - вишенка на торте. В середине статьи автор признается, что последовательность,
которую он гонял в тестах - вообще ни разу не случайна, и автор привел формулы, ее порождающие (читай главу Тест на линейную сложность).
Но внимание: все предыдущие тесты проходили очень успешно. И сразу доверие к таким тестам куда-то испарилось. Масло мне в огонь подкинул комментатор @vasiatka, после чего
доверие к тестам NIST вообще упало.
Неслучайность последовательности, перманентно мелькавшей в тексте, на мой проф.деформированный взгляд
видна невооруженным глазом, однако проходит все тесты. Вот взгяните на такие последовательности:
1011010101 - предложенная в статье
11011001111111011110010101011110001010101111101101110001001100000 - цифры числа Пи
110010001111100011001010001010001101111100011100000111 - цифры корня из двух
Не знаю, как по мне, видно что нижние 2 последовательности более сложны и имеют меньше повторяющихся паттернов.
А вообще статья шикарна, несмотря на выявленные недостатки. Автору плюс в карму. Хабр - торт.
Статистическая проверка случайности двоичных последовательностей методами NIST