ФЭНДОМ


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

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

Пусть $ 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 $, — выборка из интересующего нас распределения.

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

Пусть требуется сгенерировать выборку из экспоненциального распределения с параметром $ \lambda > 0 $. Функция этого распределения $ F(x) = 1 - e^{-\lambda 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\} $. Таким образом, модифицированный алгоритм для произвольной функции распределения включает в себя отдельно разобранный случай строго возрастающей функции распределения.
  • Несмотря на кажущуюся универсальность, данный алгоритм имеет серьёзные практические ограничения. Даже если функция распределения строго возрастает, вычислить её обратную не всегда просто, особенно если она не задана в виде элементарной функции, как, например, в случае нормального распределения. В случае функции распределения общего вида чаще всего необходимо численно находить точную нижнюю грань, что может быть очень трудоёмко.

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

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

$ \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 $ имеет функцию распределения $ F(x) $.