Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
10  
"A sequence of 100 consecutive heads will always occur infinitely many times" ... uh... Why? The sequence 01010101.... has zero ocurrences –  leonbloy Aug 23 '11 at 18:00
    
+1 to leonboy's comment. Remember that any particular sequence of 0's and 1's is "possible" in some respect. Each individual sequence has probability 0. So, it isn't that it is "impossible" to see a sequence like 01010..., it's just that the set of all outcomes such that stretches of 100 consecutive heads don't occur infinitely often has probability 0. –  guy Aug 23 '11 at 18:06
    
@leonbloy: That's not random... –  Guffa Aug 23 '11 at 18:22
1  
@guy, your advice is to Remember that any particular sequence of 0's and 1's is "possible" in some respect. In fact I would rather say that any particular sequence of zeroes and ones is impossible... :-) –  Did Aug 23 '11 at 19:17
1  
@guy, I know, I know, but I could not resist the pun... As the saying goes, l'occasion était trop belle. –  Did Aug 23 '11 at 19:40

2 Answers 2

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.

share|improve this answer
3  
@Guffa The individual sequence are not, themselves, random things. They are fixed entities. What has the random behavior is the thing that picks among the sequences we might observe. Saying that "something" happens with probability 1 means that we will randomly select a FIXED sequence such that "something" happens with probability 1. –  guy Aug 23 '11 at 18:25
3  
(If you think that randomness comes in via "random variables", you need to read the fine print of this definition. A random variable is simply a measurable, real-valued function defined on the probability space. If you don't know what these words mean, then you haven't yet grasped the formalism of probability theory under which Kolmogorov's Theorem applies.) –  Pete L. Clark Aug 23 '11 at 18:41
3  
@anon: When dealing with infinity, "almost surely" can be taken to mean that probability converges to 1 in the limit... One needs to be careful here since the occurrence of some events involving the infinite sequence cannot be checked through any of its finite parts. For example, looking at finite portions of the sequence of zeroes and ones tells you nothing about the occurrence of infinitely many ones in the complete sequence. (Some people refer to this as the difference between the weak law of large numbers and the strong law of large numbers.) –  Did Aug 23 '11 at 19:14
4  
@Guffa: I'm not asking for a name. I'm asking for a definition. You have replied to various people's assertions by saying "that's not random", so to help you out it would be best to know what definition of random sequence you're using. But to be more direct about it: the sample space in question consists of all countably infinite sequences from a $2$-element set -- say $\{0,1\}$ -- so if you think that you should only be taking the "random sequences", whatever that means, I think you are misinterpreting the setup. –  Pete L. Clark Aug 23 '11 at 19:53
2  
@Guffa: You use that word. I don't think it means what you think it mea- wait, what do you think it means, anyway? By your reasoning, it's impossible to ever flip heads because I can design an outcome of a flip to be heads. But I just flipped a coin right now, and it came up heads, despite the fact I designated it beforehand, go figure. –  anon Aug 23 '11 at 20:43

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$.

share|improve this answer
    
I fail to see the motivation of your second example in the context of the triviality of tail sigma-algebras. The event [infinitely many ones] IS a tail event and it HAS probability zero or one (zero, in this case). –  Did Aug 23 '11 at 23:21
    
The releevance is that it is a counterexample to the poster's assertion that there must be infinitely many 1s. –  Michael Hardy Aug 24 '11 at 0:00

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.