Применение датчиков случайных чисел для имитации реальных условий (стр. 3 из 3)
На самом деле вопрос о выборе n не так прост. При больших значениях n могут сглаживаться локальные отклонения, такие, как следующие друг за другом блоки чисел с сильным систематическим смещением в противоположные стороны. При действительном бросании костей этого можно не опасаться, так как все время используются одни и те же кости, но если речь идет о последовательности чисел, полученных на ЭВМ, то такой тип отклонения от случайного поведения вполне возможен. В связи с этим желательно проводить проверку с помощью критерия χ2 при разных значениях n, но в любом случае эти значения должны быть довольно большими.
Итак, проверка с помощью критерия χ2 заключается в следующем. Проводится n независимых испытаний, где n – достаточно большое число. Подсчитывается число испытаний, результат которых относится к каждой из k категорий, и по формулам вычисляется значение V. Затем V сравнивается с числами из табл. 1 при v=k-1. Если V меньше значения, соответствующего p=99%, или больше значения, соответствующего p=1%, то результаты бракуются как недостаточно случайные. Если p лежит между 99 и 95% или между 5 и 1%, то результаты считаются «подозрительными»; при значениях p, полученных интерполяцией по таблице, заключенных между 95 и 90% или 10 и 5%, результаты «слегка подозрительны».
Критерий Колмогорова-Смирнова (КС-критерий)
Как мы видели, критерий χ2 применяется в тех случаях, когда результаты испытаний распадаются на конечное число k категорий. Однако нередко случайные величины могут принимать бесконечно много значений. В частности, бесконечно много значений принимают вещественные случайные числа в интервале между 0 и 1. Хотя множество значений случайных чисел, полученных в вычислительных машине, неизбежно ограничено, хотелось бы, чтобы это никак не сказывалось на результатах расчетов.
В теории вероятностей и статистике принято использовать одни и те же обозначения при описании дискретных и непрерывных распределений. Пусть требуется описать распределение значений случайной величины ξ. Это делается с помощью функций распределения F(x), где F(x) = вероятность того, что (ξ≤x).
На рис. 1 представлены три примера. Первый, – функция распределения случайного бита, т. е. случайной величины ξ, принимающей значения 0 или 1, каждое с вероятностью 12. На 1, b – функция распределения вещественной случайной величины, равномерно распределенной между нулем и единицей, так что вероятность того, что ξ≤x, просто равна x, если 0≤x≤1. Рисунок 1, c показывает предельное распределение значений V в критерии χ2. Заметим, что F(x) всегда возрастает от 0 до 1 при увеличении x от -∞ до +∞.
Используя значения ξ1, ξ2, … , ξn случайной величины ξ, полученные в результате независимых испытаний, можно построить эмпирическую функцию распределения Fn(x):
Fn(x)=(число таких , ξ1, ξ2, … , ξnкоторые ≤x)/n.
Рисунок 1 – Примеры функций распределения
На рис. 2 показаны три эмпирические функции распределения. Там же и изображены и истинные функции распределения F(x). При увеличении n функции Fn(x) должны все более точно аппроксимировать F(x).
Критерий Колмогорова-Смирнова можно использовать в тех случаях, когда F(x) не имеет скачков. Он основан на разности между F(x) и Fn(x). Плохой датчик случайных чисел будет давать эмпирические функции распределения, плохо F(x). На рис. 2, b приведен пример, когда значения ξi слишком велики, так что кривая эмпирической функции распределения проходит слишком низко. На рис. 2, c представлен еще худший случай; ясно, что такие большие расхождения между Fn(x) и F(x) крайне маловероятны; КС-критерий должен указать, насколько они маловероятны.
Рисунок 2 – примеры эмпирических распределений
Для этого формируются следующие статистики:
Kn+=n max (Fn(x)- F(x));
Kn-=n max (F(x)- Fn(x)), при -∞<x<+∞.
Здесь Kn+ показывает, каково максимальное отклонение для случая Fn>F, а Kn- - каково максимальное отклонение для случая Fn<F.
Замечание. Наличие множителя n в формуле может показаться странным. Эти формулы не годятся для машинных расчетов, так как требуется отыскать максимальное среди бесконечного множества чисел. однако тот факт, что F(x) – неубывающая функция, а Fn(x) имеет конечное число скачков, позволяет определить статистики Kn+ и Kn- с помощью следующего простого алгоритма:
Шаг 1. Определяются выборочные значения ξ1, ξ2, … , ξn.
Шаг 2. Значения ξi располагаются в порядке возрастания так, чтобы ξ1≤ ξ2≤…≤ξn.
Шаг 3. Нужные статистики вычисляются по формулам
Kn+ =
max ( 
- F(xj));Kn- -=
max (F(xj) - 
), при 1≤j≤n.Заключение
В данной курсовой работе рассмотрены вопросы применения случайных чисел для прикладных задач математики и информатики, рассмотрены методы получения случайных чисел, начиная от самых ранних методов с использованием первых вычислительных машин по настоящее время.
После проведения обзора используемых в настоящее время датчиков случайных чисел, можно сделать вывод, что многие из них, несмотря на свою популярность, недостаточно хороши. Довольно часто какой-нибудь старый сравнительно неудовлетворительный метод передается от одного программиста к другому в слепую, и сегодняшний пользователь уже ничего не знает об его недостатках. Поэтому, при моделировании процессов и систем, в которых нужно учитывать случайные параметры, необходимо оценочно подходить к выбору подходящего датчика случайных чисел.
Один из акцентов курсовой работы был сделан на способы получения последовательностей как источника случайных чисел для ЭФМ. Рассмотрен вариант построения линейной конгруэнтные последовательности случайных чисел. Вообще, получение последовательностей псевдослучайных чисел сводится к задаче получения последовательностей, которые похожи на случайные, и определения, достаточно ли хороша генерируемая последовательность случайных чисел для выполняемой задачи. В работе рассмотрен вопрос использования критерия χ2 и КС-критерия для определения «случайности» чисел генерируемых числовых последовательностей, и показано, как могут соотноситься истинные и эмпирические функции распределения.
В качестве практической части приводится пример создания датчика случайных чисел, с последующей разработкой программы на языке Pascal.
Список литературы
1. Д. Кнут Искусство программирования для ЭВМ. т. 2, Получисленные алгоритмы. – М.: Издательство «Мир», 1977 – с. 5-98
2. Полляк Ю.Г. Вероятностное моделирование на электронных вычислительных машинах. - М.: Сов. Радио, 1971 — 386 с.
3. Вентцель Е.С., Овчаров Л.А. Теория вероятностей и её инженерные приложения, М: Наука, 1988 — 301 с.
4. Советов Б.Я. Моделирование систем: Курсовое проектирование: Учеб. пособие для вузов по спец. АСУ.- М: Высш. шк., 1988. – 135с.: ил
Приложение
1. program g1;
const n=100;
var x0, a, c, m, i: byte; x: array[0..n] of integer;
begin
writeln ('vvedite x0>=0:');
readln (x0);
writeln ('vvedite a>=2:');
readln (a);
writeln ('vvedite c>=0:');
readln (c);
writeln ('vvedite m>(x0 and a and c):');
readln (m);
if (x0>=0) and (a>=0) and (c>=0) then
if (m>x0) and (m>a) and (m>c) then
for i:=0 to n do x[i+1]:=(a*x[i]+c) mod m;
writeln ('chisla: ');
for i:=1 to n do write(x[i], ' ');
writeln;
end.
2. Program g2;
var I, l: integer;
begin
for I:=l to 10 do
write(random(200):4)
end.
3. program number(input, output);
var a, b, n, s, i : integer;
begin
writeln ('poluchenie sluchainih chisel iz intervala [a,b]');
write ('vvedite a');
readln (a);
write ('vvedite b');
readln (b);
writeln ('vvedite n');
readln (n);
for i:=1 to n do
begin
s:=trunc(random(b-a)+a);
writeln (i:2,'-e sluchainoe chislo:',s:4);
end;
readln;
end.