Критерий Колмогорова-Смирнова (КС-критерий)

 

Как мы видели, критерий χ² применяется в тех случаях, когда результаты испытаний распадаются на конечное число k категорий. Однако нередко случайные величины могут принимать бесконечно много значений. В частности, бесконечно много значений принимают вещественные случайные числа в интервале между 0 и 1. Хотя множество значений случайных чисел, полученных в вычислительных машине, неизбежно ограничено, хотелось бы, чтобы это никак не сказывалось на результатах расчетов.

В теории вероятностей и статистике принято использовать одни и те же обозначения при описании дискретных и непрерывных распределений. Пусть требуется описать распределение значений случайной величины ξ. Это делается с помощью функций распределения F(x), где F(x) = вероятность того, что (ξ≤x).

На рис. 1 представлены три примера. Первый, – функция распределения случайного бита, т. е. случайной величины ξ, принимающей значения 0 или 1, каждое с вероятностью 12. На 1, b – функция распределения вещественной случайной величины, равномерно распределенной между нулем и единицей, так что вероятность того, что ξ≤x, просто равна x, если 0≤x≤1. Рисунок 1, c показывает предельное распределение значений V в критерии χ². Заметим, что F(x) всегда возрастает от 0 до 1 при увеличении x от -∞ до +∞.

Используя значения ξ₁, ξ₂, … , ξ_n случайной величины ξ, полученные в результате независимых испытаний, можно построить эмпирическую функцию распределения F_n(x):

F_n(x)=(число таких , ξ1, ξ2, … , ξn которые ≤x)/n.

 

Рисунок 1 – Примеры функций распределения

 

На рис. 2 показаны три эмпирические функции распределения. Там же и изображены и истинные функции распределения F(x). При увеличении n функции F_n(x) должны все более точно аппроксимировать F(x).

Критерий Колмогорова-Смирнова можно использовать в тех случаях, когда F(x) не имеет скачков. Он основан на разности между F(x) и F_n(x). Плохой датчик случайных чисел будет давать эмпирические функции распределения, плохо F(x). На рис. 2, b приведен пример, когда значения ξ_i слишком велики, так что кривая эмпирической функции распределения проходит слишком низко. На рис. 2, c представлен еще худший случай; ясно, что такие большие расхождения между F_n(x) и F(x) крайне маловероятны; КС-критерий должен указать, насколько они маловероятны.

 

Рисунок 2 – примеры эмпирических распределений

 

Для этого формируются следующие статистики:

K_n⁺=n max (F_n(x)- F(x));

K_n^-=n max (F(x)- F_n(x)), при -∞<x<+∞.

Здесь K_n⁺ показывает, каково максимальное отклонение для случая F_n>F, а K_n^- - каково максимальное отклонение для случая F_n<F.

Замечание. Наличие множителя n в формуле может показаться странным. Эти формулы не годятся для машинных расчетов, так как требуется отыскать максимальное среди бесконечного множества чисел. однако тот факт, что F(x) – неубывающая функция, а F_n(x) имеет конечное число скачков, позволяет определить статистики K_n⁺ и K_n^- с помощью следующего простого алгоритма:

Шаг 1. Определяются выборочные значения ξ₁, ξ₂, … , ξ_n.

Шаг 2. Значения ξ_i располагаются в порядке возрастания так, чтобы ξ₁≤ ξ₂≤…≤ξ_n .

Шаг 3. Нужные статистики вычисляются по формулам

 

K_n⁺ =  max (  - F(x_j));

K_n^{- -}=  max (F(x_j) - ), при 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.