Calculate a Conditional Expectation via Samples

Question

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.

Answer 1

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.