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

Mueen Nawaz <m.n### [at] ieeeorg> wrote:
> http://en.wikipedia.org/wiki/Almost_surely

  Seems like my claims about the monkeys and Shakespeare were not, after all,
completely ridiculous.

-- 
                                                          - Warp

Post a reply to this message

"Mueen Nawaz" <m.n### [at] ieeeorg> wrote in:
> http://en.wikipedia.org/wiki/Almost_surely

So, a probability of 1 doesn't mean 'always', and a probability of 0 doesn't 
mean 'never' when there's infinity involved.  Was that so hard?

-- 
Tim Cook
http://empyrean.freesitespace.net

Post a reply to this message

Warp wrote:
> Mueen Nawaz <m.n### [at] ieeeorg> wrote:
>> http://en.wikipedia.org/wiki/Almost_surely
> 
>   Seems like my claims about the monkeys and Shakespeare were not, after all,
> completely ridiculous.

I never thought they were completely ridiculous. Just unconvincing. :-) 
It's still up in the air for me as to who is right. :-)

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

I think this is relevant:
http://en.wikipedia.org/wiki/Almost_surely

Post a reply to this message

Nicolas Alvarez wrote:
> I think this is relevant:
> http://en.wikipedia.org/wiki/Almost_surely

And I should learn to read the rest of the thread before posting a reply.

Post a reply to this message

John VanSickle wrote:
> 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.

	Well, it's not exactly a function.

-- 
Every hard drive I've ever bought has been larger than all my previous
hard drives combined. And this is without even trying.
--Seen on Slashdot.org


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

Post a reply to this message

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

Oh yeah, I certainly wasn't debating the accuracy of the result.  It 
appears that you already considered this detail anyway, so my 
nit-picking was entirely unnecessary.

I did like the Cantor set analogy by the way.  I didn't forsee it when I 
was reading your post and was delighted when you pointed it out.

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

Yeah, that's what I meant.

