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?

  • 11
    "A sequence of 100 consecutive heads will always occur infinitely many times" ... uh... Why? The sequence 01010101.... has zero ocurrences2011-08-23
  • 0
    +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.2011-08-23
  • 0
    @leonbloy: That's not random...2011-08-23
  • 0
    @Guffa: Give me a sequence, I'll tell you it's not random, therefore no sequence is random, therefore this problem makes no sense. That's the road down which your logic goes.2011-08-23
  • 0
    @Guffa: technically, to say that a particular outcome of a random process "is (or is not) random" does not make sense. See anon's answer.2011-08-23
  • 0
    @anon: Any sequence that you construct with the specific goal of not containing a certain sequence, will not be random.2011-08-23
  • 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... :-)2011-08-23
  • 0
    @Didier, I put "possible" in quotation marks and added the qualifier "in some respect" precisely because I didn't want to get into this :) That was the best I could do to try to get the general idea across without being formal.2011-08-23
  • 1
    @guy, I know, I know, but I could not resist the pun... As the saying goes, *l'occasion était trop belle.*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
    Of course you can create a sequence with random components that doesn't have certain sequences, but then it's not random. You could for example easily make an infinite sequence based on random, where tail-head-heads never occurs, but then it would obviously not be truly random.2011-08-23
  • 0
    @Guffa: A random sequence is allowed to take on *any* sequence of heads and tails - the fact that we are capable of thinking of these sequences does not change the fact they are allowed outcomes. This means it's possible for an infinite sequence of heads/tails to satisfy the property of not having a 100 heads stretch. The mere possibility of it is enough to distinguish *surely* from *almost surely*, by their very definitions.2011-08-23
  • 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.2011-08-23
  • 0
    @Guffa: I have two questions. 1) What is your definition of a *random sequence*? 2) Where do you think that the notion of "random sequence" enters into Kolmogorov's 0-1 Law?2011-08-23
  • 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.)2011-08-23
  • 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.)2011-08-23
  • 0
    @Didier: You're right, I was glossing over that. I've changed the sentence.2011-08-23
  • 0
    @Pete L. Clark: You don't like the term *random sequence*? What do you want to call it?2011-08-23
  • 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.2011-08-23
  • 0
    @Pete L. Clark: The sequence that anon constructed in his answer is an example of something that is not random. The sequence is designed specifically to not contain 100 consecutive heads. By removing this possibility, the result of one coin toss is not independend of the previous, and thus not random.2011-08-23
  • 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.2011-08-23
  • 0
    @anon: Obviously you didn't understand my reasoning, which you of course realise yourself, so instead of inventing something so absurd from your understanding of it, you should try to understant it instead.2011-08-23
  • 0
    @Guffa: Your reasoning is that any constructed outcome designed to satisfy certain properties cannot be a valid outcome of something random, no?2011-08-23
  • 0
    @anon: No. Obviously any constructed outcome can be repeated by a truly random outcome. My reasoning is that the constructed outcome is not random if it's designed to avoid certain sequences that would possibly occur in a random sequence.2011-08-23
  • 0
    @Guffa: It should be somewhat informative that everyone except you finds anon's and leonbloy's examples to be correct. The problem isn't with the examples but with what appears to be your conception of randomness, which is why people are asking you how you would _formally_ define a "random sequence": so that they can point out to you where your problems are coming.2011-08-23
  • 0
    I've never said "make the random sequence definitely equal to such and such", I've only said the sequences I've constructed are valid outcomes, and that's all that's needed. Your reaction - to imply I've simply called for the random sequence to equal one and only one definite given sequence - confuses me, to put it mildly.2011-08-23
  • 0
    @anon: You are missing the point. You have made the outcomes *not* equal to specific sequences. There is nothing wrong with the possible outcomes, it's the missing possible outcomes that makes it not random.2011-08-23
  • 0
    @Guffa: Where did I "*make*" the outcome not equal to specific infinite sequences? I've **never once** barred any specific infinite sequence from occurring, *only* remarked on the possibility of specific infinite sequences occurring (namely, those with no finite subsequence of 100 heads).2011-08-23
  • 1
    I see this long discussion and I have yet to see @Guffa say what he thinks the word "random" means. It looks to me that you're conflating the likelihood of a particular sequence like leon's happening with the "randomness" (whatever the heck it means for you). In other words: what makes you say leon's and anon's sequences can't happen?2011-08-24
  • 1
    @Guffa, certainly you seem to mean that random is the same as "what we expect to see in real life for an infinite number of tosses". Though this is/seems intuitive, it does not make it true, the probability that you see any particular sequence in $x$ throws goes to 1 as $x$ goes to infinity but that does not mean that it will happen, simply because in lay-man terms, it is not 1, it approaches 1.2011-08-24
  • 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
    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).2011-08-23
  • 0
    The releevance is that it is a counterexample to the poster's assertion that there _must_ be infinitely many 1s.2011-08-24