# 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.

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.