Тестирование генератора случайных чисел

Тестирование генератора случайных чисел

Результаты анализа системы S, полученные методом статистического моделирования на ЭВМ, существенно зависят от качества используемых псевдослучайных квазиравномерных последовательностей чисел. Поэтому все применяемые генераторы случайных чисел должны перед моделированием системы пройти тщательное предварительное тестирование, которое представляет собой комплекс проверок по различным статистическим критериям, включая в качестве основных проверки (тесты) на равномерность, стохастичность и независимость. Рассмотрим возможные методы проведения таких проверок, наиболее часто используемые в практике статистического моделирования систем.

m
Σ
j = 1

Проверка равномерности последовательностей псевдослучайных квазиравномерно распределенных чисел <хi> может быть выполнена по гистограмме с использованием косвенных признаков. Суть проверки по гистограмме сводится к следующему. Выдвигается гипотеза о равномерности распределения чисел в интервале (0, 1). Затем интервал (0, 1) разбивается на m равных частей, тогда при генерации последовательности <хi> каждое из чисел х с вероятностью pj = 1/m, j = 1, т, попадает в один из подынтервалов. Всего в каждый j-й подынтервал попадает Nj чисел последовательности <хi>, i = 1, N, причем N = Nj. Относительная частота попадания случайных чисел последовательности <хi> в каждый из подынтервалов будет равна Nj/N.

Оценка степени приближения, т. е. равномерности последовательности <хi>, может быть проведена с использованием критериев согласия. На практике обычно принимается т = 20 ÷ 50,N = (10 2 ÷ 10 3 )m.

Суть проверки равномерности по косвенным признакам сводится к следующему. Генерируемая последовательность чисел <хi> разбивается на две последовательности:

Затем проводится следующий эксперимент. Если выполняется условие

то фиксируется наступление некоторого события и в счетчик событий добавляется единица. После N/2 опытов, когда генерировано N число, в счетчике будет некоторое число kN/2.

Геометрически условие (4.13) означает, что точка (х2i — 1, х2i) = 1, N, находится внутри четверги круга радиусом r = 1, что иллюстрируется рис. 4.11, б. В общем случае точка (х2i — 1, х2i) всегда попадает внутрь единичного квадрата. Тогда теоретически вероятность попадания этой точки в четверть круга

Читайте также:  Ксенон и галоген сравнение

Если числа последовательности <хi> равномерны, то в силу закона больших чисел теории вероятностей при больших N относительная частота 2k/N → π/4.

Проверка стохастичности последовательностей псевдослучайных чисел <хi> наиболее часто проводится методами комбинаций и серий . Сущность метода комбинаций сводится к определению закона распределения длин участков между единицами (нулями) или закона распределения (появления) числа единиц (нулей) в n-разрядном двоичном числе Xi. На практике длину последовательности N берут достаточно большой и проверяют все п разрядов или только l старших разрядов числа Xi.

Теоретически закон появления j единиц в l разрядах двоичного числа Xi описывается исходя из независимости отдельных разрядов биномиальным законом распределения:

где P (j, l) — вероятность появления j единиц в l разрядах числа Хi; p(1) = p(0) = 0,5 — вероятность появления единицы (нуля) в любом разряде числа Хi; C j l = l!/[j!/(lj)!].

Тогда при фиксированной длине выборки N теоретически ожидаемое число появления случайных чисел Хi с j единицами в проверяемых l разрядах будет равно nj = NC j l p l (1).

После нахождения теоретических и экспериментальных вероятностей P (j, l) или чисел nj при различных значениях ln гипотеза о стохастичности проверяется с использованием критериев согласия .

При анализе стохастичности последовательности чисел <хi> методом серий последовательность разбивается на элементы первого и второго рода (а и b), т. е.

В случае экспериментальной проверки оцениваются частоты появления серий длиной j. В результате получаются теоретическая и экспериментальная зависимости P(j, l), сходимость которых проверяется по известным критериям согласия, причем проверку целесообразно проводить при различных значениях р, 0

Последнее изменение этой страницы: 2017-02-07; Нарушение авторского права страницы

