Amostragem exata de misturas impróprias

Suponha que eu queira amostrar a partir de uma distribuição contínua . Se eu tiver uma expressão de na forma$p(x)$$p$

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

onde e f_i são distribuições que podem ser facilmente amostradas, então eu posso facilmente gerar amostras de p por:$a_i \geqslant 0, \sum_i a_i= 1$$f_i$$p$

1. Amostrando um rótulo $i$ com probabilidade $a_i$
2. Amostragem $X \sim f_i$

É possível generalizar esse procedimento se o $a_i$ for ocasionalmente negativo? Suspeito ter visto isso feito em algum lugar - possivelmente em um livro, possivelmente na distribuição de Kolmogorov -, então ficaria perfeitamente feliz em aceitar uma referência como resposta.

Se um exemplo brinquedo concreto é útil, digamos que eu gostaria de amostra de

$$p(x,y) \propto \exp(-x-y-\alpha\sqrt{xy})\qquad x,y > 0$$ eu vou em seguida, tome $\alpha \in (0, 2)$ por razões técnicas que não devem importar muito, no grande esquema das coisas.

Em princípio, eu poderia expandir isso como a seguinte soma:

$$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) .$$

Os termos $(x,y)$ dentro da soma podem ser amostrados independentemente de como variáveis ​​aleatórias gama. Meu problema é evidentemente que os coeficientes são "ocasionalmente" negativos.

Edit 1 : Esclareço que estou procurando gerar amostras exatas de $p$ , em vez de calcular as expectativas em $p$ . Para os interessados, alguns procedimentos para fazer isso são mencionados nos comentários.

Edit 2 : Encontrei a referência que inclui uma abordagem específica para esse problema, na 'Geração aleatória não uniforme de variáveis ​​de Devroye' . O algoritmo é de 'Uma nota sobre amostragem de combinações de distribuições', de Bignami e de Matteis . O método é efetivamente vincular a densidade de cima pelos termos positivos da soma e, em seguida, usar a amostragem de rejeição com base nesse envelope. Isso corresponde ao método descrito na resposta de @ Xi'an.

Fiquei intrigado com essa questão, mas nunca vi uma solução satisfatória.

Uma propriedade que é possível de usar é que, se uma densidade grava que é um densidade tal que , simulando a partir de rejeitando essas simulações com probabilidade forneça simulações de . No caso atual, é a versão normalizada dos componentes de peso positivo e é o restante

$$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$$ Na verdade, isso é encontrado na Bíblia de simulação do Devroye, geração aleatória não uniforme de variáveis , Seção II.7.4, mas segue de um simples raciocínio de aceitação / rejeição.

Um primeiro inconveniente computacional desta abordagem é que, apesar simulando primeiro componente escolhido a partir de um , as somas em ambos e deve ser calculado para o passo de rejeição. Se as somas são infinitas, sem versão de formulário fechado, isso torna impossível a implementação do método de aceitação e rejeição .$f_i$$g$$h$

Uma segunda dificuldade é que, uma vez que ambas as somas de pesos são da mesma ordem a taxa de rejeiçãonão tem limite superior. Na verdade, se a série associada aos 's não estiver absolutamente convergindo, a probabilidade de aceitação será zero! E o método não pode ser implementado nesta situação.

$$\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$

No caso de uma representação de mistura, se pode ser escrito como o componente pode ser escolhido primeiro e depois o método aplicado ao componente. Mas isso pode ser delicado de implementar, identificando pares que se encaixam em da soma possivelmente infinita não sendo necessariamente viável.$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$

Eu acho que uma resolução mais eficiente poderia vir da própria representação em série. A geração aleatória não uniforme de Devroye, Seção IV.5, contém uma grande variedade de métodos em série. Por exemplo, o algoritmo a seguir para uma representação alternativa em série do destino quando o ' s convergem para zero com e é uma densidade:

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

