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

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

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

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

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

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

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

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

ПримерПравить

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

$X_i=-<!--\; -\; -->\frac{1}{\mathrm{\lambda <!--\; \lambda \; -->}}\ln <!--\; \; -->(1-<!--\; -\; -->U_i),i=1,\dots <!--\; \dots \; -->,n$$X_{i}=-{\frac {1}{\lambda }}\ln(1-U_{i}),\;i=1,\ldots ,n$ 

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

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

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

• Пусть $U_1,\dots <!--\; \dots \; -->,U_n\sim <!--\; \sim \; -->U[0,1]$$U_{1},\ldots ,U_{n}\sim U[0,1]$  — выборка из стандартного непрерывного равномерного распределения.
• Тогда $X_1,\dots <!--\; \dots \; -->,X_n$$X_{1},\ldots ,X_{n}$ , где $X_i=inf\{x\mid <!--\; \mid \; -->F(x)=U_i\}=min\{x\mid <!--\; \mid \; -->F(x)=U_i\},i=1,\dots <!--\; \dots \; -->,n$$X_{i}=\inf\{x\mid F(x)=U_{i}\}=\min\{x\mid F(x)=U_{i}\},\;i=1,\ldots ,n$ , — выборка из интересующего нас распределения. Равенство точной нижней грани минимуму выполняется ввиду непрерывности функции распределения справа, что означает, что точная нижняя грань достигается.

ЗамечанияПравить

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

Математическое обоснованиеПравить

 

Математическое обоснование.

Пусть $U\sim <!--\; \sim \; -->U[0,1]$$U\sim U[0,1]$ , то есть $F_U(u)=u,u\in <!--\; \in \; -->[0,1]$$F_{U}(u)=u,\;u\in [0,1]$ . Рассмотрим функцию распределения случайной величины $X=inf\{x\mid <!--\; \mid \; -->F(x)=U\}$$X=\inf\{x\mid F(x)=U\}$ .

$\mathbb{P}(X\le <!--\; \le \; -->x)=\mathbb{P}(inf\{x^{\prime }\mid <!--\; \mid \; -->F(x^{\prime })=U\}\le <!--\; \le \; -->x)=\mathbb{P}(U\le <!--\; \le \; -->F(x))=F_U(F(x))=F(x)$$\mathbb {P} (X\leq x)=\mathbb {P} (\inf\{x'\mid F(x')=U\}\leq x)=\mathbb {P} (U\leq F(x))=F_{U}(F(x))=F(x)$ .

То есть $X$$X$  имеет функцию распределения $F(x)$$F(x)$ .

См. такжеПравить

• Преобразование Бокса — Мюллера
• Алгоритм Зиккурат

ЛитератураПравить

Вадзинский Р.Н. Справочник по вероятностным распределениям. - СПб.: Наука, 2001, 295 с.