custo de amostragem de

9

Me deparei com o seguinte problema de simulação: dado um conjunto de números reais conhecidos, uma distribuição em é definida por onde indica a parte positiva de . Embora eu possa pensar em um amostrador Metropolis-Hastings visando essa distribuição, pergunto-me se existe um amostrador direto eficiente, aproveitando o grande número de probabilidades zero para diminuir a ordem do algoritmo de para .{ - 1 , 1 } d P ( X ={ω1,,ωd}{1,1}d ( z ) + z O ( 2 d ) O ( d )

P(X=(x1,,xd))(x1ω1++xdωd)+
(z)+zO(2d)O(d)
Xi'an
fonte

Respostas:

4

Aqui está um amostrador recursivo bastante óbvio que é no melhor caso (em termos de pesos ω i ), mas exponencial no pior caso.O(d)ωi

Suponha que já selecionamos e desejamos escolher x i . Precisamos calcular w ( x 1 , ... , x i - 1 , x i ) = Σ x i + 1{ - 1 , 1 }Σ x d{ - 1 , 1 } ( d Σx1,,xi1xi e escolhaxi=1com probabilidadew(x1,,x i - 1 ,1)

w(x1,,xi1,xi)=xi+1{1,1}xd{1,1}(j=1dωjxj)+
xi=1 O denominador será diferente de zero para qualquer escolha válida de amostrasx1,,xi-1.
w(x1,,xi1,1)w(x1,,xi1,1)+w(x1,,xi1,1).
x1,,xi1

Agora, é claro, a questão é como calcular .w(x1,,xi)

Se temos que , Em seguida, co x 0 para qualquer x com os principais entradas x 1 : i , e assim por w torna-se: Σ x i + 1Σ x d co xC:=j=1iωjxjj=i+1d|ωj|ωx0xx1:iw

xi+1xdωx=ω(xi+1xdx)=j=1iωj(xi+1xdxj)2dixj+j=i+1dωj(xi+1xdxj)0=2diC.

Cj=i+1d|ωj|ωx0w(x1,,xi)=0

w(x1,,xi)=w(x1,,xi,1)+w(x1,,xi,1)

w(1)w(1)x1wO(d)


ωiω1ω2ωd

|ω1|>j=2d|ωj|w(1)w(1)wO(d)

ω1=ω2==ωd

(1,1,,1)(1,1,,1)d/2O(2d/2)2d/2

ωiωid

Dougal
fonte
Cij=i+1d|ωj|
Cij=i+1d|ωj|
11
Não, não é o complemento: quando é muito grande, você sabe que o truncamento não é aplicado, quando é muito pequeno, sempre é aplicado, e você deve recuar para descobrir quando é ou não é aplicado.
Dougal