O problema foi considerado recentemente no contexto de estimadores com viés de debiasing para o MCMC, como por exemplo na abordagem de Glynn-Rhee . E o estimador de roleta russa (com uma conexão com o problema da fábrica de Bernoulli). E a metodologia imparcial do MCMC . Mas não há como escapar da questão do sinal ... O que torna seu uso desafiador ao estimar densidades como nos métodos pseudo-marginais.

Pensando melhor, minha conclusão é que não existe um método genérico para produzir uma simulação real a partir desta série [em vez de uma mistura que acaba se revelando inadequada], sem impor mais> estruturas aos elementos da série, como o o algoritmo acima da Bíblia de Devroye . De fato, como a maioria das densidades (?) Permite uma expansão em série do tipo acima, isso implicaria a existência de um tipo de máquina de simulação universal ...

Eu tenho o rascunho de uma ideia que poderia funcionar. Não é exato , mas espero que seja assintoticamente exato. Para transformá-lo em um método realmente rigoroso, onde a aproximação é controlada, ou algo sobre isso pode ser comprovado, provavelmente há muito trabalho necessário.

Em primeiro lugar, tal como mencionado por Xian é possível agrupar os pesos positivos, por um lado e os pesos negativos sobre o outro lado, de modo que, finalmente, que o problema tem apenas duas distribuições e :$g$$h$

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

com . Observe que você possui .$\lambda-\mu=1$$\lambda\geq 1$

Minha ideia é a seguinte. Você quer exemplos de observações da . Faz:$N$$p$

• exemplo valores de armazene-os em uma lista$\lambda N$$g$
• para cada um dos valores de amostrados de , remova o vizinho mais próximo (restante) da lista.$\mu N$$h$

No final, você recebe pontos. Não precisa ser exatamente o vizinho mais próximo, mas apenas um ponto "próximo o suficiente". O primeiro passo é como gerar matéria. O segundo passo é como gerar antimatéria e deixá-la colidir e cancelar com a matéria. Esse método não é exato, mas acredito que, sob algumas condições, é assintoticamente exato para grande (para torná-lo quase exato para pequeno, você precisa usar um grande primeiro e depois tirar uma pequena parte aleatória da lista final) . Estou dando um argumento muito informal que é mais uma explicação do que uma prova.$(\lambda-\mu)N=N$$N$$n$$N$

Considere no espaço de observação e um pequeno volume torno de com o volume de Lebesgue . Após a amostragem de , o número de elementos na lista que também está em é aproximadamente . Após a segunda etapa, aproximadamente serão removidos e você terá aproximadamente o número desejado . Para isso, você precisa assumir que o número de pontos no volume é suficientemente grande.$x$$v$$x$$\epsilon$$g$$v$$\lambda Ng(x)\epsilon$$\mu Nh(x)\epsilon$$Np(x)\epsilon$

É muito improvável que esse método resista a grandes dimensões ou a algumas patologias de e mas pode funcionar em pequena dimensão e em distribuições "suficientemente uniformes" suficientemente suaves.$g$$h$

Nota sobre um método exato:

Primeiro pensei nisso para distribuições discretas e, claramente, nesse caso, o método não é exato, pois pode gerar amostras com probabilidade 0. Tenho a forte intuição de que um método exato não é possível com tempo de processamento finito e que esse método impossibilidade poderia ser comprovada, pelo menos para distribuições discretas. A regra do jogo é que você só estão autorizados a utilizar exatas samplers "oracle" para e , mas não sei e em função de . Para simplificar, restrinja as distribuições de Bernoulli. A inexistência de um método exato está relacionada à teoria da Fábrica de Bernoulli : se você pudesse criar uma moeda partir de uma$g$$h$$g$$h$$x$$(\lambda p - \mu q)$$p$-coin e -coin, você pode criar uma moeda a partir de uma moeda que é conhecida por ser impossível para .$q$$\lambda p$$p$$\lambda>1$