и по основной теореме интегрального исчисления

Если Y обладает равномерным распределением на [О, 1), то его интегральная функция распределения равна

О при ttO;

G(G) = P(F<a) =

\ldy = a при 0<с<1; о

1 при 1 < с.

Пусть случайная переменная X имеет интегральную функцию распределения F, и пусть случайная переменная равномерно распределена на [О, 1). Предположим, что обратная функция ведет себя достаточно хорошо. Мы хотим показать, что случайная переменная, определяемая формулой X=F~(F), имеет интегральную функцию распределения /. Тогда, если {i/i, у., . . ., Уп) - последовательность равномерно распределенных чисел, то последовательность {Xi=F~{yi), Х2=Р-{У2), . ., Хп=р-Чуп)} будет иметь распределение F.

Таким образом, мы хотим показать, что

Р(Х<х)=/(х), если X=F-Y), а Y обладает равномерньш распределением. Это доказывается так:

P(X<x) = P(/-(F)<x) = P(F<P(x))= J \dy=F{x).

Мы уже отмечали, что F{x) всегда лежит между О и 1; здесь мы также использовали интегральную функцию распределения для F.

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

Экспоненциальное распределение (с параметром Ц имеет функцию плотности

/(x)=?ie-, 0<л:<оо;

=0 в остальных случаях.

Интегральная функция распределения для экспоненциально распределенной случайной переменной задается выражением

P(x) = 0 при x<0;

\ke-dx={\-e-) при л;>0„ о

Это распределение является фундаментальным в теории очередей. Экспоненциально распределенные случайные переменные хорошо подходят для моделирования интервалов между прибытиями. Если Y распределена равномерно, то

Y=F(X)=l-e-K Обращая F (т. е. решая относительно X), получим

Х = -1п(1-F).

Таким образом, если {уи у2.....Уп) - равномерно распределенные

случайные числа, то

xi = -у 1п(1-i). Х2 = - -1п{1-у), x„= -у 1п(1 -

будут экспоненциально распределенными случайными числами.

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

Algorithm PNRN (полярный жтод генерации случайных чисел с нормальным распределением) для генерации двух независимых случайных чисел с распределением Л(0, 1) из двух независимых, равномерно распределенных случайных чисел. Распределение iV(0, 1) преобразуется в Л(р,, а) с использованием теоремы 6.3.4. Шаг 1. [Генерация двух равномерно распределенных случайных чисел] Генерируются два независимых случайных числа Ut и с распределением 17(0, 1); set Fi2i7i-1; and V. -<-2f/g-1. {Vi и Vi имеют распределение 17(-1, -fl).) Шаг 2. [Вычисление и проверка S] Set S-Vl+Vl; if S>1 then

go to шаг 1 fi.

Шаг 3. [Вычисление Nj и N] Set Ni <- ViV (-21nS)/S; and ч--V2V{-2h-iS)/S; and STOP. {Nt и распределены нормально.)

Алгоритм PNRN имеет важное вычислительное преимущество перед алгоритмом NRN, а именно: он обычно генерирует по одному числу с нормальным распределением на каждое число с равномерным распределением. Компенсируется ли этим дополнительное время, затрачиваемое на вычисление натуральных логарифмов и квадратных корней?

Доказательство правильности алгоритма PNRN существенно опирается на интегральное исчисление и аналитическую геометрию; оно оставлено в качестве упражнения.

Упражнения 6.3

6.3.1. Разработайте алгоритм для случайной генерации двух карточек <«бинго» (игра наподобие лото) типа показанных на следующем примере:

1-1S 16-30 31-45 46-60 61-75

Б И Н Г О

4 17 32 49 73

11 25 42 51 67

12 19 ПУСТО 46 62 8 29 37 54 64

5 * 30 44 50 74

Проследите, чтобы ни одно число не появлялось дважды в одном столбце.

6.3.2. Алгоритм SS часто используется для извлечения несмещенной выборки М файлов данных из N, где N - большое число. Почему для такого применения важна однопроходность?

6.3.3. Проверьте теорему 6.3,2 для случая k=l.

*L6.3.4. Алгоритм SS (проверка). Проведите обширную проверку алгоритма SS. Попытайтесь получить экспериментальное подтверждение теоремы 6,3.2.

***6.3.5. Алгоритм SS (анализ). Покажите, что среднее значение k в момент остановки алгоритма SS равно

M(N+l)

Йсред---ЩГГ--

6.3.6. Обсудите относительные достоинства и недостатки алгоритмов SS и SELECT.

6.3.7. Равномерно равпределенные случайные переменные. Если Y - равномерно распределенная случайная переменная на интервале [а, р], то какова ее функция плотности? Вычислите Е [К] и var [К].

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

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

6.3.10. Если X - случайная переменная с распределением Nhi, а*), покажите явно, что Е Ш=р,. а var U]=g«.

6.3.11. Вычислите выборочную дисперсию для эксперимента по упорядочению прямой вставкой (в упр. 2.4.25).

*L6.3.12. Алгоритм MS (реализация). Запрограммируйте алгоритм MS, используя любые удобные значения К и Хо. Сгенерируйте 10 случайных чисел и вычислите оцен-