>>     lim_{n->inf} a^n = 0 if 0 <= a < 1
> 
> 	(Incidentally, I'm not sure I understand your limit. What is 'a' and
> why is it fixed?

For base m a would be (m-1)/m -- the probability that a single given 
digit of the random sequence doesn't contain a 1 in base m.

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

In that case I'll spare you the trouble of being tempted to read it 
later.  I just adapted the construction of a Vitali set from the real 
line to infinite binary sequences by replacing addition with xor.  A few 
small things changed as a result, but nothing major.

I'm enveious you had an integration theory class that got into measure 
theory.  I don't recall such a course being available back when I was 
taking math classes, but it would have been pretty fun had there been.

Post a reply to this message

Invisible wrote:
> (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 assume by "group" you actually mean to say "cyclic group"?  If not 
that might explain why it's proving hard to understand.

Post a reply to this message

>> (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 assume by "group" you actually mean to say "cyclic group"?  If not 
> that might explain why it's proving hard to understand.

I was under the impression the result applies to all groups - which is 
why the groups of prime order are always cyclic.

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message

Nicolas Alvarez wrote:
> Nicolas Alvarez wrote:
>> I think this is relevant:
>> http://en.wikipedia.org/wiki/Almost_surely
> 
> And I should learn to read the rest of the thread before posting a reply.

That is almost surely correct. ;-)

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message

Orchid XP v8 wrote:
> I was under the impression the result applies to all groups - which is 
> why the groups of prime order are always cyclic.

It is true that every subgroup of a finite group has an order which 
divides that of the group (this result has actually been around longer 
than group theory itself).  This implies that all prime order groups are 
cyclic.

The converse, however, does not hold.  Some finite groups do not have 
any subgroups corresponding to some of their order's divisors.

Post a reply to this message

Kevin Wampler wrote:
> Orchid XP v8 wrote:
>> I was under the impression the result applies to all groups - which is 
>> why the groups of prime order are always cyclic.
> 
> It is true that every subgroup of a finite group has an order which 
> divides that of the group (this result has actually been around longer 
> than group theory itself).  This implies that all prime order groups are 
> cyclic.
> 
> The converse, however, does not hold.  Some finite groups do not have 
> any subgroups corresponding to some of their order's divisors.

Ah, right. I guess I missed that technicallity.

Of course, intuitively, it totally makes sense that the order of a 
subgroup would have to be a factor of the group's order. I just thought 
that every group could be split into subgroups. So I guess there are 
large non-prime groups that don't have any [nontrivial] subgroups then?

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message

Orchid XP v8 wrote:
> Of course, intuitively, it totally makes sense that the order of a 
> subgroup would have to be a factor of the group's order. I just thought 
> that every group could be split into subgroups. So I guess there are 
> large non-prime groups that don't have any [nontrivial] subgroups then?

This is not actually true either.  If a group G is of order n, then G 
does have a subgroup of every order which is a *prime* factor of n. 
It's just that there's no guarantee for composite factors.

Post a reply to this message

Kevin Wampler wrote:
> Orchid XP v8 wrote:
>> Of course, intuitively, it totally makes sense that the order of a 
>> subgroup would have to be a factor of the group's order. I just 
>> thought that every group could be split into subgroups. So I guess 
>> there are large non-prime groups that don't have any [nontrivial] 
>> subgroups then?
> 
> This is not actually true either.  If a group G is of order n, then G 
> does have a subgroup of every order which is a *prime* factor of n. It's 
> just that there's no guarantee for composite factors.

So, in summary, G *definitely* has subgroups for every prime factor, and 
*might* have subgroups for some or all of the composite factors as well?

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message

Orchid XP v8 wrote:
> So, in summary, G *definitely* has subgroups for every prime factor, and 
> *might* have subgroups for some or all of the composite factors as well?

I believe that is correct.  In addition I think that G must have a 
subgroup for every prime power which still divides the order of G. 
Weather or not the composite factors have associated subgroups will 
indeed depend on the particular group G represents.

As an example consider the group of rotations of a tetrahedron.  It has 
12 elements but no subgroup of order 6.

Post a reply to this message

Kevin Wampler wrote:
> I did like the Cantor set analogy by the way.  I didn't forsee it when I
> was reading your post and was delighted when you pointed it out.

	It popped into my head while reading Darren and Tim argue in the other
thread. Delighted me too to see the relationship.

>>>     lim_{n->inf} a^n = 0 if 0 <= a < 1
>>
>>     (Incidentally, I'm not sure I understand your limit. What is 'a' and
>> why is it fixed?
> 
> For base m a would be (m-1)/m -- the probability that a single given
> digit of the random sequence doesn't contain a 1 in base m.

	Ah, I get it.

> I'm enveious you had an integration theory class that got into measure
> theory.  I don't recall such a course being available back when I was
> taking math classes, but it would have been pretty fun had there been.

	Well, I think it's standard in the first semester of analysis at the
grad level. Some good schools probably do it at the undergrad. I learned
this stuff only recently - learning as I go along.

-- 
Lisa: Oedipus killed his father and married his mother.
Homer: Who payed for THAT wedding?


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

Post a reply to this message

>> So, in summary, G *definitely* has subgroups for every prime factor, 
>> and *might* have subgroups for some or all of the composite factors as 
>> well?
> 
> I believe that is correct.  In addition I think that G must have a 
> subgroup for every prime power which still divides the order of G. 
> Weather or not the composite factors have associated subgroups will 
> indeed depend on the particular group G represents.
> 
> As an example consider the group of rotations of a tetrahedron.  It has 
> 12 elements but no subgroup of order 6.

http://en.wikipedia.org/wiki/Lagrange%27s_theorem_(group_theory)

It seems that for a *commutative* group, my original statements are 
correct. I found many other interesting properties, but failed to find 
any confirmation of your assertion about prime subgroup orders...

Post a reply to this message

Invisible wrote:

> http://en.wikipedia.org/wiki/Lagrange%27s_theorem_(group_theory)
> 
> It seems that for a *commutative* group, my original statements are 
> correct. I found many other interesting properties, but failed to find 
> any confirmation of your assertion about prime subgroup orders...

Wait a minute... this isn't finite sequences and probability! o_O

Post a reply to this message

>>> So, in summary, G *definitely* has subgroups for every prime factor, 
>>> and *might* have subgroups for some or all of the composite factors 
>>> as well?
>>
>> I believe that is correct.  In addition I think that G must have a 
>> subgroup for every prime power which still divides the order of G. 
>> Weather or not the composite factors have associated subgroups will 
>> indeed depend on the particular group G represents.
>>
>> As an example consider the group of rotations of a tetrahedron.  It 
>> has 12 elements but no subgroup of order 6.
> 
> http://en.wikipedia.org/wiki/Lagrange%27s_theorem_(group_theory)
> 
> It seems that for a *commutative* group, my original statements are 
> correct. I found many other interesting properties, but failed to find 
> any confirmation of your assertion about prime subgroup orders...

Wait, here we go:

http://en.wikipedia.org/wiki/Sylow%27s_theorem

Post a reply to this message