1

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.

Zachiah
  • 123
  • I do not quite understand. Suppose after $n$ rolls you have $K$ ones; the laws of large numbers say $\frac{K}{n}\to \frac16$ in probability and almost surely as $n$ increases. Are you asking whether there will eventually be an $n$ where $|K -\frac n6| > 40$? If so, the answer is yes with probability $1$, but again with probability $1$ there will be a larger $n$ with $K=\frac n6$ – Henry Oct 06 '22 at 02:18
  • Yes, that's what I was asking. How do you prove this though? – Zachiah Oct 06 '22 at 11:40
  • It is a fairly standard result for random walks. One way is to show there is a positive probability (which you can bound below) of getting beyond the boundary from any position in a given number of steps, and then add these up in a sensible way – Henry Oct 06 '22 at 12:27

1 Answers1

1

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.

Qiaochu Yuan
  • 419,620