Точная выборка из неправильных смесей

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

$$p(x) = \sum_{i=1}^\infty a_i f_i(x)$$

где и f_i - это распределения, из которых можно легко брать выборки, тогда я могу легко сгенерировать выборки из p :$a_i \geqslant 0, \sum_i a_i= 1$$f_i$$p$

1. Выборка метки $i$ с вероятностью $a_i$
2. Выборка $X \sim f_i$

Можно ли обобщить эту процедуру, если $a_i$ иногда отрицательны? Я подозреваю, что видел, как это где-то сделано - возможно, в книге, возможно, для рассылки Колмогорова - поэтому я был бы очень рад принять ссылку в качестве ответа.

Если конкретный пример с игрушкой полезен, скажем, я хотел бы взять пример из

$$p(x,y) \propto \exp(-x-y-\alpha\sqrt{xy})\qquad x,y > 0$$ я буду принять $\alpha \in (0, 2)$ по техническим причинам, которые не должны иметь большого значения, в общей схеме вещей.

В принципе, я мог бы затем расширить это как следующую сумму:

$$p(x,y) \propto \sum_{n=0}^\infty \frac{(-1)^n \alpha^n \left( \frac{n}{2} \right)! \left( \frac{n}{2} \right)!}{n!} \left( \frac{x^{n/2} e^{-x}}{\left( \frac{n}{2} \right)!}\right) \left( \frac{y^{n/2} e^{-y}}{\left( \frac{n}{2} \right)!}\right) .$$

$(x,y)$ -термины внутри сумма может быть затем независимо от пробы , как гамма случайных величин случайным образом . Моя проблема, очевидно, в том, что коэффициенты «иногда» отрицательны.

Редактировать 1 : Я уточняю, что я стремлюсь генерировать точные выборки из $p$ , а не вычислять ожидания по $p$ . Для тех, кто заинтересован, некоторые процедуры для этого упоминаются в комментариях.

Редактировать 2 : Я нашел ссылку, которая включает в себя особый подход к этой проблеме, в «Неоднородном генерации случайных вариаций» Девроя . Алгоритм взят из «Заметки о выборке из комбинаций распределений» Бингами и де Маттеиса . Метод заключается в том, чтобы эффективно связать плотность сверху с помощью положительных членов суммы, а затем использовать выборку отклонения, основанную на этом конверте. Это соответствует методу, описанному в ответе @ Xi'an.

Я ломал голову над этим вопросом, но так и не нашел удовлетворительного решения.

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

$$f(x)=\frac{g(x)-\omega h(x)}{1-\omega}\qquad \omega>0$$ $g$$g(x)\ge \omega h(x)$$g$$\omega h(x)/g(x)$$f$$g$ $$g(x)=\sum_{\alpha_i>0} \alpha_i f_i(x) \big/ \sum_{\alpha_i>0} \alpha_i$$ $\omega h$ $$h(x)=\sum_{\alpha_i<0} \alpha_i f_i(x) \big/ \sum_{\alpha_i<0}\alpha_i$$ Это действительно найдено в Библии моделирования Devroye, Неоднородная генерация случайных вариаций, раздел II.7.4, но следует из простого рассуждения о принятии-отклонении.

Первый вычислительный недостаток этого подхода состоит в том, что, несмотря на первое моделирование из выбранного компонента , суммы для и должны быть вычислены для этапа отклонения. Если суммы бесконечны без закрытой версии, это делает невозможным реализацию метода accept-reject .$f_i$$g$$h$

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

$$\sum_{\alpha_i>0}\alpha_i = 1 - \sum_{\alpha_i<0}\alpha_i$$ $$1-\varrho^\text{accept}=\sum_{\alpha_i<0}|\alpha_i| \Big/ \sum_i |\alpha_i|$$ $\alpha_i$

В случае смешанного представления, если можно записать как сначала можно выбрать компонент, а затем метод, примененный к компоненту. Но это может быть деликатным для реализации, так как идентификация пар которые соответствуют из возможно бесконечной суммы, не всегда выполнима.$f$

$$f(x)=\sum_{i=1}^\infty \alpha_i \frac{g_i(x)-\omega_i h(x_i)}{1-\omega_i}\qquad \omega_i>0$$ $(g_i,h_i)$$g_i(x)-\omega_i h(x_i)>0$

