koszt próbkowania w wysokości

Natknąłem się na następujący problem z symulacją: biorąc pod uwagę zestaw $\{\omega_1,\ldots,\omega_d\}$ znanych liczb rzeczywistych, rozkład na $\{-1,1\}^d$ jest zdefiniowany przez

$$\mathbb{P}(X=(x_1,\ldots,x_d))\propto (x_1\omega_1+\ldots+x_d\omega_d)_+$$ gdzie $(z)_+$ oznacza pozytywną część $z$. Chociaż mogę wymyślić próbnik Metropolis-Hastings ukierunkowany na ten rozkład, zastanawiam się, czy istnieje skuteczny próbnik bezpośredni, wykorzystujący dużą liczbę zerowych prawdopodobieństw w celu zmniejszenia kolejności algorytmu od$O(2^d)$ do $O(d)$.

Oto dość oczywisty rekurencyjny sampler $O(d)$ w najlepszym przypadku (pod względem ciężaru $\omega_i$), ale w najgorszym przypadku ma charakter wykładniczy.

Załóżmy, że już wybraliśmy $x_1, \dots, x_{i-1}$i chcesz wybrać $x_{i}$. Musimy obliczyć

$$w(x_1, \dots, x_{i-1}, x_i) = \sum_{x_{i+1} \in \{-1, 1\}} \cdots \sum_{x_{d} \in \{-1, 1\}} \left( \sum_{j=1}^d \omega_j x_j \right)_+$$ i wybierz $x_i = 1$ z prawdopodobieństwem $$\frac{w(x_1, \dots, x_{i-1}, 1)}{w(x_1, \dots, x_{i-1}, 1) + w(x_1, \dots, x_{i-1}, -1)}.$$ Mianownik będzie niezerowy dla każdego ważnego wyboru próbek $x_1, \dots, x_{i-1}$.

---

Teraz oczywiście chodzi o to, jak obliczyć $w(x_1, \dots, x_i)$.

Jeśli mamy to $C := \sum_{j=1}^{i} \omega_j x_j \ge \sum_{j=i+1}^{d} \lvert \omega_j \rvert$, następnie $\omega \cdot x \ge 0$ dla każdego $x$ z wiodącymi wpisami $x_{1:i}$, a więc $w$ staje się:

$$\begin{align} \sum_{x_{i+1}} \cdots \sum_{x_d} \omega \cdot x &= \omega \cdot \left( \sum_{x_{i+1}} \cdots \sum_{x_d} x \right) \\&= \sum_{j=1}^i \omega_j \underbrace{\left( \sum_{x_{i+1}} \cdots \sum_{x_d} x_j \right)}_{2^{d-i} x_j} + \sum_{j=i+1}^d \omega_j \underbrace{\left( \sum_{x_{i+1}} \cdots \sum_{x_d} x_j \right)}_{0} \\&= 2^{d-i} C .\end{align}$$

W przeciwnym wypadku $C \le - \sum_{j=i+1}^{d} \lvert \omega_j \rvert$mamy to $\omega \cdot x \le 0$ a więc $w(x_1, \dots, x_i) = 0$.

W przeciwnym razie musimy powtórzyć, używając $w(x_1, \dots, x_i) = w(x_1, \dots, x_i, 1) + w(x_1, \dots, x_i, -1)$.

Załóżmy, że pamięć nie stanowi problemu i że możemy buforować wszystkie podliczenia $w(1)$, $w(-1)$w drzewie - do tego stopnia, że ​​trafiliśmy w jeden z „ładnych” przypadków, po których wszelkie połączenia wymagają stałego czasu. (Będziemy musieli obliczyć to całe drzewo, aby wybrać$x_1$.) Potem, kiedy to drzewo $w$ obliczenia są zbudowane, sampler zajmie tylko $O(d)$czas. Pytanie brzmi, ile czasu zajmuje zbudowanie drzewa, lub równoważnie, jak duże jest ono.

---

Oczywiście trafimy w „ładne” przypadki, jeśli $\omega_i$ są posortowane, $\omega_1 \ge \omega_2 \ge \dots \ge \omega_d$.

W najlepszym przypadku, $\lvert \omega_1 \rvert > \sum_{j=2}^d \lvert \omega_j \rvert$. Następnie natychmiast trafiliśmy w „fajną” skrzynkę$w(1)$ lub $w(-1)$, więc $w$ budowa drzewa zajmuje cały czas, a cały sampler zajmuje $O(d)$ czas.

W najgorszym (posortowanym) przypadku $\omega_1 = \omega_2 = \dots = \omega_d$. Zatem pytanie brzmi: jak duże jest całe drzewo?

Cóż, pierwsze ścieżki do zakończenia są oczywiście $(1, 1, \dots, 1)$ i $(-1, -1, \dots, -1)$ długości $\lceil d/2 \rceil$. Drzewo jest zatem kompletne do tej głębokości, a zatem zawiera co najmniej$O(2^{d/2})$węzły (Ma więcej; prawdopodobnie można go znaleźć za pomocą argumentu takiego jak te używane w problemach z ruiną hazardzisty, ale nie mogłem go znaleźć w ciągu dwóch minut Googlinga i nie obchodzi mnie to szczególnie - $2^{d/2}$ jest wystarczająco zły ....)

Jeśli twoje ustawienie ma tylko kilka bardzo dużych $\omega_i$, jest to prawdopodobnie dość praktyczne podejście. Jeśli…$\omega_i$ są podobnej wielkości, prawdopodobnie nadal są wykładnicze i zbyt drogie dla dużych $d$.