Две случайные последовательности

[slavav]

Даже на алфавите из 16 значений?
Усовершенствуем тест ГСЧ. Выполним его $16!$ раз для всевозможных перестановок алфавита последовательности, результат усредним.
Это долго, но реально. Вот тест отвечающий аксиоме. Жаль что не все они такие. :)

-- 16.02.2018, 20:06 --

Добавлю, что мой пример непрактичен. Я только продемонстрировал теоретическую возможность

[B@R5uk]

У топикстартера битовая последовательность получена прямым сочленением битовых представлений чисел с фиксированной разрядностью. Если же вместо фиксированной разрядности взять какой-нибудь код Хаффмана, то всё станет совсем плохо. Например, возьмём английский алфавит, сопоставим каждой букве какое-нибудь случайное значение частотности, построим префиксный код и возьмём текст, где случайные гласные и случайные согласные чередуются через один, и преобразуем согласно полученному коду. Результирующая битовая последовательность вряд ли будет содержать хоть какой-то намёк на закономерность чередования, которая лежит в её основе.

[Евгений Машеров]

files в сообщении #1292754 писал(а):

Насколько я разобрался, тот же тест NIST на уровне чисел не работает, а работает только на уровне двоичных разрядов. Я могу прогнать через NIST двоичные разряды моих чисел, на как мы уже выяснили, случайность двоичной последовательности вовсе не означает случайность числовой последовательности, полученной из двоичной.

Используйте DIEHARD, он не только с битами умеет...

[Евгений Машеров]

В общем, изящное рассуждение, что если биты случайны, то и функция от них случайна, не то, чтобы неверно. Оно просто сюда не относится. У нас не случайные биты, а биты, выдержавшие тест на случайность. Статистический тест. Который может давать ошибочные результаты. Ложноположительные и ложноотрицательные диагнозы. При заданной длине выборки мы можем маневрировать лишь меж ними. Чтобы одновременно сократить и число ложноположительных, и ложноотрицательных (ошибок I и II рода), надо увеличивать выборку. Мы можем придти к выводу, что длина выборки достаточна, чтобы вероятности ошибок были бы нужной малости, и поэтому верить результатам теста.
Но в данном примере биты участвуют в формировании числа в разной степени. Старший бит вносит больше, чем все остальные вместе взятые. Что приводит к тому, что статистические характеристики набора чисел, сформированных из битовой последовательности, определяются четвертью наличных бит - только "старшими". То есть эффективная длина выборки оказывается в разы меньше формальной длины её, и может оказаться, что при том, что формальная длина выборки достаточна для суждения о распределении, в действительности данных недостаточно.
Я бы советовал вместо специализированных тестов NIST, ориентированных на проверку битовых последовательностей, использовать проверку чисел, скажем, из DIEHARD. Вообще, лучше проверять именно то, что желаешь использовать.