# How many samples needed to approximate true mean?

If I have some arbitrary random variable with true mean $\mu$ how many samples from its distribution do I need to take such that the empirical mean $x$ approximates $\mu$ within an error of less than $\epsilon$?

That is, how many samples are needed such that: $\lvert \bar x-\mu\rvert \le \epsilon$

I know that law of large numbers allows that if I have $\infty$ samples it would definitely converge but if I can't get that many samples and am willing to tolerate partial error, how do I determine the sample size?

• Do you know the population size? Do you know the probability distribution? – Lior Kogan Apr 29 '15 at 11:22
• I don't think that is pre-known. I am specifically interested in knowing how many samples of a Monte Carlo trajectory I would need to get an estimated value within error $\epsilon$ of the true mean which is unknown.. This is in the context of reinforcement learning if that helps. – user3425451 Apr 29 '15 at 12:18

No matter what your sample size is (unless it is the whole population), there is no guarantee that the error of the estimate would be bounded.

Imagine a population where the value of the parameter of interest is 0 for all items, except for one item where the parameter's value is Googolplex.

Instead, it is common to construct a confidence interval.

• So in the particular case that I'm interested in, I am interested in knowing how many trajectories of a Monte Carlo method I would need to run in order to get close to the true value. Are you saying that that is not possible to definitively determine without prior knowledge of the variable being sampled? In particular, I'm considering this in the reinforcement learning context: webdocs.cs.ualberta.ca/~sutton/book/ebook/node51.html The author mentions: "Both first-visit MC and every-visit MC converge to [true value] as the number of visits (or first visits) goes to infinity" – user3425451 Apr 29 '15 at 13:33
• That's right. You need to either (1) know the value-range of the parameter (assume it is bounded) and the population size (2) construct a confidence interval, so you can say something like "we are 99% confident that the error is less than ϵ". – Lior Kogan Apr 29 '15 at 13:42
• Ok, that seems to make sense. I'm only iffy about this because my professor said that there was an algorithm that can tell us how many samples would be needed for empirical mean to match true mean to $\epsilon$ precision in the Monte Carlo case. Unfortunately, he prefers that we search on our own so he didn't tell what the algorithm is :) – user3425451 Apr 29 '15 at 13:47

If you are talking about $|\bar{x}-\mu|$ then LiorKogan is right, there's no guarantee that the error is bounded. Now, to compute this confidence interval, you need to find the $x$ such that $P(X>x)>\eta$, where $\eta$ is some bound in the probability that you define. To compute it, you would need to know the distribution of $x$, which usually you don't know, but if you say that the mean of your random variable IS defined, then you can be sure by the generalized CLT that the mean follows a Levy Stable Distribution: if you can infere the exponent, you get an estimate for what you want. If the variance is defined, then you get the usual Gaussian case (case $\alpha=2$ of the Levy Stable). The classic example of this problem is in the context of election polls: "How many people do I have to ask to get a confidence interval lower than 1%?".

This is simplified for practical application. Say $\bar x$ is a sample mean computed with $n$ samples, $\mu$ is the mean of the true population, and $\sigma$ is the standard deviation of the true population. Central Limit Theorem shows that the $E[\bar x] = \mu$. It is also shows that the standard deviation of $\bar x$ is $SD(\bar x) = \frac{\sigma}{\sqrt n}$ (this is commonly referred to as the standard error). You can estimate $\sigma$ by just taking the standard deviation of your sample. Just increase $n$ until you have a standard error that you are satisfied with.

If your random variable is bounded, then the sample mean ( normalized sum of IID RVs) of that random variable obeys the following bound: $P(|\bar{x} - \mu| > \epsilon) \leq e^{-2Ne^2}$. This result is for the simple case of $X \in [0,1]$. This is the famous Hoeffding inequality.

The nice part of this theorem is that the assumptions are very weak for the general case, bounded RV, and IID Samples. This gives it a lot of "practical" use but there are some major pitfalls. Note that this is convergence in probability (it's not that $\bar{x}$ gets close to $\mu$, it's that the probability that $\bar{x}$ is far can be made arbitrarily small).

Another thing to note is that in the proof of the LLN you encounter a similar inequality to Hoeffding's inequality via the Chebyshev inequality: $\operatorname{P}( \left| \overline{X}_n-\mu \right| \geq \varepsilon) \leq \frac{\sigma^2}{n\varepsilon^2}$, where $n$ is the sample index, $\sigma$ is the variance of $X$ and $\overline{X}_n$ is the sample mean on $n$ samples. Again the assumptions are fairly weak, IID samples and each $E(X_I) < \infty$.

You can use either of these expressions to answer a question "close" to the one you posed, which is, Given $N$ samples, what is the probability that the mean is far from the true mean. You essentially treat this as not a bound on the difference, but a bound on the error.