Выбор критерия.

[Alm99]

Добрый день уважаемые форумчане! Поставлена задача исследования двух алгоритмов ГПСЧ, выбран линейный конгруэнтный метод и так намазываемый алгоритм с РСЛОС "Вихрь Мерсенна". Суть такова: имеется набор $\xi_{n}$, каждый такой элемент $\xi_{i}$, представляет собой сгенерированную пару чисел $x, y$. Сначала применялся конгруэнтный метод, а затем "Вихрь Мерсенна". Необходимо, чтобы числа $x, y$ каждого соседнего набора $\xi_{n+1}$ отличались как можно более от чисел предыдущего набора $\xi_{n}$, т.е были независимы. Так вот вопрос, что можно выбрать в качестве критерия независимости этих пар чисел для каждого набора, чтобы сравнить какой алгоритм эффективнее генерирует псевдослучайные числа?

[slavav]

Тестирование_псевдослучайных_последовательностей

[Alm99]

slavav в сообщении #1447767 писал(а):

Тестирование_псевдослучайных_последовательностей

Ну тогда я могу задать еще один глупый вопрос, мне же просто тогда получается надо рассмотреть корреляционную зависимость от двух величин для каждой пары соседних наборов?

[Alm99]

Просто если коэффициент корреляции равен нулю, это не означает, что элементы в последовательности независимы... А мне надо именно исследовать то, что соседний набор независим от предыдущего, и все остальных, расположенных до него. Поэтому я поинтересовался. Я читал книгу Кнута, там описано про тестирование именно на случайность, на равномерность, но распределение и так равномерно. А вот независимы ли $\xi_{n}$...? К тому же у меня получается, что каждый такой набор $\xi_{i}$ еще и имеет размерность m=2.

[slavav]

Я бы собрал все пары $(x_i, y_i)$ в одну последовательность $x_1, y_1, x_2, y_2, \dots, x_i, y_i, \dots$ и тестировал бы её тестами из NIST.
Так как статистические тесты выявляют не случайные подпоследовательности (это что вам нужно), то они покажут насколько независимы ваши пары.

[Alm99]

slavav в сообщении #1447833 писал(а):

Я бы собрал все пары $(x_i, y_i)$ в одну последовательность $x_1, y_1, x_2, y_2, \dots, x_i, y_i, \dots$ и тестировал бы её тестами из NIST.
Так как статистические тесты выявляют не случайные подпоследовательности (это что вам нужно), то они покажут насколько независимы ваши пары.

Хорошо, спасибо, буду пробовать!

[Alm99]

slavav в сообщении #1447833 писал(а):

Я бы собрал все пары $(x_i, y_i)$ в одну последовательность $x_1, y_1, x_2, y_2, \dots, x_i, y_i, \dots$ и тестировал бы её тестами из NIST.
Так как статистические тесты выявляют не случайные подпоследовательности (это что вам нужно), то они покажут насколько независимы ваши пары.

Правда есть проблема, у меня числа сгенерированные от 0 до 1, и они не в двоичной форме, а эти тесты работают для бинарных чисел, т.е мне мои 200000 x и y придется переводить в двоичный код...

[Someone]

Alm99 в сообщении #1447889 писал(а):

Правда есть проблема, у меня числа сгенерированные от 0 до 1, и они не в двоичной форме

Странная проблема. Вы разве не знаете, что в компьютере вообще всё представляется в двоичной системе? Независимо от того, хотите Вы этого или нет.

[Alm99]

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

[Someone]

Alm99 в сообщении #1447913 писал(а):

Я думал для NIST надо преобразовывать, хотя не понимаю, с чего я это решил.

Может быть, Вы и правы, этого я не знаю. Там написано "Random Bit Generation". Ясно, что если напрямую рассматривать двоичный код числа с плавающей точкой как последовательность бит, то будет плохо, потому что там есть большая малослучайная часть — порядок. Ну, попробуйте взять мантиссу и сдвинуть её вправо в соответствии с порядком. Проще всего — умножить число на походящую степень двойки и преобразовать в целое число. Только надо разобраться с форматом представления числа в компьютере, там в некоторых форматах старший бит мантиссы может быть скрытым, потому что в нормализованном числе он всегда содержит единицу. Может быть, придётся пожертвовать младшим битом мантиссы.

В качестве альтернативы можно почитать, что написано о тестировании псевдослучайных последовательностей у Д. Кнута во втором томе "Искусства программирования на ЭВМ" (Donald E. Knuth, "The art of computer programming", Seminumerical algoritms, Third edition). Можно найти в интернете.

[gabber]

ГСЧ компов и так выдает независимые числа. Короткие серии могут и не пройти тест на независимость, но в этом и заключается независимость.
Образно говоря, если из миллиона раздач ни разу у двух игроков на руках не оказалось по тузовому флеш-роялю, то крупье явно жульничает.

[Someone]

Alm99
Наткнулся на статью о применении тестов NIST для проверки генераторов псевдослучайных чисел. Проверены $18$ генераторов.

[Alm99]

Someone
Почитал ее. Интересно, конечно все это...