Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

We know that the expectation operator is defined for a random variable $x$, as such:

$$ \mathbb{E} \left\{x\right\} = \int_{-\infty}^{\infty} x \: p_x(x) \; \mathrm{d}x $$

Where $p_x{x}$ is the PDF of the random variable $x$.

If there is an arbitrary(?) function $f$ acting on the random variable $x$, then the expected value of this function can also be written as:

$$ \mathbb{E}\left\{f(x) \right\} = \int_{-\infty}^{\infty} f(x) \: p_x(x) \: \mathrm{d}x $$

My questions are: On many algorithms that I study, (statistical in nature), one often finds themselves taking the expected value of some entity, that is a function of the random variable $x$. In the reverse case, one can also find themselves poking around and manipulating the probability distribution function of $x$, and then we can 'take it back' into an expression using the expectation operator.

Upon evaluating the expected value of $x$ however, ($\mathbb{E[x]})$, I often come across this estimation formula:

$$ \mathbb{E}\left\{x\right\} \approx \frac{1}{N}\sum_{n=1}^{N} x[n] $$

and similarly,

$$ \mathbb{E}\left\{f(x)\right\} \approx \frac{1}{N}\sum_{n=1}^{N} f(x[n]) $$ Where each $x[n]$ is an individual realization of the random variable $x$.

My question is, why is this formula true, and how did it come about? Every book I read seems to just include it as if it fell from the sky one day and no explanation is given as to why it is true.

Could someone please give an intuitive and mathematical explanation for why - and more importantly, how this happens to be true? What is the history/rationale behind it?

Many thanks.

share|improve this question
3  
Answer: Strong law of large numbers. –  Did Aug 21 '12 at 14:41
1  
It is the Law of Large Numbers. There's a lot of litterature on this subject, see for example Shiryaev's Probability. –  Stefan Hansen Aug 21 '12 at 14:42
    
I think you misunderstood the question. The OP is puzzled by the discrete form of the expectation and wants to understand what it is saying. He is not asking about convergence of a sum of a sequence of random variables to a limit. –  Michael Chernick Aug 21 '12 at 14:59
1  
@MichaelChernick: One of his questions is why the approximation can be used. And the answer to that is the Law of Large Numbers. –  Stefan Hansen Aug 21 '12 at 15:12
1  
@MichaelChernick: I don't follow. After "I often come across this estimation formula" he states an approximation and then asks why this can be used. –  Stefan Hansen Aug 21 '12 at 16:02

2 Answers 2

up vote 2 down vote accepted

As you are aware, the expected value of a random variable $X$ is computed as:

$\mathbb{E}\{X\} = \int_{-\infty}^{\infty}z f_{X}(z)dz$, where $f_X$ is the probability density function (PDF) of $X$.

Note that the above integral may not converge (e.g. if $X$ is a Cauchy random variable), and the PDF may not exist as well. But let's assume we are not getting into such problems, which is indeed the case in most practical settings.

Often, we will not know the PDF, or even its functional form. In such a case, one resorts to estimating the PDF from realizations of the random variable. That is, assume we have $N$ realizations of $X$ - $\{x_i\}_{i=1}^N$. Let us consider the following estimate:

$\hat{f}_X(z) = \frac{1}{N}\sum_{i=1}^N \delta(z-x_i)$, where $\delta(.)$ is the Dirac delta function.

So essentially, we are treating the random variable as a uniform discrete random variable, and putting a mass of $1/N$ over each of the observed values. The estimate of the expectation of $X$ becomes:

$\hat{\mathbb{E}}_N\{X\} = \int_{-\infty}^{\infty}z \frac{1}{N}\sum_{i=1}^N \delta(z-x_i)dz$

$= \frac{1}{N}\sum_{i=1}^N \int_{-\infty}^{\infty}z \delta(z-x_i)dz$

By the sifting property of the delta function, you will note that the integral becomes $x_i$. Hence, we arrive at the following expression for the sample expectation:

$\hat{\mathbb{E}}_N\{X\} = \frac{1}{N}\sum_{i=1}^N x_i$

Note that $x_i$'s are themselves random, since another set of draws from $X$ is likely to give me a different set of realizations. Thus the above estimate of the expected value is itself a random variable - dependent on the draws $\{x_i\}_{1}^N$ and the number of draws $N$. Since all $x_i$s are distributed identically (with PDF $f_X$), and are independent draws, the Laws of Large Numbers tell us that $\mathbb{E}_N\{X\} \rightarrow \mathbb{E}\{X\}$ with probability $1$ (almost surely), and in probability, as $N \rightarrow \infty$.

share|improve this answer
    
Thank you very much, very good post. My understanding is slowly materializing on this issue... One thing though: You say that let us assume $\hat{f}_X(z) = \frac{1}{N}\sum_{i=1}^{N} \delta(z - x_i)$ - let me understand: We are doing this because given no prior information, we are literally weighing each observation we have, by $\frac{1}{N}$, to ensure that the PDF sums to 1 of course. So every observation that happens to exist in the observation set gets this weight, and observations that didnt happen to come about, well too bad for them. (contd) –  Mohammad Aug 21 '12 at 15:20
    
(contd), After that, we insert this estimate into the actual formula of the expectation operator involving the weighted integral of the PDF, and now this time around, each observation gets weighted by the value of that observation itself... (via sifting). So I get that. What I do not get is 'where' is the frequency/popularity of some observation taken into account here? For example, you observed 99 instances of an r.v equaling 10, but only one instance equaled 11. Where is this information being taken into account in the above? –  Mohammad Aug 21 '12 at 15:25
    
Good question. If an observation (say $x_0$) occurs $K$ times, we will have the corresponding term repeated $K$ times in the sum of Dirac deltas. This automatically constitutes a frequency weighting. –  Kartik Audhkhasi Aug 21 '12 at 16:01
    
Right. How would we mathematically add this information to the equation you cite, correctly? $\hat{f}_X(z) = \frac{1}{N}\sum_{i=1}^{N} K_{x_i} \; \delta(z-x_i)$. Would this be acceptable? –  Mohammad Aug 21 '12 at 16:12
    
This equation is correct, except that the summation would be over unique values of $X$ observed in the $N$ samples. –  Kartik Audhkhasi Aug 21 '12 at 16:20

This is just the expected value applied to a discrete uniform distribution that puts probability mass 1/N on each of the N distinct outcomes of the random variable. Alternatively it could be the sample estimate of these expectations where x[n] represents an individual observation.

share|improve this answer
    
This is just the expected value applied to a discrete uniform distribution that puts probability mass 1/N on each of the N distinct possible values of the random variable... No this is not. –  Did Aug 22 '12 at 11:34
    
@did Oh come on. I am referring to the formula as given assuming the x[n] are iid. –  Michael Chernick Aug 22 '12 at 11:39
    
Oh come on, where is the discrete uniform distribution you are referring to? –  Did Aug 22 '12 at 11:42
    
The distribution that places mass 1/N at each x[n] for n=1,2,...,N. –  Michael Chernick Aug 22 '12 at 13:56
    
Which are certainly not the distinct possible values of the random variable. This seems to confuse the underlying common theoretical distribution of the i.i.d. random variables x[k] and the empirical random distribution of the sample x[1], ..., x[n]. –  Did Aug 22 '12 at 14:53

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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