Существует ли какой-либо одномерный дистрибутив, из которого мы не можем сэмплировать?

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

Не могли бы вы привести какой-нибудь пример одномерного распределения, из которого невозможно произвести случайную генерацию? Я полагаю, что такой пример, где это невозможно, не существует (?), Поэтому предположим, что под «невозможным» мы подразумеваем также случаи, которые являются очень дорогостоящими в вычислительном отношении, например, которые требуют моделирования методом грубой силы, такого как отрисовка огромного количества образцов, чтобы принять только их мало.

Если такого примера не существует, можем ли мы доказать, что мы можем генерировать случайные ничьи из любого допустимого распределения? Мне просто любопытно, существует ли контрпример для этого.

Если вам известна накопительная функция распределения , то вы можете инвертировать ее, аналитически или численно, и использовать метод выборки обратного преобразования для генерации случайных выборок https://en.wikipedia.org/wiki/Inverse_transform_sampling .$F(x)$

Определите . Это будет обрабатывать любое распределение, непрерывное, дискретное или любую комбинацию. Это всегда можно решить численно и, возможно, аналитически. Пусть U - выборка из случайной величины, распределенной как Uniform [0,1], т. Е. Из равномерного [0,1] генератора случайных чисел. Тогда F - 1 ( U ) , определенный, как указано выше, является случайной выборкой из случайной величины, имеющей распределение F ( x ) . $F^{-1}(y) = inf(x:F(x) \ge y)$$F^{-1}(U)$$F(x)$

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

Если F (x) не известен, то это другая история.

Когда распределение определяется только его производящей функцию момента или его характеристической функцией Φ ( t ) = E [ exp { i t X } ] , редко можно найти пути генерации из этих распределений.$\phi(t)=\mathbb{E}[\exp\{tX\}]$$\Phi(t)=\mathbb{E}[\exp\{itX\}]$

Соответствующий пример сделан для стабильных распределений$\alpha$ , которые не имеют известной формы для плотности или cdf, не генерируют моментную функцию, но имеют характеристическую функцию замкнутой формы.

В байесовской статистике апостериорные распределения, связанные с трудноизвлекаемыми правдоподобиями или просто наборами данных, которые слишком велики, чтобы поместиться в один компьютер, можно рассматривать как невозможные (точно) для моделирования.

$F$$u \sim (0,1)$$F^{-1}(u)$$F$$F^{-1}$

${\bf \theta} = (\theta_1,...,\theta_d)$$\theta_j$

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

$(q_i)_{i=1}^\infty$$P(X=q_i)=0$$i$$\sum_{i=1}^\infty P(X=q_i)=0$$P(X\in \mathbb{Q})=1$

$\mu$$\pi(\mu) = 1$

Не могли бы вы привести какой-нибудь пример одномерного распределения, из которого невозможно произвести случайную генерацию?

$c$$c$

Если вас интересует только выборка случайных величин, значения которых могут быть разумно аппроксимированы 64-битными числами с плавающей точкой, или у вас есть некоторый аналогичный допуск для конечной ошибки в значении, и вы все равно не представляли свои выборки на машинах Тьюринга , учти это:

$X \sim \text{Ber}(p)$$p = 1 - c$$0$$1$

$0$$(-∞, c)$$1$$[c, ∞)$$0$$(-∞, 0)$$c$$[0, 1)$$1$$[1, ∞)$$c$$x$$y$-ось. Я не уверен, что делает выборку наиболее трудной, поэтому выберите тот, который вам больше не нравится ;-)

скажем, что под «невозможным» мы подразумеваем также случаи, которые являются очень дорогостоящими в вычислительном отношении, например, которые требуют моделирования методом грубой силы, например, отбор огромного количества образцов, чтобы принять только некоторые из них.

В этом случае очевидный ответ кажется очевидным:

• $n$$n$
• Образец прообраз криптографической хэш-функции (т.е. генерировать биткойны и разбивать мерзавцев и мерзавцев).
• Пример набора оптимальных стратегий Го (с китайскими правилами суперко, которые делают все игры конечными - насколько я понимаю).

Немного более формально: я привожу вам большой пример NP-полной проблемы (или EXP-Complete и т. Д.) И прошу вас единообразно отобрать для меня набор решений.

$\bot$$\mathbb{R}$$-1$$\bot$

Вы можете легко проверить, удовлетворяет ли какое-либо заданное правдивое назначение моему экземпляру SAT, и, проверив их все, что вы знаете, делает ли кто-нибудь, поэтому я полностью определил CDF, предоставив вам булеву формулу (или схему), но пока не попробовал соответствующий дистрибутив. по сути, вы должны стать чем-то по меньшей мере таким же мощным, как оракул, разрешающий SAT.

Поэтому я дал вам неисчислимое число, которое должно выбрасывать песок в ваши шестерни, и я дал вам CDF, который медленно вычисляется. Может быть, следующий очевидный вопрос, который нужно задать, выглядит примерно так: существует ли CDF, представленный в некоторой эффективной форме (например, может быть оценен за полиномиальное время), такой, что трудно сгенерировать выборки с таким распределением? Я не знаю ответа на этот вопрос. Я не знаю ответа на этот вопрос.