Есть программа которая в процессе работы использует встроенный генератор случайных чисел как проверить, что он действительно случайный.
По институту помню были какие то методы.


Digitman © ( 2004-09-07 10:35 ) [1]


> как проверить, что он действительно случайный

"В этом мире случайностей нет.."(с) МВ

Читайте также:  В чем отличие цифрового телевидения от аналогового


TUser © ( 2004-09-07 10:37 ) [2]

Он не случайный. Он псевдослучайный. Но ты можешь проверить получаемую послеждовтаельность чисел на соотвествие предъявляемым требованиям, например равномерность распределения и пр.


Боян Георгиев ( 2004-09-07 10:41 ) [3]

Можно проверить так:
Выполни Random(1000) 1000 разов и считай числа в 10 интервалам (1..100, 101..200, . 901..1000) и если счет в десетях интервалов равной, то генератор действительно случайный.


Digitman © ( 2004-09-07 10:42 ) [4]

если тебе необходимо виз.представление распределения, то организуй 2-мерный integer-массив, в котором № элемента — это "случайное" число в диапазоне, не превышающем границы массива, а значение этого эл-та массива ты будешь увеличивать на 1-цу всякий раз, когда генератор выдаст очер.число, совпадающее с номером этого элемента

в цикле "от забора и до обеда" получай "случйное" число, ищи соотв.элемент массива и инкрементируй найденный элемент

после завершения цикла любым удобным способом визуализируй массив в виде столбчатого графика, где по оси Х — "случайные" числа, а по оси Y — кол-ва "выпадений" каждого из этих чисел


Multy ( 2004-09-07 10:45 ) [5]

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


TUser © ( 2004-09-07 10:48 ) [6]

Я бы сказал, что распределение получаемого ряда чисел д.б. равномерным, а также равномерным д.б. распределение разниц между двумя последовательно полученными числами (некоторая гарантия независимости ряда, хотя, насколько я понимаю, все подобные ряды марковские и в той или иной степени каждое число зависит от предыдущего). Равномерность распределения проверяют по хи-квадрату.


Jeer © ( 2004-09-07 10:57 ) [7]

Поищи описание тестов DIEHARD. Это стандарт на сегодня для проверки "случайности" генераторов.


Рамиль © ( 2004-09-07 11:25 ) [8]

А с чего это распределение должно быть равномерным? Оно у Random равномерно. А программа может генерировать для себя любое распределение. Равномерность не может быть критерием случайности.

Читайте также:  Прикольные фотки на аву для пацанов


lehich © ( 2004-09-07 11:30 ) [9]


Jeer © ( 2004-09-07 11:32 ) [10]

В основе методов генерации "случайных" последовательностей с заданным распределением лежат, как правило" генераторы с равномерным распределением.
Если не оттестирован равномерный, то тестировать производный сложнее, да и неверно.


Romkin © ( 2004-09-07 11:37 ) [11]

Критериев полно. Возьми второй том Кнута, посмотри. Там они описаны. Но проверять генератор надо не на все критерии, а на нужные. А для этого надо знать, для чего нужен программе этот генератор. Одно дело — колоду карт перемешать, другое — найти методом Монте-Карло значение кратного интеграла. Во втором случае, кстати, прове6рка проще 🙂
А код генератора есть?


Koala © ( 2004-09-07 11:48 ) [12]

Не знаю точное условие задачи применения случайных чисел, но в клиент-банках (точно не скажу как) используется генератор случайных чисел совместно с движением мыши по экрану, генератор задает интервал при котором считываются координаты экрана и это более вероятность получения массива случайных чисел.

Вы можете добавить виджет генератора случайных чисел себе на сайт, просто разместив код:

Пример работы виджета: http://jsfiddle.net/bEp28/

Страница с результатами сохранена и будет доступна по ссылке: в течении 3 дней. Если вам нужно сохранить результат на более длительный период, создайте личный кабинет на сайте. Стоимость личного кабинета — 300 рублей.

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

Если вам не требуется функционал личного кабинета, то вы можете навсегда сохранить результат только этой генерации. Стоимость сохранения результата — 30 рублей.

Ссылка на основную публикацию
Adblock detector