Are probabilities of repeated independent random events gauranteed to deviate from the expected propabilities by any constant number of experiments?

44 Views Asked by At

So if I roll a die, there is a $1/6$ chance that I get let's say a 1. From my understanding, this implies that if I were to pick any tolerance $\theta > 0$, and then repeatedly roll the die, It is guaranteed that eventually the proportion of 1's rolled compared to total rolls would deviate from $1/6$ be less than $\theta$.

My question is let's say I was to pick a number $x$ which is the number of experiments "off", I want to be, is it guaranteed that eventually, I will, for a moment, be off by more than $x$ experiments?

As a concrete example, let's say I picked $x = 40$ for the die example. Is it guaranteed that eventually, I will be off from the expected probability ($1/6$), by 40 rolls?

My intuition tells me that yes it will eventually happen because, if $n$ is the number of rolls, $40/n$ approaches 0 as $n$ gets large, and thus being "40 off" would become more and more insignificant, but I have no idea how to prove something like this, and my intuition might be wrong anyway.

1

There are 1 best solutions below

0
On BEST ANSWER

Yes, this is true, in the sense that the probability that this happens is $1$ (this is not quite the same as "guaranteed"). First I'll give an elementary proof of a simpler version of this result for flipping a fair coin, then a less elementary proof of a much more general result using the central limit theorem (although likely weaker results would suffice).

So, suppose we flip a fair coin $2n$ times (this simplifies things slightly but doesn't really matter), and for some fixed $x$ we want to know whether we are guaranteed that at some point the number of heads differs from the expected number $n$ by more than $x$. This is true and we can prove it by bounding the probability that this doesn't happen, which after $2n$ flips is

$$\frac{1}{2^{2n}} \sum_{k=n-x}^{n+x} {2n \choose k}.$$

Now, we know that ${2n \choose k}$ attains its maximum when $k = n$, so this sum is bounded by $\frac{2x+1}{2^{2n}} {2n \choose n}$. We also have an elementary argument which shows that ${2n \choose n} \le \frac{2^{2n}}{\sqrt{2n}}$, from which it follows that

$$\frac{1}{2^{2n}} \sum_{k=n-x}^{n+x} {2n \choose k} \le \frac{2x+1}{\sqrt{2n}}.$$

As $n \to \infty$ this converges to $0$, meaning that the probability that after $2n$ flips the number of heads differed from the expected number of heads by more than $x$ converges to $1$. It follows that the event given by the union of all these events (meaning that the number of heads differs by more than $x$ at some point) has probability exactly $1$, so happens almost surely.

Now for the much more general result. Let $X$ be a random variable with finite mean $\mu$ and finite variance, and let $S_n = X_1 + \dots + X_n$ be the sum of $n$ iid copies of $X$. By the central limit theorem, $\mathbb{P}(|S_n - n \mu| \le x)$ grows like $O \left( \frac{x}{\sqrt{n}} \right)$ (exactly as in the above computation) and in particular converges to $0$ as $n \to \infty$. So as before it follows that $\mathbb{P}(|S_n - n \mu| > x)$ converges to $1$ and hence the union of all these events has probability $1$ and happens almost surely.