Evaluating variance efficiently

Let $f(x,y)$ be a scalar function and let $X$ and $Y$ be independent random variables with known distribution functions. I would like to evaluate the variance $$\sigma^2 =\mathrm{var}_X\left[\mathrm{E}_Y f(X,Y)\right],$$ where $\mathrm{E}_Y$ denotes the expectation with respect to $Y$, and $\mathrm{var}_X$ denotes the variance with respect to $X$. I am not able to perform the integrals analytically but am able to draw samples of $X$ and $Y$. How can I evaluate $\sigma^2$ efficiently? I have tried a few approaches (see below) but none of them are satisfactory.

Slow method that works

I can evaluate the variance by Monte Carlo integration: Let $\{X_1,\ldots X_N\}$ and $\{Y_1,\ldots,Y_N\}$ be samples of the random variables. I compute the sample mean with respect to $Y$ for each sample of $X$ to get samples $\mu_i=N^{-1}\sum_{j=1}^N f(X_i,Y_j)$. The desired quantity is then the variance of the set $\{\mu_1,\ldots,\mu_N\}$. Unfortunately, the computational complexity is $\mathcal{O}\left(N^2\right)$.

Faster method with problems

The expression for the variance can be recast as \begin{align} \sigma^2&=\mathrm{var}_X\left[\mathrm{E}_Y f(X,Y)\right]\\ &=\mathrm{E}_X\left[\mathrm{E}_Y f(X,Y)\right]\left[\mathrm{E}_{Y'} f(X,Y')\right]\\ &=\mathrm{cov}_{XYY'}\left[f(X,Y),f(X,Y')\right]. \end{align} This suggests I can draw samples for $X$, $Y$, and $Y'$, evaluate the function and compute the covariance which is less computationally intensive. However, for any finite sample, there is a small (but non-negligible) probability that the covariance will be negative.

• (1) What does $\phi$ have to do with the rest of the question? Is it related to $f$? (2) The notation seems deceptive, because as you have defined it, $\sigma^2$ depends on $X$. This is all confusing and suspicious. Are you sure that what you have written down correctly describes your situation and your objectives? – whuber Feb 26 '16 at 15:11
• Sorry, $\phi$ should indeed be $f$. The variance $\sigma^2$ should not depend on $X$. I have attempted to clarify. – Till Hoffmann Feb 26 '16 at 15:48