2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




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

-- 16.02.2018, 20:06 --

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

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

 
 
 
 Re: Две случайные последовательности
Сообщение17.02.2018, 20:32 
Аватара пользователя
files в сообщении #1292754 писал(а):
Насколько я разобрался, тот же тест NIST на уровне чисел не работает, а работает только на уровне двоичных разрядов. Я могу прогнать через NIST двоичные разряды моих чисел, на как мы уже выяснили, случайность двоичной последовательности вовсе не означает случайность числовой последовательности, полученной из двоичной.


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

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

 
 
 [ Сообщений: 19 ]  На страницу Пред.  1, 2


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group