Let's say that instead of a 2 sided coin, I have a three state
random generator, which generates each state with equal probability.

        Now I had already shown that the likelihood of getting a
_particular_ infinite sequence was the same as getting a _particular_
value between 0 and 1. (That is, the likelihood is zero - I'm arguing
purely mathematically - let's put the "real" world aside).

        Intuitively, that's because a point is infinitely smaller than
the interval [0,1].

        In fact, if I were to ask the probability of getting a rational
number, the answer is still 0. While the set of rationals is infinite,
it's still infinitely smaller than the unit interval - the latter is of
a higher infinity.

        So how about this one: In my three state random sequence
generator, what is the probability of getting *any* sequence that
doesn't have one of the states? If I were to label the states 0, 1 and
2, the question would be: What is the probability of getting a sequence
that doesn't have 1 in it?

        Now this is equivalent to asking: What is the probability that
if I pick any number at random from [0,1], the number will not have a 1
in it when written with a base 3 expansion?

        It may not be obvious what the solution is. The set of all such
sequences may appear small, but in one sense it isn't: It has the same
cardinality as the real line (it is of the same infinity as [0,1]).

        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?):

http://en.wikipedia.org/wiki/Cantor_set

        Now I'll re-emphasize: While the Cantor set _appears_ to be
small, it is of the same cardinality as [0,1].

        It turns out this set has "measure" 0. And any integral of a
function (the uniform distribution in this case) over a set of measure
zero is 0.

        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.

        I think it's a cool result - shows that probability theory is at
least consistent.


-- 
Guitar for sale. Very cheap. No strings attached.


                    /\  /\               /\  /
                   /  \/  \ u e e n     /  \/  a w a z
                       >>>>>>mue### [at] nawazorg<<<<<<
                                   anl

Post a reply to this message

Mueen Nawaz wrote:
>         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.

According to wikipedia, any algorithmically random sequence of 'b' symbols 
forms a normal number in base 'b'.

http://en.wikipedia.org/wiki/Normal_number

So, yeah. :-) That's really a fascinating page. :-)

-- 
   Darren New, San Diego CA, USA (PST)
   There's no CD like OCD, there's no CD I knoooow!

Post a reply to this message

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

Mueen Nawaz wrote:
>         I think it's a cool result - shows that probability theory is at
> least consistent.

I don't know if it's just me, but I find certain areas of mathematics 
fascinating, and others utterly boring.

For example, take DSP. You've got impulse responses and convolution. 
You've got correlation, the Fourier transform, and related transforms. 
You've got Fourier duals, trigonometric identities, IIR filters, the 
Laplace transform, the Z-transform, transfer functions, the fast Fourier 
transform, filter kernel windows, autocorrelation...

Then you have set theory. The entire theory seems to be about nitpicking 
and pointless questions such as "are there more rational than irrational 
algebraic numbers?" I mean, like, *who cares*?

...and then I spend 2 hours drawing squares and cubes, and shifting 
algebra around to painstakingly derive [a special case of] the binomial 
theorum from first principles. The euphoria of finally figuring out the 
hidden pattern is topped only by the frustration at discovering that 
somebody else already figured this out - several thousand years ago.

I guess some questions are just more interesting than others. Certain 
areas of mathematics seem to abound with interesting concepts and 
beautiful ideas. And other areas seem to involve only splitting hairs 
and irritating technicalities.

Post a reply to this message

Invisible wrote:

> ...and then I spend 2 hours drawing squares and cubes, and shifting 
> algebra around to painstakingly derive [a special case of] the binomial 
> theorum from first principles. The euphoria of finally figuring out the 
> hidden pattern is topped only by the frustration at discovering that 
> somebody else already figured this out - several thousand years ago.

Actually, I kinda like the idea of *knowing* that a certain formula, 
derived by someone else, is correct, and that I am not simply taking it 
on faith.

Regards,
John

Post a reply to this message

Mueen Nawaz wrote:

>         It turns out this set has "measure" 0. And any integral of a
> function (the uniform distribution in this case) over a set of measure
> zero is 0.

I understand that the Dirac delta function,

http://en.wikipedia.org/wiki/Dirac_delta_function

is an exception to this.

Regards,
John

Post a reply to this message

>> ...and then I spend 2 hours drawing squares and cubes, and shifting 
>> algebra around to painstakingly derive [a special case of] the 
>> binomial theorum from first principles. The euphoria of finally 
>> figuring out the hidden pattern is topped only by the frustration at 
>> discovering that somebody else already figured this out - several 
>> thousand years ago.
> 
> Actually, I kinda like the idea of *knowing* that a certain formula, 
> derived by someone else, is correct, and that I am not simply taking it 
> on faith.

Well, it's not so much that. Obviously I suck at math and there are 
several centuries (if not millennia) of mathematicians far more clever 
than me to check it. It's more that I'm curios to know *why* it works.

(For example, if you have a group of size X, it has subgroups of every 
size that is a factor of X - including 1 and X itself. I still don't 
completely understand why, but it's still cool.)

Post a reply to this message

Kevin Wampler wrote:
> 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....

	That's only a technicality that I was hoping no one would notice.
Strictly speaking, the Cantor set is the set of all numbers that _can_
be written without a 1 in the base 3 expansion (as in your case) - as
opposed to just numbers that *must* be written without a 1. The
important point is that there are only a countably infinite number of
such "exceptions", and so those exceptions are "tiny" compared to the
whole Cantor set, because the Cantor set has the cardinality of the reals.

	Put another way, I showed that the even if I allow some sequences with
a single 1 to sneak in, the probability is still 0.


> 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

	One would be in the set of sequences we're interested in, and the other
wouldn't. In terms of the Cantor set, they're both in it as they are the
same number.

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

	Well, we all know *that*.<G> I was pointing out a different way of
looking at it.

	(Incidentally, I'm not sure I understand your limit. What is 'a' and
why is it fixed?

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

	I didn't read the whole thing - xors make my head hurt. But I got the
general idea, having seen similar arguments before. When I was learning
integration theory using measures, I noticed that integrals were always
defined over _measurable_ sets.

	Moral of the story: Don't apply probability to problems constructed
using the axiom of choice.<G>

-- 
Guitar for sale. Very cheap. No strings attached.


                    /\  /\               /\  /
                   /  \/  \ u e e n     /  \/  a w a z
                       >>>>>>mue### [at] nawazorg<<<<<<
                                   anl

Post a reply to this message

Mueen Nawaz wrote:

> 	That's only a technicality that I was hoping no one would notice.

How quotable is that? :-D

Post a reply to this message

To muddy the waters further:

http://en.wikipedia.org/wiki/Almost_surely

-- 
Guitar for sale. Very cheap. No strings attached.


                    /\  /\               /\  /
                   /  \/  \ u e e n     /  \/  a w a z
                       >>>>>>mue### [at] nawazorg<<<<<<
                                   anl

Post a reply to this message