Случайный выбор из ограниченного множества

 

В общем случае случайные целые числа X, которые лежат между 0 и k – 1, можно получить, умножив U на k и положив X = ë k × U û (ближайшее целое снизу).

В общем случае можно получить, если необходимо, различные веса для различных целых чисел. Предположим, что значение X = x ₁ должно быть получено с вероятностью p ₁, X = x ₂ — с вероятностью p ₂, … и X = x_k — с вероятностью p_k. Для этого генерируется равномерное число U и полагается

 

(Заметим, что .)

 

Общие методы для непрерывных распределений

 

В общем случае распределение действительных чисел может быть выражено в терминах «функции распределения» F (X), которая точно определяет вероятность того, что случайная величина X не превысит значения x:

 

                    F (X) = P_r (X £ x)                                           (4.11)

Эта функция всегда монотонно возрастает от 0 до 1, т.е. F (x ₁) £ F (x ₂), если x ₁ £ x ₂;

F (- ¥) = 0, F(+ ¥) = 1. Если F (X) непрерывна и строго возрастающая (так что

F (x ₁) < F (x ₂), когда x ₁ < x ₂), то она принимает все значения между 0 и 1 и существует обратная функция F ^-1 (y), такая, что для 0 < y < 1 Y = F (X), тогда и только тогда, когда

X = F ^-1 (y). В большинстве случаев, когда F (X) непрерывна и строго возрастающая, можно вычислить случайную величину X с распределением F (X), полагая X = F ^-1 (U), где U — равномерно распределенная случайная величина. Заметим, что если х₁ — случайная величина, имеющая функцию распределения F ₁ (Х), и если х₂ — независимая от х₁ случайная величина с функцией распределения F ₂ (Х), то max (х₁, х₂) имеет распределение F ₁ (Х) F ₂ (Х), min (х₁, х₂) имеет распределение F ₁ (Х) + F ₂ (Х) – F ₁ (Х) × F ₂ (Х).

 

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

 

Нормальное распределение

 

Возможно, наиболее значительным неравномерным распределением является нормальное распределение с нулевым средним значением и среднеквадратичным отклонением, равным единице:

 

                                                         (4.12)

 

Рассмотрим алгоритм вычисления двух независимых нормально распределенных случайных величин: X ₁ и X ₂.

 

Алгоритм Р. (Метод полярных координат для нормальных случайных величин).

Р1. [Получение равномерно распределенных случайных величин.] Сгенерировать две независимые случайные величины U ₁ и U ₂, равномерно распределенные между 0 и 1. Присвоить V ₁ 2 U ₁ – 1, V ₂ 2 U ₂ – 1. (Здесь V ₁ и V ₂ равномерно распределены между –1 и +1.)

Р2. [Вычисление S. ] Присвоить S V ₁ ² + V ₂ ².

Р3. [Проверить S ³ 1?] Если S ³ 1 возврат к п. Р1.

Р4. [Вычисление X ₁, X ₂. ] Присвоить X ₁ и X ₂ следующие значения:

 

, .

 

Это требуемые нормально распределенные случайные величины.

 

Показательное распределение

 

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

 

                                   .                             (4.13)

 

Метод логарифма. Очевидно, если , то . В [6] предлагается 1 – y рассматривать как равномерное распределение 1 – U, или просто U, что позволяет записать , где X — случайная величина, имеющая экспоненциальное распределение со средним, равным m.