costo de muestreo de versus

Me encontré con el siguiente problema de simulación: dado un conjunto de números reales conocidos, una distribución en está definida por donde denota la parte positiva de . Si bien puedo pensar en una muestra de Metropolis-Hastings dirigida a esta distribución, me pregunto si existe una muestra directa eficiente, aprovechando la gran cantidad de probabilidades cero para disminuir el orden del algoritmo de a .$\{\omega_1,\ldots,\omega_d\}$$\{-1,1\}^d$

$$\mathbb{P}(X=(x_1,\ldots,x_d))\propto (x_1\omega_1+\ldots+x_d\omega_d)_+$$ $(z)_+$$z$$O(2^d)$$O(d)$

Aquí hay una muestra recursiva bastante obvia que es en el mejor de los casos (en términos de pesos ), pero exponencial en el peor de los casos.$O(d)$$\omega_i$

Supongamos que ya hemos seleccionado y deseamos elegir . Necesitamos calcular y elige con probabilidad El denominador será distinto de cero para cualquier elección válida de muestras .$x_1, \dots, x_{i-1}$$x_{i}$

$$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)_+$$ $x_i = 1$ $$\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)}.$$ $x_1, \dots, x_{i-1}$

---

Ahora, por supuesto, la pregunta es cómo calcular .$w(x_1, \dots, x_i)$

Si tenemos que , entonces para cualquier con entradas , y entonces convierte en: $C := \sum_{j=1}^{i} \omega_j x_j \ge \sum_{j=i+1}^{d} \lvert \omega_j \rvert$$\omega \cdot x \ge 0$$x$$x_{1:i}$$w$

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

En el caso opuesto, , tenemos que y entonces .$C \le - \sum_{j=i+1}^{d} \lvert \omega_j \rvert$$\omega \cdot x \le 0$$w(x_1, \dots, x_i) = 0$

De lo contrario, debemos recurrir, usando .$w(x_1, \dots, x_i) = w(x_1, \dots, x_i, 1) + w(x_1, \dots, x_i, -1)$

Suponga que la memoria no es un problema y que podemos almacenar en caché todos los sub-cálculos en , en un árbol, hasta el punto en que llegamos a uno de los casos "agradables", después de lo cual cualquier Las llamadas toman tiempo constante. (Tendremos que calcular todo este árbol de todos modos para seleccionar .) Luego, una vez que se construya este árbol de cálculos , la muestra tomará solo tiempo. La pregunta es cuánto tiempo se tarda en construir el árbol, o de manera equivalente qué tan grande es.$w(1)$$w(-1)$$x_1$$w$$O(d)$

---

Por supuesto, veremos los casos "agradables" más rápido si los están ordenados, .$\omega_i$$\omega_1 \ge \omega_2 \ge \dots \ge \omega_d$

En el mejor de los casos, . Entonces llegamos a un caso "agradable" inmediatamente, ya sea para o , por lo que construcción del árbol toma constante de tiempo, y todo el muestreador toma tiempo.$\lvert \omega_1 \rvert > \sum_{j=2}^d \lvert \omega_j \rvert$$w(1)$$w(-1)$$w$$O(d)$

En el peor de los casos (ordenados), . Entonces la pregunta es: ¿qué tan grande es el árbol total?$\omega_1 = \omega_2 = \dots = \omega_d$

Bueno, los primeros caminos para terminar son, por supuesto y de longitud . Por lo tanto, el árbol está completo hasta esa profundidad, y por lo tanto contiene al menos nodos. (Tiene más; probablemente puedas encontrarlo con un argumento como los que se usan en los problemas de ruina del jugador, pero no pude encontrarlo en dos minutos de Google y no me importa particularmente:  es malo suficiente....)$(1, 1, \dots, 1)$$(-1, -1, \dots, -1)$$\lceil d/2 \rceil$$O(2^{d/2})$$2^{d/2}$

Si su configuración tiene solo unos pocos muy grandes , este es probablemente un enfoque razonablemente práctico. Si los son todos de magnitud similar, probablemente todavía sea exponencial y demasiado caro para grande .$\omega_i$$\omega_i$$d$