Материал: Имитационное и статистическое моделирование — копия

Программный датчик БСВ обычно вычисляет значения z1, z2, z3, … по ка- кой-либо рекуррентной формуле вида

при заданном стартовом значении z0.

Заданное значение z0 полностью определяет посредством формулы (1.2) всю последовательность z1, z2, z3, … , поэтому величину z на выходе датчика БСВ называют псевдослучайной величиной. В практическом применении датчиков БСВ статистические свойства псевдослучайной последовательности чисел в широких пределах идентичны свойствам «чисто случайной» последовательности.

Программные датчики БСВ обладают, по сравнению с аппаратными датчиками, следующими достоинствами:

–простотой создания датчиков;

–простотой применения;

–простотой тиражирования датчиков;

–надёжностью;

–быстродействием;

–компактностью;

–высокой точностью достижения необходимых статистических свойств, сравнимой с точностью представления вещественных чисел;

–возможностью повторного воспроизведения, когда это нужно, любой последовательности случайных значений без их предварительного запоминания.

Путём преобразования БСВ можно получать модельные реализации многих других случайных объектов, включая любые непрерывные или дискретные случайные величины (как простые, так и многомерные), случайные события, случайные процессы, графы, схемы и т. д. Поэтому БСВ z называют базовой случайной величиной.

2.2. Метод середины квадрата

Метод середины квадрата предложен для получения псевдослучайных чисел по общему правилу (1.2) Д. фон Нейманом в 1946 г. Вот один из вариантов этого метода:

1)возьмём произвольное 4-значное число;

2)возведём полученное 4-значное число в квадрат и, если необходимо, добавим к результату слева нули до восьмизначного числа;

3)возьмём четыре цифры из середины восьмизначного числа в качестве очередного псевдослучайного 4-значного числа;

4)если нужны еще псевдослучайные числа, то вернёмся к 2);

5)конец алгоритма.

Например, если в качестве начального 4-значного числа взять 1994, то из него получается следующая последовательность псевдослучайных чисел: 9760, 2576, 6357, 4114, 9249, 5440, 5936, 2360, 5696, 4444, 7491, 1150, 3225, 4006, 0480, 2304, 3084, 5110, 1121, 2566, ...

6

Сам по себе метод середины квадрата не получил широкого распространения, так как выдает «больше чем нужно малых значений» [9]. Но использованный в нём принцип применяется во многих, если не во всех, более поздних датчиках БСВ. Этот принцип состоит в вырезании и/или перемешивании нескольких цифр в числовом результате какой-либо простой арифметической операции.

2.3. Мультипликативный конгруэнтный метод

Так называемый мультипликативный конгруэнтный датчик БСВ однозначно задаётся двумя параметрами: модулем m и множителем k. Обычно эти параметры представляют собой достаточно большие целые числа.

При заданных m, k псевдослучайные числа zi вычисляются мультипликативным конгруэнтным датчиком по рекуррентной формуле

где m – модуль; k – множитель; A0 – начальное значение; mod – операция вычисления остатка от деления произведения(k · Ai-1) на m. Заметим, что вычисление остатка от деления эквивалентно выбору младшей цифры частного в системе счисления с основанием m.

Датчик (1.3) дает периодическую псевдослучайную последовательность z1, z2, …, с длиной периода T ≤ m – 1. Чтобы длина периода T была максимальной, модуль m берут близким к максимальному представимому в компьютере целому числу. Для упрощения операций деления и вычисления остатков в двоичных ЭВМ часто берут m = 2n. Рекомендуется также брать достаточно большой множитель k, причем взаимно простой с m.

В[22] можно найти более подробные рекомендации по выбору параметров датчика. Заметим, однако, что не существует рекомендаций, гарантирующих высокое качество датчиков до того, как будет проведено их специальное тестирование.

Взаключение параграфа приведём таблицу параметров датчиков, рекомендуемых в публикациях [2, 9, 10] и в ряде языков программирования (табл. 1.1).

7

2.4. Тестирование равномерности БСВ

Обозначим равномерное распределение вероятностей на интервале (0, 1) через R[0,1]. Тогда утверждение, что БСВ z имеет распределение R[0,1], можно кратко записать в виде z ~ R[0,1].

С помощью статистических тестов проверяют два свойства датчика БСВ, делающих его точной моделью идеальной математической БСВ: во-первых, проверяют равномерность распределения чисел, выдаваемых датчиком на интервале (0, 1), и, во-вторых, их статистическую независимость. При этом последовательность псевдослучайных чисел zi на выходе датчика рассматривают как статистическую выборку.

