Calculate a Conditional Expectation via Samples Consider a binary random variable $Y \sim p(Y)$, a random variable $X \sim p(X)$ (can be discrete or continuous) and a conditional distribution $p(X|Y)$. Suppose that I generate $N$ samples from $p(Y)$, denoted by $y_1, \dots, y_N$ and then generate a sample from $p(X|Y)$ for each $y_n$: $x_1, \dots, x_N$. Is the following empirical expectation correct for any function $g(.)$?
$\frac{1}{N} \sum_{n=1}^N y_n g(x_n) \approx E_{x \sim p(X)}[p(Y = 1|X) g(X)]$
I wrote the following:
$E_{x \sim p(X)}[p(Y = 1|X) g(X)] = \sum_X p(Y = 1|X) g(X) p(X)$
$ = \sum_X p(Y=1) p(X|Y=1) g(X)$
But I'm not sure how the last line can be approximated by  $\frac{1}{N} \sum_{n=1}^N y_n g(x_n)$. I ran some simulations and it seems that they are equivalent.
 A: Yes they are equivalent, given some very general assumptions on $g(\cdot)$, and you can prove this by the law of large numbers.
Lets consider the simpler case of a single discrete variable $X$ first. We want to show that the expectated value of $X$ can be approximated by a mean of samples from $X$. Generalising this to your problem is simple.
Let $\mathbb{E}(X) = \sum_{i=1}^N p_i X_i =  \mu$ and $V(X) = \mathbb{E}((X-\mu)^2) = \sigma^2$. These are just definitions of the mean and variance. Now let 
$S_n = \sum_{n=1}^{N} X_n$
for some finite $N$. What we want to show is that $\frac{S_n}{N} \to \mu$ as $N \to \infty$.
To show this consider $V(S_n)$. Since the variance of the sum of independent random variables is the same as the sum of their variance and the process generating $X_i$ is constant and samples generated are indepdendent, the variance of the sum is just $n$ times to variance of one variable i.e.
$V(S_n) = n\sigma^2$
equivalently
$V(\frac{S_n}{n}) = \sigma^2$
note also that from the defintion of expectation follows that
$\mathbb{E}(\frac{S_n}{n}) = \mu$
Chebyshevs inequality states that:
$P(|X-\mu| \geq \epsilon) \leq \frac{V(X)}{\epsilon^2}$
Therefore
$P(|\frac{S_n}{n} - \mu|\geq\epsilon) \leq \frac{\sigma^2}{N\epsilon^2} $
since $\epsilon$ (i.e. your target accuracy) is fixed this will tend to 0 as $N\to \infty$.
This is easily applied to your problem by considering the variable $Z$ with distribution $P(Z) = P(Y,X,g(X)) = P(Y|X) \cdot P(g(X)|X) \cdot P(X)$. You can sample $Z$ as you have a process for sampling $X$ and $Y$ and calculating $g(X)$. The key assumption I mentioned above, on $g(\cdot)$ is that it is such that $P(Z)$ has finite variance.
