стоимость выборки

9

Я столкнулся со следующей проблемой моделирования: для заданного набора известных действительных чисел распределение по { - 1 , 1 } d определяется как P ( X = ( x 1 , , x d) ) ) ( x 1 ω 1 + + x d ω d ) + где ( z ){ω1,,ωd}{1,1}d

P(X=(x1,,xd))(x1ω1++xdωd)+
обозначает положительную часть z . Хотя я могу думать о сэмплере Metropolis-Hastings, нацеленном на это распределение, мне интересно, существует ли эффективный прямой сэмплер, использующий преимущество большого числа нулевых вероятностей для уменьшения порядка алгоритма с O ( 2 d ) до O ( d ) .(z)+zO(2d)O(d)
Сиань
источник

Ответы:

4

Вот довольно очевидный рекурсивный пробоотборник , что это в лучшем случае (с точкой зрения веса ш I ), но экспоненциальный в худшем случае.O(d)ωi

x1,,xi1xi

w(x1,,xi1,xi)=xi+1{1,1}xd{1,1}(j=1dωjxj)+
xi=1
w(x1,,xi1,1)w(x1,,xi1,1)+w(x1,,xi1,1).
x1,,xi1

w(x1,,xi)

C:=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

Дугал
источник
Cij=i+1d|ωj|
Cij=i+1d|ωj|
1
Нет, не дополнение: когда оно очень большое, вы знаете, что усечение не применяется, когда оно очень маленькое, оно всегда применяется, и между ними вы должны выполнить повторение, чтобы выяснить, когда оно применяется или не применяется.
Дугал