Курсовая работа: Применение датчиков случайных чисел для имитации реальных условий

Если последовательность ведет себя удовлетворительно относительно тестов Т₁ , Т₂ , … , Т_n , мы не можем быть уверены в том, что она выдержит и следующее испытание Т_{n +1} . Однако каждый тест дает нам все больше и больше уверенности в случайности последовательности. Обычно последовательность проверяется с помощью полудюжины разных тестов. Если их результаты оказываются удовлетворительными, мы считаем ее случайной.

Различают два сорта тестов: эмпирические тесты, когда машина манипулирует с группами чисел последовательности и производит оценку с помощью определенных статистических критериев, и теоретические тесты.

Критерий χ²

Критерий χ² («хи-квадрат»), вероятно, самый распространенный из всех статистических критериев. Он используется не только сам по себе, но и как составная часть многих других тестов. Прежде чем приступить к общему описанию критерия χ² , рассмотрим сначала в качестве примера, как можно было бы применить этот критерий для анализа игры в кости. Пусть каждый раз бросаются независимо две «правильные» кости, причем бросание каждой из них приводит с равной вероятностью к выпадению одного из чисел 1, 2, 3, 4, 5 и 6. Вероятности выпадения любой суммы s при одном бросании представлены в таблице:

Сумма s= 2 3 4 5 6 7 8 9 10 11 12

Вероятность p_s = .

Если бросать кости n раз, можно ожидать, что сумма s появится в среднем np_s раз. Например, при 144 бросаниях значение 4 должно появится около 12 раз. Следующая таблица показывает, какие результаты были в действительности получены при 144 бросаниях.

Сумма s= 2 3 4 5 6 7 8 9 10 11 12

Фактическое число выпадений Y_s = 2 4 10 12 22 29 21 15 14 9 6

Среднее число выпадений np_s = 4 8 12 16 20 24 20 16 12 8 4 .

Отметим, что фактическое число выпадений отличается от среднего во всех случаях. В этом нет ничего удивительного. Дело в том, что всего имеется 36¹⁴⁴ возможных последовательностей исходов для 144 бросаний, и все они равновероятны. Каким же образом мы можем проверить, правильно ли изготовлена данная пара костей? Ответ заключается в том, что мы можем дать только вероятностный ответ, т.е. указать, насколько вероятно или невероятно данное событие.

Естественный путь решения нашей задачи состоит в следующем. Вычислим сумму квадратов разностей фактического числа выпадений Y_s и среднего числа выпадений np_s :

V=( Y₂ - np₂ )² +( Y₃ - np₃ )² +…+( Y₁₂ - np₁₂ )² .

Для плохого комплекта костей должны получаться относительно высокие значения V.

Предположим, что все возможные результаты испытаний разделены на k категорий. Проводится n независимых испытаний: это означает, что исход каждого испытания абсолютно не влияет на исход остальных. Пусть p_s – вероятность того, что результат испытания попадает в категорию s, и пусть Y_s – число испытаний, которые действительно попали в категорию s. Сформируем статистику V=. Вернемся к вопросу о том, какие значения V можно считать разумными. Ответ на это дает табл. 1, в которой приведено «распределение χ² с v степенями свободы» при разных значениях v. Следует пользоваться строкой таблицы с v=k-1; число «степеней свободы» равно k-1, т.е. на единицу меньше числа категорий.

Большим преимуществом рассматриваемого метода является то, что одни и те же табличные значения используются при любых n и любых вероятностях p_s . Единственной переменной является v=k-1. На самом деле приведенные в таблице значения не являются абсолютно точными во всех случаях: это приближенные значения, справедливые лишь при достаточно больших значениях n. Как велико должно быть n? Достаточно большими можно считать такие значения n, при которых любое из np_s не меньше 5; однако лучше брать n значительно большим, чтобы повысить надежность критерия.

На самом деле вопрос о выборе n не так прост. При больших значениях n могут сглаживаться локальные отклонения, такие, как следующие друг за другом блоки чисел с сильным систематическим смещением в противоположные стороны. При действительном бросании костей этого можно не опасаться, так как все время используются одни и те же кости, но если речь идет о последовательности чисел, полученных на ЭВМ, то такой тип отклонения от случайного поведения вполне возможен. В связи с этим желательно проводить проверку с помощью критерия χ² при разных значениях n, но в любом случае эти значения должны быть довольно большими.

Итак, проверка с помощью критерия χ² заключается в следующем. Проводится n независимых испытаний, где n – достаточно большое число. Подсчитывается число испытаний, результат которых относится к каждой из k категорий, и по формулам вычисляется значение V. Затем V сравнивается с числами из табл. 1 при v=k-1. Если V меньше значения, соответствующего p=99%, или больше значения, соответствующего p=1%, то результаты бракуются как недостаточно случайные. Если p лежит между 99 и 95% или между 5 и 1%, то результаты считаются «подозрительными»; при значениях p, полученных интерполяцией по таблице, заключенных между 95 и 90% или 10 и 5%, результаты «слегка подозрительны».

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

Как мы видели, критерий χ² применяется в тех случаях, когда результаты испытаний распадаются на конечное число 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) крайне маловероятны; КС-критерий должен указать, насколько они маловероятны.