Mueen Nawaz wrote:
 >         In point of fact, it's the Cantor set (i.e. what is the
 > probability that a number you pick will be from the Cantor set?):

I think that it's unfortunately a touch more involved than that.  For 
instance:

0.200000....
0.122222....

I think represent the same number on the real line, but one would be in 
the set and one wouldn't.  Nevertheless I do think that the Cantor set 
is a really intuitively useful visualization in this case, and certainly 
works perfectly well for all finite sequences.

 >
 > So the probability of getting any infinite sequence that doesn't
 > have one of the states is zero. I'm willing to bet that this generalizes
 > to any base.


It does, but the proof is probably easier if you compute the limit as 
the sequence length goes to infinity rather than visualize it geometrically:

     lim_{n->inf} a^n = 0 if 0 <= a < 1


 > shows that probability theory is at least consistent.

This sort of thing is actually way more subtle than it might appear at 
first, but in a very very interesting way.  I've attempted to construct 
an example to illustrate this, but I might have botched something so 
fair warning:

We'll just consider infinite binary sequences.  First, we'll define an 
equivalence relation R on these sequences.  Say that R(x,y) iff y = 
xor(x,q) for some sequence q which eventually starts repeating.  Since R 
is a relation we can use it to partition the set of infinite binary 
sequences into equivalence classes.

Then create a set S with one member of each equivalence class. What's 
the probability that a random sequence will be in S?

---

Now for why this is tricky. Let's say that the probability that a random 
sequence is in S is some number, call it p.  You can (if I haven't 
messed it up) show that p+p+p+... = 1, which is pretty clearly impossible.

To do this, we'll define an infinite sequence of sets.  First, note that 
there's only countably many infinite binary sequences which eventually 
repeat, so we can put them in correspondence with the integers.  For 
each integer k let's then define q(k) to be the k'th sequence in this order.

Now we'll define an infinite sequence of sets, one for each integer k. 
Let S_k be the set of infinite sequences such that S_k = {xor(s,q(k)) : 
s in S}.  First note that these sets are all disjoint by virtue of our 
definition of S.  Next, note that for any infinite binary sequence, u, 
you can find some S_k which contains it by noting that s will have some 
representative, s, in S and thus for some k xor(u,q(k)) = s.

Now something very odd has happened here.  We assumed before that the 
probability a random sequence was in S was p.  Since each S_k has the 
same `measure' as S the chance that a random sequence lies in any S_k is 
still p.  Since the S_k sets are pairwise disjoint the chance that a 
sequence will be in the union of n them can be found by n*p.  But we 
have infinitely many S_k sets and the probability that a sequence is in 
their union is one, so we have

1 = sum_{0:inf} p

Since no real number has this property, p cannot exist.  Thus there is 
no probability (zero or otherwise) that a random sequence is in S.  Said 
in more standard terminology: S has no measure.

---


This same sort of thing underlies the famous Banach-Tarski paradox, if 
you're interested in more.

Post a reply to this message