Применение датчиков случайных чисел для имитации реальных условий (стр. 2 из 3)
Как видно из приведенного примера, последовательность не всегда оказывается «случайной», если выбирать x0, a, c, m произвольно. Этот пример иллюстрирует тот факт, что конгруэнтные последовательности всегда «зацикливаются», т.е. в конце концов числа образуют цикл, который повторяется бесконечное число раз. Это свойство присуще всем последовательностям, имеющим общий вид Xn+1=f(Xn). Повторяющийся цикл называется периодом. Длина периода у данного примера равна 4.
Специального рассмотрения требует частный случай с=0, когда процесс выработки случайных чисел происходит несколько быстрее. Ограничение с=0 уменьшает длину периода последовательности, но при этом все еще можно получить относительно большой период. В первоначальном методе Лемера было принято с=0, хотя автор и упомянул возможность использования с≠0. Идея получения более длинных последовательностей за счет обобщения с≠0 принадлежит Томсону и независимо Ротенбергу.
Чтобы хоть немного упростить формулы, можно определить b=a-1. Можно сразу отбросить случай а=1, так как при этом Xn=(X0+nc) modm, и очевидно, что последовательность не случайная. Вариант а=0 еще хуже. Следовательно, для практических целей мы можем предположить, что а≥2, b≥1.
случайный число моделирование программирование
Выбор модуля
Как правильно выбрать число m? Оно должно быть достаточно большим, так как длина периода не может быть больше m. Другой фактор влияющий на выбор m, - это скорость выработки чисел: мы должны выбрать такое значение m, чтобы быстро вычислять (aXn+c) modm.
Выбор множителя и длины.
Как выбрать множитель a, чтобы получился период максимальной длины? Для любой последовательности, предназначенной для использования в качестве источника случайных чисел, важен большой период. Действительно, хотелось бы, чтобы период содержал значительно больше чисел, чем это необходимо для решения какой-либо одной задачи. Однако, большой период – это только один из необходимых признаков случайной последовательности. Вполне возможны абсолютно неслучайные последовательности с очень большим периодом. Например, при a=c=1 последовательность сводится к Xn+1=(Xn+1) modm. Очевидно, что ее период равен m, тем не менее ее никак нельзя назвать случайной.
Так как возможны только m различных значений, длина периода не может превышать m. Исследуем все возможные способы выбора a и c, которые дают период длины m.
Замечание! Когда период имеет длину m, каждое число от 0 до (m-1) встречается за период ровно один раз. Поэтому в этом случае выбор X0 не влияет на длину периода.
Теорема.
Длина периода линейной конгруэнтной последовательности равна m тогда и только тогда, когда
1) c и m взаимно простые числа;
2) b=a-1 кратно p для любого простого p, являющегося делителем m;
3) b кратно 4, если m кратно 4.
Теорема.
Если m=10e, e≥5, c=0 и X0 не кратно 2 или 5, период линейной конгруэнтной последовательности равен 5×10e-2 в том и только том случае, когда amod 200 принимает одно из следующих 32 значений:
3, 11, 13, 19, 21, 27, 29, 37, 53, 59, 61, 67, 69, 77, 83, 91, 109, 117, 123, 131, 133, 139, 141, 147, 163, 171, 173, 179, 181, 187, 189, 197.
Другие методы
Конечно, линейные конгруэнтные последовательности – не единственный из предложенных для вычислительных машин источников случайных чисел.
Одно из общепринятых заблуждений, когда речь идет о получении случайных чисел, заключается в том, что достаточно взять хороший датчик и слегка его изменить, чтобы выработать «еще более случайную» последовательность. Довольно часто это неверно. Например, мы знаем, что по формуле Xn+1=(aXn+c) modm можно получить довольно хорошие случайные числа. Не будет ли последовательность Xn+1=((aXn+c) mod (m+1)+c) modm еще более случайной? Ответ таков, что новая последовательность с большей вероятностью менее случайна.
Например, простейший пример зависимости Xn+1 от более чем одного из предыдущих значений реализуется в последовательность Фибоначчи Xn+1=(Xn+Xn-1) modm. Этот датчик рассматривали в начале пятидесятых годов. Он дает обычно длину периода, большую, чем m. Однако тесты с определенностью показали, что числа, получаемые из соотношения Фибоначчи, являются недостаточно случайными. Поэтому в настоящее время эта формула интересна главным образом как прекрасный «плохой пример».
Можно также рассмотреть датчики вида Xn+1=(Xn+Xn-k) modm, где k – достаточно большое число, предложенные Грином, Смитом и Клемом. При соответствующем выборе X0, X1, … , Xk эта формула обещает стать источником хороших случайных чисел. Этот датчик работает обычно быстрее, чем датчики, реализующие предыдущие методы, так как здесь не требуется никакого умножения. В статье Грина, Смита и Клема говорится, что при k≤15 последовательность не удовлетворяет тесту «проверка интервалов», хотя при k=16 тест проходит нормально.
Статистические тесты
Основная задача состоит в получении последовательностей, которые похожи на случайные. Мы уже видели, как добиться большого периода последовательности. Хотя это и важно, но большой период еще вовсе не означает, что последовательность хороша для работы. Как же решить, достаточно ли случайна последовательность?
Если дать любому человеку карандаш и бумагу и попросить его написать 100 случайных десятичных цифр, очень мало шансов на то, что он достаточно хорошо сможет с этим справиться. Люди стремятся избегать комбинаций, кажущихся им неслучайными, таких, как пары одинаковых соседних цифр (хотя примерно каждая из 10 цифр должна совпадать с предыдущей). Поэтому увидев таблицу действительно случайных чисел, любой человек скорее всего скажет, что они совсем не случайные, его глаз сразу же отметит некоторые видимые закономерности.
Все мы выделяем особенности телефонных номеров, номерных знаков машин и т.д., чтобы легче их запомнить. Главная мысль всего сказанного заключается в том, что мы не можем доверять себе в оценке, случайна или нет данная последовательность чисел. Необходимо использовать какие-то непредвзятые механические тесты.
Статистическая теория дает нам некоторые количественные критерии случайности. Возможным же тестам буквально нет конца.
Если последовательность ведет себя удовлетворительно относительно тестов Т1, Т2, … , Тn, мы не можем быть уверены в том, что она выдержит и следующее испытание Тn+1. Однако каждый тест дает нам все больше и больше уверенности в случайности последовательности. Обычно последовательность проверяется с помощью полудюжины разных тестов. Если их результаты оказываются удовлетворительными, мы считаем ее случайной.
Различают два сорта тестов: эмпирические тесты, когда машина манипулирует с группами чисел последовательности и производит оценку с помощью определенных статистических критериев, и теоретические тесты.
Критерий χ2
Критерий χ2 («хи-квадрат»), вероятно, самый распространенный из всех статистических критериев. Он используется не только сам по себе, но и как составная часть многих других тестов. Прежде чем приступить к общему описанию критерия χ2, рассмотрим сначала в качестве примера, как можно было бы применить этот критерий для анализа игры в кости. Пусть каждый раз бросаются независимо две «правильные» кости, причем бросание каждой из них приводит с равной вероятностью к выпадению одного из чисел 1, 2, 3, 4, 5 и 6. Вероятности выпадения любой суммы s при одном бросании представлены в таблице:
Сумма s= 2 3 4 5 6 7 8 9 10 11 12
Вероятность ps =
.Если бросать кости n раз, можно ожидать, что сумма s появится в среднем nps раз. Например, при 144 бросаниях значение 4 должно появится около 12 раз. Следующая таблица показывает, какие результаты были в действительности получены при 144 бросаниях.
Сумма s= 2 3 4 5 6 7 8 9 10 11 12
Фактическое число выпадений Ys = 2 4 10 12 22 29 21 15 14 9 6
Среднее число выпадений nps = 4 8 12 16 20 24 20 16 12 8 4 .
Отметим, что фактическое число выпадений отличается от среднего во всех случаях. В этом нет ничего удивительного. Дело в том, что всего имеется 36144 возможных последовательностей исходов для 144 бросаний, и все они равновероятны. Каким же образом мы можем проверить, правильно ли изготовлена данная пара костей? Ответ заключается в том, что мы можем дать только вероятностный ответ, т.е. указать, насколько вероятно или невероятно данное событие.
Естественный путь решения нашей задачи состоит в следующем. Вычислим сумму квадратов разностей фактического числа выпадений Ys и среднего числа выпадений nps :
V=( Y2- np2)2+( Y3- np3)2+…+( Y12- np12)2.
Для плохого комплекта костей должны получаться относительно высокие значения V.
Предположим, что все возможные результаты испытаний разделены на k категорий. Проводится n независимых испытаний: это означает, что исход каждого испытания абсолютно не влияет на исход остальных. Пусть ps – вероятность того, что результат испытания попадает в категорию s, и пусть Ys – число испытаний, которые действительно попали в категорию s. Сформируем статистику V=
. Вернемся к вопросу о том, какие значения V можно считать разумными. Ответ на это дает табл. 1, в которой приведено «распределение χ2 с v степенями свободы» при разных значениях v. Следует пользоваться строкой таблицы с v=k-1; число «степеней свободы» равно k-1, т.е. на единицу меньше числа категорий.Большим преимуществом рассматриваемого метода является то, что одни и те же табличные значения используются при любых n и любых вероятностях ps. Единственной переменной является v=k-1. На самом деле приведенные в таблице значения не являются абсолютно точными во всех случаях: это приближенные значения, справедливые лишь при достаточно больших значениях n. Как велико должно быть n? Достаточно большими можно считать такие значения n, при которых любое из nps не меньше 5; однако лучше брать n значительно большим, чтобы повысить надежность критерия.