Генерируем случайные числа, распределенные по заданному закону

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

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

Сначала разберемся с функциями распределения.

## Функция плотности вероятности (f), функция распределения (F) и квантильная функция (F??).

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

NB. Распределение случайной величины описывает вероятность появления тех или иных значений в массиве данных.

#### Функция плотности вероятности (pdf — probability density function).

Любое непрерывное распределение полностью характеризуется функцией плотности вероятности (ФПВ, обозначается f). Именно график ФПВ обычно рисуют для того, чтобы показать форму распределения.

Для непрерывной случайной величины значение ФПВ в точке x равно высоте столбика под графиком. С большой натяжкой можно утверждать, что f(x) — это вероятности встретить значение x в нашей выборке:

f(x) = p(x).

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

Корректно говорить, что ФПВ используют для вычисления вероятности встретить значение x в некотором интервале [a; b]. Данная вероятность равна определенному интегралу от f(x):

P(a ? x ? b) = ?(a, b) f(x) dx.

Но не суть важно. Потому что есть еще одна функция, полностью описывающая любое распределение — это (кумулятивная) функция распределения.

#### (Кумулятивная) Функция распределения (cdf — cumulative distribution function).

Функция распределения F(y) равна вероятности того, что любое выбранное случайным образом значение x будет не больше значения y:

F(y) = P(x ? y).

Значение ФР равно площади участка, ограниченного графиком функции f(x) на интервале от -? до y.

F(y) = ?(-?, y) f(x) dx.

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

#### Связь ФПВ и ФР

F — это первообразная функции f, либо f есть F'. Отсюда вероятность попадания x в интервал [a; b] выражается следующей формулой:

f([a; b]) = P(x ? b) - P(x ? a) = F(b) - F(a).

Функция f(x) явным образом задана для всех известных распределений. А вот аналитическое выражение F(x) для некоторых распределений отсутствует, так как не все интегралы выражаются элементарными функциями. Это не всегда хорошо.

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

## Метод инверсии.

Метод использует обратную функцию F??(p) от функции распределения F(y):

F??(p) = y.

Это, так называемая, квантильная функция.

Область определения F?? — интервал [0; 1], то есть все возможные значения вероятностей. Область значений — вся числовая ось, то есть все возможные значения переменной x. Следовательно, если мы возьмем равномерно распределенные значения вероятности p(i), например изменяющиеся с шагом 0,05, то обратная ФР отобразит их в значения переменной x, распределенные по закону, описанному функцией плотности. То есть F?? берет вероятность p и выдает значение x, которое соответствует этой вероятности в нужном распределении. По сути квантильная функция F?? преобразует равномерно распределенные вероятности в числа, которые растягиваются или сжимаются в зависимости от формы исходного распределения.

Отсюда происходит алгоритм.

#### Алгоритм метода инверсии

- Генерируем случайное равномерно распределенное значение p из [0; 1].

- Подставляем его в формулу F??.

- Получаем x, которое подчиняется искомому распределению: x = F??(p).

- Повторяем нужное число раз.

Вуаля!

#### Проблема

Работа алгоритма выглядит прекрасной, пока мы не зададимся вопросом: как найти обратную функцию распределения F??, если сама функция не выражается элементарным образом?

В этом случае мы можем каким-либо способом аппроксимировать F и F??. Но есть другой, более простой и интуитивно понятный метод — метод выборки с отклонением.

## Метод выборки с отклонением.

Это разновидность метода Монте-Карло, применяемая для приближенного вычисления определенных интегралов или генерации случайных величин с заданной плотностью распределения f(x). Он позволяет моделировать выборки из сложных распределений, используя более простую вспомогательную функцию g(x).

Функция g(x) ограничивает сверху функцию f(x). Она удовлетворяет условию:

f(x) ? c ? g(x),

где c > 0 — это константа подобранная так, чтобы график c ? g(x) всегда лежал выше или касался графика f(x).

Идея метода заключается в следующем. Метод генерирует две случайных величины: x — которое является потенциальным значением распределения, и p из отрезка [0; 1] — которое описывает вероятность выбора x в качестве правильного значения. Метод принимает или не принимает x в зависимости от выполнения условия:

p ? f(x) / g(x).

В данном случае p из [0; 1] отображается в точку на отрезке [0; g(x)]. Если эта точка лежит не выше графика функции f(x), то мы принимаем x в качестве нужной нам случайной величины.

В качестве функции g необходимо использовать функцию, интеграл которой на используемом интервале равен единице. Часто, для этого можно взять отрезок g(x) = const.

#### Алгоритм метода выборки с отклонением.

- Генерируем случайное x из интервала, для которого строим распределение.

- Генерируем случайное p из [0; 1].

- Проверяем условие p ? f(x) / g(x).

- Если условие выполняется, сохраняем x.

Вуаля!

## Выводы.

Мы разобрали два фундаментальных метода для генерации случайных чисел по заданному непрерывному распределению:

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

- Метод выборки с отклонением более универсален, особенно когда F?? недоступна. Использует вспомогательную функцию g(x) для отсева неподходящих значений, что делает его применимым к сложным распределениям. Минус метода — потенциально низкая эффективность (много отклонений), если g(x) плохо подобрана, но в простых случаях (g(x)=const) метод отлично работает.

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

Источник: vk.com

Комментарии: