1
$\begingroup$

I was reading about Kolmogorov's zero-one law specifying:

a certain type of event, called a tail event, will either almost surely happen or almost surely not happen

I came to this example:

In an infinite sequence of coin-tosses, a sequence of 100 consecutive heads occurring infinitely many times is a tail event.

That can't be true, can it?

In an infinite sequence of coin-tosses, any specific sequence will occur infinite times. A sequence of 100 consecutive heads will always occur infinitely many times, not almost surely.

Saying that a sequence will occur any less than infinite many times actually get absurd. If the 100 consecutive heads occur any finite number of times, if I then get 99 consecutive heads any time after that, the next toss will not be random, but it has to turn up tails.

So, am I missing something fundamental?

  • 1
    @guy, I know, I know, but I could not resist the pun... As the s$a$ying goes, *l'occasion était trop $b$elle.*2011-08-23

2 Answers 2

10

There are infinite sequences of coin flips that do not contain a single stretch of 100 consecutive heads. In fact, there are uncountably infinitely many: let $t_1,t_2,t_3,\dots$ be an infinite sequence of numbers from $\mathbb{N}$, and $h_1,h_2,h_3,\dots$ be an infinite sequence of numbers from $\{0,1,2,\dots,99\}$. Then a sequence of $t_1$ tails, $h_1$ heads, $t_2$ tails, $h_2$ heads, and so on is a sequence with no stretch of 100 heads.

When dealing with infinity, "almost surely" deals with situations that occur with probability $1$ according to the formal notions associated with a probability space. This does not imply there are no valid situations where an event occurs or a hypothesis is sasisfied, as Wikipedia says:

If an event is sure, then it will always happen, and no outcome not in this event can possibly occur. If an event is almost sure, then outcomes not in this event are theoretically possible; however, the probability of such an outcome occurring is smaller than any fixed positive probability, and therefore must be 0. Thus, one cannot definitively say that these outcomes will never occur, but can for most purposes assume this to be true.

  • 0
    @Guffa To make your intuition precise about what it means for an individual sequence to be random, check out [algorithmic randomness](http://www.scholarpedia.org/article/Algorithmic_randomness) (see also [Wikipedia](http://en.wikipedia.org/wiki/Algorithmically_random_sequence)).2011-12-19
0

To say that "a tail event, will either almost surely happen or almost surely not happen" is not true if one drops an assumption of independence that you did not state, but which is usually stated in this context. (I suspect one could weaken it, but one cannot drop it completely and get the same conclusion.) Here is a simple example: For $i=1,2,3,\dots$, let $X_i = 0$ or $1$ with respective conditional probabilities $1-p$ and $p$, given the value of $p$, and suppose they are conditionally independent given $p$, and $p$ itself is a random variable uniformly distributed between $0$ and $1$. Consider the event $ \lim_{n\to\infty} \frac{X_1+\cdots+X_n}{n} < \frac12. $ That is a tail event with probability $1/2$.

Suppose you assume independence, and again $X_i = 0$ or $1$, but this time $\Pr(X_i = 1) = 1/2^i$. Then $E(X_i) = 1/2^i$, so $ E(X_1+X_2+X_3+\cdots) = \frac12+\frac14+\frac18 + \cdots = 1. $ If the expected value of the sum is finite then $\Pr(X_1+X_2+X_3+\cdots <\infty)=1$, so the event $X_i=1$ must happen for only finitely many values of $i$.

  • 0
    The releevance is that it is a counterexample to the poster's assertion that there _must_ be infinitely many 1s.2011-08-24