Генерация СВ с заданной функцией плотности/распределения

[MestnyBomzh]

Предположим, мы можем генерировать равномерное распределение. Тогда утверждается, что есть универсальный метод инверсии, благодаря которому мы можем сгенерировать СВ с любой функцией плотности/распределения.

Я не очень понимаю, почему это правда. У нас есть функция распределения СВ, например, $X$, которую мы хотим сгенерировать. Мы берем $F_X(x)$ и ищем обратную функцию $F^{-1}_X(x)$ - предположим, что мы нашли её. Дальше генерируем равномерную СВ $U$, после чего утверждается, что $F^{-1}_X(U)$ - это искомая функция распределения. Я не очень понимаю, почему это всё правда. ЧТобы удостовериться в этом надо проверить, что

$$P(F^{-1}_X(U) \leqslant x) = F_X(x)$$

Я нашел в интернете следующее краткое объяснение почему последняя фор-ла верна:

$$P(F^{-1}_X(U) \leqslant x) = P(U \leqslant F_X(x)) = F_X(x)$$

Первый переход я понимаю. А вот второй нет. Как я себе понимаю второй переход: $P(U \leqslant F_X(x)) = F_U (F_X(x))$
Не вижу почему это равно $F_X(x)$, могли бы помочь?

[arseniiv]

$F_U$ — тождественная функция на $[0; 1]$, а за пределы этого промежутка подставляемые в неё значения $F_X(x)$ не выходят.

[MestnyBomzh]

arseniiv
Почему она тождественная? Мы знаем, что $U ~ R[a;b]$, если я возьму $a=0.5, b=1$ , то функция $F_U(x)$ уже не будет тождественной на $[0;1]$

[mihaild]

Потому что сгенерированная нами $U$ равномерна не на каком-то неизвестном отрезке, а на $[0; 1]$.

[MestnyBomzh]

Ок, увидел. Но ведь бывают случаи, когда мы не можем найти обратную функцию. Как в таком случае действовать?

[mihaild]

Давайте начнем с примера. У нас есть случайная величина $\xi$, которая с вероятностью $\frac{1}{2}$ принимает значение $42$, а с вероятностью $\frac{1}{2}$ - $666$. Можете ли вы придумать такую монотонную функцию $f$, что $\xi = f(U)$?

[MestnyBomzh]

Немного непривычно рассматривать $U$ - непрерывную СВ и $\xi$ - дискретную. Если я правильно понял, то из равномерного $U$ описанную Вами дискретную СВ можно получить вот так:

$$\xi = \begin{cases} 42 &\text{,если $U <0.5$;}\\ 666 &\text{,если $U \geqslant 0.5$;} \end{cases}$$

Тут действительно с вер-ю 0.5 будет приниматься 42 и с вер-ю 0.5 будет приниматься 666. Ну и эта функция, очевидно, монотонна

[mihaild]

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

Если понятно, то дальше есть два варианта: либо попробовать придумать аналогичное преобразование, которое не будет требовать дискретности, либо для данной величины $\xi$ придумать последовательность дискретных $\xi_n$, сходящуюся к ней в каком-то смысла так, чтобы соответствующие преобразования $[0; 1] \to \mathbb{R}$ сходились (хотя бы почти всюду; тут как раз пригодится монотонность).
(мне первый способ представляется проще, но второй использует более стандартный подход)

[MestnyBomzh]

mihaild в сообщении #1244359 писал(а):

Понятно ли, как обобщить этот подход на произвольную дискретную величину?

Да, на произвольную дискретную понятно.

mihaild в сообщении #1244359 писал(а):

придумать аналогичное преобразование,

Это же и есть поиск обратной функции? Тут снова проблема, у каких-то функций обратная просто не существует в явном виде, тогда этот метод не годится

mihaild в сообщении #1244359 писал(а):

либо для данной величины $\xi$ придумать последовательность дискретных $\xi_n$,

То есть есть у меня нормальное распределение. Я беру и делаю его дискретным с шагом, например, 0.1. А после дискретное легко приближается, как мы уже знаем?

[mihaild]

MestnyBomzh в сообщении #1244367 писал(а):

Это же и есть поиск обратной функции?

Не совсем. Для дискретного случая же вы не обратную функцию выписали?
На самом деле в доказательстве, что применив обратную функцию к равномерной с.в. мы получаем исходное распределение, используется не то, что наша функция - обратная (т.е. $f(g(x)) = x$ для любого $x$), а некоторое более слабое свойство. Попробуйте посмотреть, какое (и функция с таким свойством будет уже существовать для любой функции распределения).

MestnyBomzh в сообщении #1244367 писал(а):

Я беру и делаю его дискретным с шагом, например, 0.1. А после дискретное легко приближается, как мы уже знаем?

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

[ewert]

MestnyBomzh в сообщении #1244367 писал(а):

Тут снова проблема, у каких-то функций обратная просто не существует в явном виде, тогда этот метод не годится

Тогда самый простой из стандартных способов -- это метод "приём-отклонение". Для случайной величины, принимающей значения из интервала $(0;1)$ с плотностью $f(x)$, причём $\max f=M$, генерируют пару стандартных равномерно распределённых случайных величин $x,\ y$ и проверяют, выполняется ли неравенство $M\cdot y<f(x)$. Как только выполняется -- принимают икс в качестве очередного значения, а игрек просто игнорируют.

Если же интервал значений икса другой (в т.ч. бесконечный), то его сводят к стандартному какой-либо явно обратимой заменой.

[arseniiv]

Есть ещё куча приёмов генерации, см. напр. Luc Devroye. Non-uniform random variate generation. Многие являются, конечно, развитием упомянутых.

[MestnyBomzh]

Окей, а если вернуться к истокам: как сгенерировать равномерное распределение?

[mihaild]

Зависит от того, в каком смысле "сгенерировать", и что есть изначально.
На практике множество вещественных чисел конечно, поэтому там нужно просто сгенерировать равномерное дискретное распределение.

[arseniiv]

(Как я понял вопрос автора)

MestnyBomzh в сообщении #1244413 писал(а):

Окей, а если вернуться к истокам: как сгенерировать равномерное распределение?

О, ну это тоже большая тема. Нельзя с наскоку отличить хороший генератор (псевдо)случайных* чисел от плохого — для этого разработаны целые пакеты статистических тестов; также важно бывает отличить надёжный для криптографических нужд от ненадёжного. Однако для не слишком точных применений бывает достаточно классики жанра линейного конгруэнтного генератора с правильно выбранными параметрами. Такой генератор несложен в реализации, хотя в мейнстримных языках программирования сейчас доступны реализации и лучших генераторов типа вихря Мерсенна, xorshift и всяких других. (Особенно криптостойких — тут малюсенькая ошибка в самописной реализации может дорого обойтись.)

На самом деле об этом тоже стоит порекомендовать книгу, но мне никто такую не рекомендовал, в отличие от предыдущей, потому нечего. Ну вот разве что главу/главы из «Искусства программирования» Кнута, если проберётесь.

* Поставил «псевдо» в скобки, потому что для затравки или как часть состояния генератор может использовать данные, получаемые от физического устройства или из программного окружения (например, на ПК это могут быть, среди прочего, должным образом обработанные движения мыши и интервалы между нажатиями клавиш), но это уже будет вообще третья история, ещё более сложная, потому что надо знать достаточно точно вероятностное распределение данных из таких источников.