# How can one quantify the convergence of relative frequency to probability?

Say I run a simple Bernoulli trial a number of times and compute the relative frequency for success. Clearly the relative frequency should represent the underlying probability for success better the more experiments I run.

My question is this: Is there any way to say how close the two values are given the number of times the experiment was run? For example if I run the experiment N times, what is the expected deviation of the relative frequency and the probability? Or turning the question around: If I want to know the probability up to an uncertainty of ε, how many experiments do I have to run?

Any pointers to results in this direction would be appreciated.

• Of course you can never be sure of knowing the probability up to an uncertainty of $\epsilon$ - there is always a chance that you get unlucky and have far more (or less) successes than you "should". You can have high probability of being close, and that's what concentration inequalities like Chebyshev can quantify. In statistics, people like to think of this concept in terms of confidence intervals. – Nate Eldredge Mar 23 '18 at 13:42
• By the way, the best place for such a question may be stats.stackexchange.com. – Nate Eldredge Mar 23 '18 at 13:42

Let $X$ be the arithmetic mean of a random sample of size $n$ chosen from a given distribution with mean $\mu$ and variance $\sigma^2$. Then for any $\epsilon>0$ $$P(|X-\mu| \ge \epsilon) \le \frac{\sigma^2}{ n \epsilon^2}$$
Example: tossing a fair coin (mean $\mu=1/2$, variance $\sigma=1/4$), I want to get within $\epsilon = 0.1$ of the mean $1/2$. If I toss it $n=1000$ times, then I will be within that error with probability at least $$1-\frac{\sigma^2}{n\epsilon^2} = \frac{159}{160} \approx 0.99$$
Now $X = H/n$ where $H$ is the number of times my coin came up on heads. So this means (fair coin, tossing 1000 times) $$P(400 < H < 600) > 0.99$$