Jak optymalnie rozłożyć losowania przy obliczaniu wielu oczekiwań

Załóżmy, że chcemy obliczyć pewne oczekiwania:

$$E_YE_{X|Y}[f(X,Y)]$$

Załóżmy, że chcemy to przybliżyć za pomocą symulacji Monte Carlo.

$$E_YE_{X|Y}[f(X,Y)] \approx \frac1{RS}\sum_{r=1}^R\sum_{s=1}^Sf(x^{r,s},y^r)$$

ALE załóżmy, że pobieranie próbek z obu rozkładów jest kosztowne, dlatego możemy sobie pozwolić tylko na narysowanie stałej liczby $K$.

Jak powinniśmy przydzielić $K$? Przykłady obejmują$K/2$ losuje do każdego rozkładu, lub skrajnie, jedno losowanie na zewnętrznym i $K-1$ wciąga wnętrze, odwrotnie itd ...

Moja intuicja mówi mi, że będzie to miało związek z wariancją / entropią rozkładów względem siebie. Załóżmy, że zewnętrzny to punkt masy, a następnie podział$K$ , który minimalizuje błąd MC byłby losowanie 1 z $Y$ i narysuj $K-1$ z $X|Y$.

Mam nadzieję, że było to jasne.

To bardzo interesujące pytanie, z niewielką dokumentacją w literaturze Monte Carlo, z wyjątkiem powiązania ze stratyfikacją i Rao-Blackwellisation . Jest to prawdopodobnie spowodowane faktem, że obliczenia oczekiwanej wariancji warunkowej i wariancji oczekiwanej warunku są rzadko wykonalne.

Po pierwsze, załóżmy, że biegniesz $R$ symulacje z $\pi_X$, $x_1,\ldots,x_R$ i dla każdego symulowanego $x_r$biegniesz $S$ symulacje z $\pi_{Y|X=x_r}$, $y_{1r},\ldots,y_{sr}$. Twoje szacunki Monte Carlo są wtedy

$$\delta(R,S)=\frac{1}{RS}\sum_{r=1}^R\sum_{s=1}^S f(x_r,y_{rs})$$ Wariancja tego oszacowania jest rozkładana w następujący sposób $$\begin{align*} \text{var} \{\delta(R,S)\} &= \frac{1}{R^2S^2} R\text{var} \left\{\sum_{s=1}^S f(x_r,y_{rs})\right\}\\ &= \frac{1}{RS^2} \text{var}_X\mathbb{E}_{Y|X}\left\{\sum_{s=1}^S f(x_r,y_{rs})\big|x_r\right\}+\frac{1}{RS^2}\mathbb{E}_{X}\text{var}_{Y|X} \left\{\sum_{s=1}^S f(x_r,y_{rs})\big|x_r\right\}\\ &=\frac{1}{RS^2} \text{var}_X\{ S \mathbb{E}_{Y|X}[f(x_r,Y)|x_r]\}+ \frac{1}{RS^2} \mathbb{E}_{X}[S\text{var}_{Y|X}\{f(x_r,Y)|x_r\}]\\ &=\frac{1}{R} \text{var}_X\{\mathbb{E}_{Y|X}[f(x_r,Y)|x_r]\}+ \frac{1}{RS} \mathbb{E}_{X}[\text{var}_{Y|X}\{f(x_r,Y)|x_r\}]\\ &\stackrel{K=RS}{=}\frac{1}{R}\text{var}_X\{\mathbb{E}_{Y|X}[f(x_r,Y)|x_r]\}+ \frac{1}{K} \mathbb{E}_{X}[\text{var}_{Y|X}\{f(x_r,Y)|x_r\}] \end{align*}$$ Dlatego jeśli chcemy zminimalizować tę wariancję, optymalnym wyborem jest $R=K$. Implikując to$S=1$. Z wyjątkiem sytuacji, gdy pierwszy warunek wariancji jest zerowy, w którym to przypadku nie ma to znaczenia. Jednak, jak omówiono w komentarzach, założenie$K=RS$ jest nierealne, ponieważ nie uwzględnia produkcji jednego $x_r$ [lub zakłada, że ​​jest to bezpłatne].

Przyjmijmy teraz różne koszty symulacji i ograniczenie budżetowe $R+aRS=b$, co oznacza, że $y_{rs}$koszt $a$ razy więcej do symulacji niż $x_r$„s. Tak więc powyższy rozkład wariancji

$$\frac{1}{R}\text{var}_X\{\mathbb{E}_{Y|X}[f(x_r,Y)|x_r]\}+ \frac{1}{R(b-R)/aR} \mathbb{E}_{X}[\text{var}_{Y|X}\{f(x_r,Y)|x_r\}]$$ które można zminimalizować w $R$ tak jak $$R^*=b\big/1+\{a\mathbb{E}_{X}[\text{var}_{Y|X}\{f(x_r,Y)|x_r\}/\text{var}_X\{\mathbb{E}_{Y|X}[f(x_r,Y)|x_r]\}\}^{1/2}$$ [najbliższa liczba całkowita pod ograniczeniami $R\ge 1$ i $S\ge 1$], z wyjątkiem sytuacji, gdy pierwsza wariancja jest równa zero, w którym to przypadku $R=1$. Kiedy$\mathbb{E}_{X}[\text{var}_{Y|X}\{f(x_r,Y)|x_r\}]=0$, minimalna wariancja odpowiada maksimum $R$, który prowadzi do $S=1$ w obecnym formalizmie.

Należy również zauważyć, że to rozwiązanie należy porównać z rozwiązaniem symetrycznym, gdy jest wbudowana całka wewnętrzna $X$ dany $Y$ a całka zewnętrzna jest przeciwna do marginesu w $Y$ (zakładając, że symulacje są również wykonalne w tej kolejności).

Ciekawym rozszerzeniem tego pytania byłoby rozważenie innej liczby symulacji $S(x_r)$ dla każdego symulowanego $x_r$, w zależności od wartości $\text{var}_{Y|X}\{f(x_r,Y)|x_r\}$.