Метод обратного преобразования

Материал из Википедии — свободной энциклопедии

Ме́тод обра́тного преобразова́ния — способ генерации случайных величин с заданной функцией распределения, путём модификации работы генератора равномерно распределённых чисел.

Содержание

1 Описание алгоритма
- 1.1 Строго возрастающая функция распределения
- 1.2 Неубывающая функция распределения
2 Замечания
3 Математическое обоснование
4 См. также

[править] Описание алгоритма

Пусть $F (x)$ является функцией произвольного распределения. Покажем как, имея генератор выборки из стандартного непрерывного равномерного распределения, получить выборку из распределения, задаваемого функцией распределения $F (x)$ .

[править] Строго возрастающая функция распределения

Если функция $F:\mathbb{R}\to [0,1]$ строго возрастает на всей области определения, то она биективна, а следовательно имеет обратную функцию $F^{-1}:[0,1]\to \mathbb{R}$ .

Пусть $U_1,\ldots ,U_n \sim U[0,1]$ - выборка из стандартного непрерывного равномерного распределения.
Тогда $X_1,\ldots, X_n$ , где $X_i = F^{-1}(U_i),\; i=1,\ldots, n$ , - выборка из интересующего нас распределения.

Пример. Пусть требуется сгенерировать выборку из экспоненциального распределения с параметром $λ > 0$ . Функция этого распределения $F (x) = 1 - e - λ x$ строго возрастает, и её обратная функция имеет вид $F^{-1}(x) = -\frac{1}{\lambda} \,\ln ( 1 - x )$ . Таким образом, если $U_1,\ldots, U_n$ - выборка из стандартного непрерывного равномерного распределения, то $X_1, \ldots, X_n$ , где

$X_i = -\frac{1}{\lambda}\ln (1-U_i),\; i=1,\ldots,n$

- искомая выборка из экспоненциального распределения.

[править] Неубывающая функция распределения

Если функция $F:\mathbb{R} \to [0,1]$ лишь не убывает, то её обратная функция может не существовать. В таком случае необходимо модифицировать приведённый выше алгоритм.

Пусть $U_1,\ldots ,U_n \sim U[0,1]$ - выборка из стандартного непрерывного равномерного распределения.
Тогда $X_1,\ldots, X_n$ , где $X_i = \inf\{x \mid F(x) = U_i\},\; i=1,\ldots, n$ , - выборка из интересующего нас распределения.

[править] Замечания

Если $F (x)$ строго возрастает, то $F^{-1}(u) = \inf\{x \mid F(x) = u\}$ . Таким образом, модифицированный алгоритм для произвольной функции распределения включает в себя отдельно разобранный случай строго возрастающей функции распределения.
Несмотря на кажущуюся универсальность, данный алгоритм имеет серьёзные практические ограничения. Даже если функция распределения строго возрастает, вычислить её обратную не всегда просто, особенно если она не задана в виде элементарной функции, как, например, в случае нормального распределения. В случае функции распределения общего вида чаще всего необходимо численно находить точную нижнюю грань, что может быть очень трудоёмко.