Лекция: Критерии качества случайных последовательностей
Оценка качества последовательностей случайных величин
Чтобы быть уверенным в результатах имитационного эксперимента, предварительно необходимо убедиться в случайности используемых последовательностей случайных величин. А качество случайных чисел, получаемых программным способом на компьютере, зависит от того, насколько удачно построен алгоритм, или подобраны коэффициенты и начальные значения параметров генераторов.
Статистическая теория предлагает целый ряд количественных критериев случайности. Однако, если последовательность удовлетворяет относительно тестов Т1? Т2, ..., Т„, все же нет уверенности, что и тест Tn+i она выдержит столь же успешно. И все-таки чем больше тестов прошла последовательность, тем надежнее получаются результаты. Как правило, случайные числа проходят проверку с помощью следующих тестов: универсальных тестов (критерий χ2(«хи-квадрат»), критерий Колмогорова -Смирнова (КС-критерий)) и эмпирических тестов (проверка по моментам распределения, проверка равномерности, проверка серий, проверка интервалов, проверка комбинаций, проверка с помощью вычисления какой-нибудь общеизвестной константы).
Проверка по моментам распределения. Математическое ожидание и дисперсия равномерной случайной последовательности в интервале [0,1] равны 0,5 и 1/12 соответственно. Пусть имеется последовательность чисел ξ,i, ξ,2» ..., ξ n» полученная с использованием какого-нибудь программного генератора. Для этих чисел
Если генерируемые числа близки к равномерной случайной последовательности в интервале [0,1], то при достаточно больших
Проверка на равномерность. Интервал [0,1] разбивается на n равных подынтервалов и фиксируется, в какой из подынтервалов попадают числа ξi. Пусть m1 — количество случайных чисел, попавших в первый интервал; m2 — во второй и т.д. При этом
m1 + m2i +… + mn = N.
Затем вычисляются частоты попадания случайных чисел в каждый из подынтервалов
pi=mi/N
Если случайная последовательность чисел равномерная, то при больших N гистограмма (ломаная линия) должна приближаться к теоретической прямой у=1/n. Если число разбиений равно 10, то у = 0,1. На рис. 2.6 приведены результаты исследования последовательности случайных чисел (для N = 1000), полученных с использованием стандартной функции random языка Паскаль.
Рис.2,6 Результат исследования последовательности чисел на равномерность
Проверка по критерию χ2- Применение этого метода основано на следующей процедуре:
1. Отрезок [0,1] разбивается на n подынтервалов (n принимают равным от 10 до 20).
2. По совокупности N чисел подсчитывается количество mi, попавших в i-й подынтервал (i = 1,2, ...,n).
3. Определяется эмпирическое значение
где p=l/n.
4. Для доверительной вероятности а и числа степеней
свободы 1 = n — 1 определяется теоретическое значение критерия,
5. При выполнении условия χэ2< χт2 гипотеза о равномерности принимается, в противном случае — признается несостоятельной.
Проверка с помощью вычисления какой-нибудь общеизвестной константы. Для реализации этой проверки выбирается, например, вычисление числа п. Значение его известно и определено с большой точностью: π = 3,1416… Нужно выбрать какую-нибудь формулу, в записи которой участвует число я. Например, площадь круга: S = πR2 и, если R = 1, то S = π. Т. е., вычислив методом имитационного моделирования площадь круга с радиусом, равным единице, и проверив на сколько эта площадь отличатся от величины 3,1416, можно судить о качестве генератора, выдающего последовательность случайных величин, равномерно распределенных в интервале [0,1].