1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.