Проверка равномерности распределения БСВ сводится к построению эмпирических вероятностных характеристик (моментов и распределений) случайной величины (с. в.) z по выборке z1, z2, z3, … , zn и их сравнению с теоретическими характеристиками распределения R[0,1]. В силу закона больших чисел с ростом длины выборки n эмпирические характеристики должны приближаться к теоретическим. При этом, поскольку компьютер позволяет легко получать выборки весьма большой длины, такое сближение эмпирических и теоретических характеристик можно наблюдать непосредственно, без использования специальных статистических тестов.

В настоящее время, как правило, любые языки программирования и пакеты моделирования содержат встроенные датчики БСВ и необходимость в самостоятельной разработке или тестировании датчиков возникает редко. Так, в Ms Excel имеется функция СЛЧИС( ), возвращающая значение БСВ.

Пример 1 . Создайте файл «СлВеличины.xls». Назовите первый лист СлВ. Введите в ячейку A1 формулу =СЛЧИС( ). Скопируйте её в диапазон A1:A100. Вы видите в этом диапазоне выборку из n = 100 значений БСВ. При нажатии на клавишу F9 случайные значения в столбце A меняются.

Найдите суммы k-х степеней этих случайных чисел (для k = 1, 2, 3, 4) и поделите эти суммы на 100.

Примечание: сумму кубов (и подобно им – других степеней) чисел диапазона A1:A100 можно вычислить в любой ячейке листа по формуле =СУММ(A1:A100^3), которую после её набора следует вводить нажатием Ctrl+Shift+Enter. Полученные значения представляют собой эмпирические начальные моменты k-го порядка. Сравните их с теоретическими значениями моментов. Посмотрите, насколько изменяются эмпирические моменты в разных опытах, осуществляемых нажатием клавиши F9. Чтобы удобнее было сравнивать эмпирические и теоретические значения, ограничьте точность их отображения двумя знаками после запятой.

Проведите такой же расчёт при длине выборки, увеличенной на два порядка, т. е. при n = 10 000. Средние отклонения эмпирических моментов от теоретических уменьшатся при этом приблизительно на порядок. Таким образом, с ростом n наблюдается явная сходимость эмпирических моментов псевдослучайной последовательности, выдаваемой в Excel датчиком БСВ, к теоретическим моментам равномерного распределения R[0,1].

8

2.5. Тестирование независимости БСВ

Простейшую проверку статистической независимости БСВ можно осуществить, оценивая линейную корреляцию между числами zi и zi+s, отстоящими друг от друга в псевдослучайной последовательности на фиксированный шаг s ≥ 1. Для вывода формулы, с помощью которой можно по выборке рассчитать оценку коэффициента корреляции такой пары чисел, рассмотрим теоретическое определение коэффициента корреляции двух произвольных с. в. x и y. Коэффициент корреляции определяется для них формулой

9

Условимся рассматривать в выборке всякую пару чисел (zi, zi+s) как реа-

(1.5) следующим образом. Заменяя в (1.5) справа м. о. M(xy) соответствующим эмпирическим м. о. (средним арифметическим выборочных значений), а слева –

Коэффициент корреляции двух с. в. характеризует степень линейной зави-

симости между ними. Поэтому с ростом длины выборки n оценка ˆ должна

R

приближаться к нулю (т. е. должно быть R(x,y) = 0, линейная зависимость должна отсутствовать). В противном случае датчик БСВ не отвечает требованию независимости БСВ. В то же время, если R(x,y) = 0, то это еще не гарантирует независимости случайных чисел. Но все же один из тестов – тест на линейную зависимость – можно считать успешно пройденным.

Следует обратить внимание, что сходимость оценки коэффициента корреляции, как и сходимость оценок м. о. и других эмпирических моментов, относится к классу сходимостей по вероятности. Последовательность значений

(по абсолютной величине) от точного предельного значения R(x,y) убывает пропорционально n .

Проверить независимость БСВ в Ms Excel можно также с помощью имеющегося в нём пакета анализа данных.

Пример 3 . Откройте файл «СлВеличины.xls», созданный при выполнении примеров 1 и 2. Перейдите на новый лист и назовите его Выборка. Введите в ячейку A1 формулу =СЛЧИС(). Скопируйте её на диапазон A1:B10000. Нажмите несколько раз ключ F9, чтобы убедиться в правильном пересчёте полученных столбцов случайных чисел.

Коэффициент корреляции между двумя числами в строках диапазона можно вычислить с помощью меню Сервис/Анализ данных/корреляция, выдающего диалоговое окно «Корреляция» (если опция Анализ данных отсутствует,

10