2
$\begingroup$

I am reviewing some probability for a class I am about to take, and I came up with this example to try to help my intuition.

Suppose I take the the space of all sequences of the two symbols $H,T$. Let $X_i$ be the function on this space that is 1 if the $i$th entry is $H$ and $0$ otherwise. Then I think that these can be considered as independent identically distributed random variables, so that the Strong Law of Large Numbers should say that $ \lim \frac1n\sum_{i=1}^n X_i = \frac 12 a.e. $

This implies that the set of sequences of $H,T$ which in the limit are not balanced have measure $0$. The measure here is the one so that the set of all sequences starting with $H$ has measure $\frac12$, the set of all sequences starting with $HH$ has measure $\frac14$, etc.

So my question is: Is this correct? Is there such a measure on this space of sequences? If so, is there a nice way to see the conclusion at the beginning of the paragraph above without quoting the strong law of large numbers?

2 Answers 2

3

The space you're talking about, the space of all one-way infinite binary sequences, is known as Cantor Space (especially within logic). I think of it as the set of all paths through the full infinite binary branching tree.

As Qiaochu said, the 'fair coin measure' can be thought of as a product measure. But I prefer to just recall that by Caratheodory's extension theorem, it suffices to define any set function $\mu$ on the algebra of basic clopens (that is, sets of the form $[\sigma]:=\{A \in \{0,1\}^{\mathbb{N}} : A \text{ extends } \sigma \},$ where $\sigma$ is some finite binary string) such that $\mu[\sigma] = \mu[\sigma 1] + \mu[\sigma 0]$ and $\mu[\varnothing] = 1$. ("$\varnothing$" denotes the empty finite binary string; all elements of $\{0,1\}^{\mathbb{N}}$ extend it.)

So to get the measure you want, you just define your $\mu$ such that $\mu[\sigma 0] = \mu[\sigma 1] = \mu[\sigma]/2$. Notice that in terms of the tree picture, you're just saying that no matter where you are in the tree, it costs the same amount of measure to go the the left as to the right (so my tree is growing upwards).

Notice that this measure (often called the Lebesgue measure because of what @Michael said in the comments) is just a special case of a Bernoulli measure, which corresponds to a coin with probability $p$ of heads and $1-p$ of tails (or if you prefer $p$ to go left in the tree and $1-p$ to go right).

There are other ways to see that almost every number must have a 'balanced' frequency of 0's and 1's, but none of them are much nicer than using the law of large numbers. For example, one could apply, as @Qiaochu suggested, the Borel-Cantelli lemma. To do so, you want to exploit something that happens infinitely often (because of the $\limsup$). If some $A \in \{0,1\}^{\mathbb{N}}$ does not have a balanced number of 1's and 0's, then frequency of 0's compared to the frequency of 1's is outside of the interval from $[1- 1/n, 1+1/n]$ for some $n$ infinitely often. I haven't checked the whether the resulting sets have measures whose total sum is finite (as is required by the B-C), but something like this should work.

One could also apply Birkhoff's Ergodic Theorem (which is just a generalization of the law of large numbers anyway) or the theory of Algorithmic Randomness to conclude that almost every normal has a balanced frequncy of 0's and 1'. In fact, you can conclude much more, that almost every real number is Normal in every base.

  • 0
    Quinn: As @Nate said.2012-08-22
3

Yes, yes, and it depends on what you mean by "nice."

The measure you want is product measure on the product space $\{ 0, 1 \}^{\mathbb{N}}$, where $\{ 0, 1 \}$ is given the obvious probability measure. An alternate description of this measure is as Haar measure on the group $(\mathbb{Z}/2\mathbb{Z})^{\mathbb{N}}$. From either of these descriptions, it exists and has the properties you want it to.

You can get the conclusion you want without the SLLN by using the central limit theorem instead; alternately, you can compute the characteristic function of $\frac{1}{n} \sum_{i=1}^n X_i$ by hand, verify that it converges to the characteristic function of the constant r.v. with value $\frac{1}{2}$, then use Lévy continuity... (This only gets you convergence in distribution; see did's comments below.) I don't know a way to get this conclusion which doesn't require some level of technology.

Edit: Wikipedia claims that this result ought to follow from Borel-Cantelli, but I don't see it at the moment.

  • 0
    I liked the Wikipedia link... very interesting.2012-08-29