Я думаю, что более эффективное разрешение могло бы прийти из самого представления серии. Devroye, Неоднородная генерация случайных вариаций, раздел IV.5, содержит широкий спектр последовательных методов. Как, например, следующий алгоритм для представления альтернативного ряда цели когда ' s сходятся к нулю с и является плотностью:

$$f(x)=\kappa h(x)\{1-a_1(x)+a_2(x)-\cdots\}$$ $a_i(x)$$n$$h$

Эта проблема была недавно рассмотрена в контексте искажения смещенных оценок для MCMC, как, например, в подходе Глинна-Ри . И российский оценщик рулетки (в связи с проблемой фабрики Бернулли). И беспристрастная методология MCMC . Но нет выхода из проблемы знака ... Что делает его использование сложным при оценке плотностей, как в псевдо-маргинальных методах.

После дальнейших размышлений я пришел к выводу, что не существует общего метода для создания фактической симуляции из этой серии [вместо смеси, которая оказывается неправильной], без наложения дополнительной> структуры на элементы серии, как в вышеуказанный алгоритм из Библии Деврой . Действительно, поскольку большинство (?) Плотностей допускают последовательное разложение вышеописанного вида, это в противном случае подразумевало бы существование своего рода универсальной имитационной машины ...

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

Во-первых, как упомянул Сиань, вы можете сгруппировать положительные веса, с одной стороны, и отрицательные веса, с другой стороны, чтобы в итоге у задачи было только два распределения и :$g$$h$

$$p=\lambda g - \mu h$$

с . Обратите внимание, что у вас есть .$\lambda-\mu=1$$\lambda\geq 1$

Моя идея заключается в следующем. Вы хотите образец наблюдений от . Делать:$N$$p$

• выборка значений из и сохранение их в списке$\lambda N$$g$
• для каждого из значений, выбранных из , удалите их ближайшего (оставшегося) соседа из списка.$\mu N$$h$

В конце вы получаете баллов. Это не обязательно должен быть точно ближайший сосед, а просто точка, которая «достаточно близка». Первый шаг подобен созданию материи. Второй шаг похож на создание антивещества, и пусть оно сталкивается и отменяется с материей. Этот метод не является точным, но я считаю, что в некоторых условиях он асимптотически точен для больших (чтобы сделать его почти точным для малых сначала нужно использовать большое а затем взять небольшую случайную часть окончательного списка) , Я даю очень неофициальный аргумент, который является скорее объяснением, чем доказательством.$(\lambda-\mu)N=N$$N$$n$$N$

Рассмотрим в пространстве наблюдений и небольшой объем вокруг с объемом Лебега . После выборки из число элементов в списке, которые также находятся в , приблизительно равно . После второго шага из него будет удалено приблизительно , и вы приблизительно получите желаемое число . Для этого нужно предположить, что количество точек в объеме достаточно велико.$x$$v$$x$$\epsilon$$g$$v$$\lambda Ng(x)\epsilon$$\mu Nh(x)\epsilon$$Np(x)\epsilon$

Очень маловероятно, что этот метод противостоит большой размерности или некоторым патологиям и но может работать в малой размерности и достаточно гладких, «достаточно однородных» распределениях.$g$$h$

Примечание о точном методе:

Сначала я подумал об этом для дискретных распределений, и ясно, что в этом случае этот метод не является точным, поскольку он может генерировать выборки с вероятностью 0. У меня есть сильное убеждение, что точный метод невозможен с конечным временем обработки, и что это невозможность может быть доказана, по крайней мере, для дискретных распределений. Правило игры состоит в том, что вам разрешено использовать только точные сэмплеры «оракула» для и но вы не знаете и как функции от . Для простоты ограничимся распределениями Бернулли. Отсутствие точного метода связано с теорией фабрики Бернулли : если бы вы могли создать -койну из$g$$h$$g$$h$$x$$(\lambda p - \mu q)$$p$-coin и -coin, тогда вы можете создать монету из монеты, которая, как известно, невозможна для .$q$$\lambda p$$p$$\lambda>1$