задается формулой

у 2JtfT

Это знаменитая «колоколообразная кривая теории вероятностей». График этой функции приведен на рис. 6.3.2. Кривая симметрична

Рис. 6.3.2. Функция плотности нормального распределения.

относительно р*, имеет резко заострентш вид при малых значениях

и более «сглаженный» при больших. Нормальное распределение с параметрами р и обозначается как Л/(р, а). Распределение (0,1) называется стандартным нормальным.

Простые, но несколько трудоемкие выкладки показывают, что если X - нормальная случайная переменная с параметрами р и а", то ElX]=\i и var lX]=o

Неожиданно большое количество случайных переменных обладает нормальным распределением или близким к нормальному. Многие из этих случайных переменных испытывают суммарное влияние со стороны других случайных переменных. Теоретически это следует из ряда важных теорем, известных под совместным названием центральных предельных теорем. Грубо говоря, эти теоремы гласят, что случайная переменная, являющаяся суммой многих других случайных переменных, приближается к нормально распределенной.

Можно показать, что X и являются несмещенными и состоятельными оценками с минимальной дисперсией для [х и любой нормально распределенной случайной переменной. В тех случаях, когда предполагается, что случайная переменная отражает суммарное влияние других случайных переменных, нормальное распределение с параметрами X и S" (основанное на статистических наблюдениях) может оказаться хорошей оценкой для всего неизвестного распределения случайной переменной.

В разд. 2.4 и 4.2 мы уже видели, что важно иметь машинно-генери-руемые «случайные числа» для облегчения тестирования и анализа алгоритмов. Следовательно, важно иметь эффективные алгоритмы для генерации случайных чисел.

Машинные генераторы случайных чисел чаще всего генерируют значения выборки случайной переменной, распределенной равномер-

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

Одним из очевидных механических средств достижения этого является колесо с единичной окружностью. Это колесо вращается против конца очень острой иглы, и координата точки окружности против конца иглы служит очередным случайным числом. Почему такое устройство не вводят в состав аппаратуры компьютера? Такие колеса не применяются потому, что случайные числа можно генерировать быстро, дешево, точно и почти так же надежно с помощью некоторых простых алгоритмов.

В действительности эти алгоритмы не генерируют случайных чисел с той неопределенностью, которая присуща вращающемуся колесу. На самом деле они используют простые арифметические операции для детерминированной выработки последовательности чисел, которые только кажутся случайными. Эти числа можно предсказать до того, как они будут сгенерированы. Этот факт, по-видимому, раздражает некоторых, но на самом деле для этого нет оснований. Последовательности псевдослучайных чисел, генерируемых этими алгоритмами, оказываются случайными и удовлетворяют ряду сложных статистических тестов, что в результате «узаконивает» их как удовлетворительные.

Один из ранних генераторов случайных чисел, принадлежащий Джону фон Нейману (1946), известен как метод середины квадрата.

Algorithm MS (середина квадрата) для генерации /С-разрядных псевдослучайных чисел. Должно быть задано /С-разрядное начальное число Хо. Для удобства предполагаем, что К, четно и нужна последовательность Х(\), Х{2).....Х(М) из М случайных чисел (см.

упр. 6.3.20).

Шаг 0. [Инициализация] Set X Хо,

Шаг. 1, [Основной цикл] For У ч- 1 to М do шаг 2 od; and STOP. Шаг 2, [Генерация нового случайного числа X (J)] Set Y

Х2; Х(/) (средние К разрядов числа Y); and X ч-Х(У). (Число У будет иметь 2К разрядов, а следую-

I щее случайное число X (/) получается, если удалить

по К/2 разрядов с каждого конца У. Ясно, что десятичная точка помещается перед первым разрядом числа X (У) до поступления его на выход случайного генератора.)

Для /С=4 и Хо=2134 первые 10 псевдослучайных чисел, выработанные алгоритмом MS, будут:

Х2 = 04 5539 56 Xi= 0.5539

Несмотря на видимую случайность чисел, генерируемых алгоритмом MS, ему свойственны недостатки, которые привели к тому, что им избегают пользоваться в серьезных приложениях. Убедитесь, что если в последовательности когда-нибудь появится 0.0000, то все следующие за ним числа будут также 0.0000. Генерация случайных чисел в алгоритме MS может вырождаться различными путями. Для /С=4 и Хо=1357 последовательность оказывается следующей:

Xi=0.84l4 Х2=0.7953 Хз=0.2502 Х,=0.2600 Х,=0.7600 Хв=0.7600 Х,=0.7600

Х„=0.7600 для п>5.

Это вряд ли похоже на случайные числа. Даже при более тщательном выборе К и Хо последовательности, генерируемые этим методом, склонны к быстрому «зацикливанию» и работают неудовлетворительно при проверке по сложным статистическим критериям.

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

Algorithm LCM (линейный конгруэнтный метод) для генерации последовательности Х(1), Х(2), . . ., Х{М) из М псевдослучайных чисел. Должны быть заданы следующие входные значения:

X (0) = начальное «необработанное» случайное число X (0) 1; целое

В = множитель 61; целое

К = шаг КО; целое

MOD - модуль MOD>X(0), В, К; целое