## Randomness (was: AI)

Expand Messages
• ... To assert that pi is not random is meaningless. Random numbers are a sequence of numbers with the property that no member can be predicted from the
Message 1 of 20 , Mar 26 8:05 AM
• 0 Attachment
On Mon, 25 Mar 2002, Martin Sewell wrote:
> > The problem with using Kolmogorov Complexity as a measurement of randomness
> > is that it implies that the sequence of numbers represented by pi (which
> > has never failed a frequency based statistical test for randomness) aren't
> > random.

At 13:28 26/03/2002 +0000, Peter Ross wrote:
>Sigh .... pi is not random.
>[...]

To assert that "pi is not random" is meaningless.

Random numbers are a sequence of numbers with the property that no member
can be predicted from the preceding elements; in particular these cannot
form a progression or follow any regular or repetitive pattern. The
sequence of digits which we represent by pi satisfies this definition.

>Kolmogorov/Chaitin/Solomonov complexity is currently about the only
>reasonable definition we have for what it means for a sequence to be random.
>[...]

Whilst proving randomness is impossible and measuring randomness is an area
of debate; randomness is already precisely defined, thus:
A sequence of numbers is random if no member can be predicted from the
preceding elements.

Whilst Kolmogorov Complexity is *a* (rather good) definition of randomness,
which plays a central role in algorithmic information theory, it is by no
means universally accepted as *the* definition of randomness.

Regards

Martin
• ... You have just proven (partially) that Pi is not random. Given a sequence of numbers taken from Pi, one may observe that they are taken from Pi and thus
Message 2 of 20 , Mar 26 11:10 AM
• 0 Attachment
> To assert that "pi is not random" is meaningless.
>
> Random numbers are a sequence of numbers with the property that no member
> can be predicted from the preceding elements; in particular these cannot
> form a progression or follow any regular or repetitive pattern. The
> sequence of digits which we represent by pi satisfies this definition.

You have just proven (partially) that Pi is not random. Given a sequence
of numbers taken from Pi, one may observe that they are taken from Pi and
thus generate the next number.

Of course, my argument depends on the fact that generating the more
significant digits of Pi is easier than the less significant, and that at
the present we are unable to generate an arbitrary subsequence of digits
of Pi.

One way to look at it, Pi digits (as far as we know now) are random but we
are unable to truly benefit from this randomness because computers have
sequence. Does this make any sense?

> Whilst proving randomness is impossible and measuring randomness is an area
> of debate; randomness is already precisely defined, thus:
> A sequence of numbers is random if no member can be predicted from the
> preceding elements.
>
> Whilst Kolmogorov Complexity is *a* (rather good) definition of randomness,
> which plays a central role in algorithmic information theory, it is by no
> means universally accepted as *the* definition of randomness.

Actually, Martin's definition seems to be the most known, intuitive, and
undebatable definition. I just want to add that statistical measures give
us the distribution of the numbers, which is not the same as randomness. A
particular true random sequence may have the same number repeating for 100
times and then never occurring again in finite sequence.

The quality of a sequence and it's suitability for a particular
application should not be confused with randomness.

Consider this example. Let's say we have a statistical measure for the
randomness of a finite sequence. We can hand craft a sequence that passes
the measure. Our sequence is not random because in crafting it each number
depended on the previous one. Pseudo random number generators are our
attempt to find the solution that a such a measure is looking for. (for
this example to work, the length of the sequence needs to be sufficiently
large with respect to the largest allowable number).

Regards,

TAA

----------------------------------------------------------
Tony Abou-Assaleh
Graduate Student, Department of Computer Science
University of Waterloo, Waterloo, ON, Canada, N2L 3G1
Office: DC2503
Voice: (519) 888-4567 Ext. 3399
Fax: (519) 885-1208
Email: taa@...
-------------------------[THE END]------------------------
• [Repost of a message I sent 24 hours ago which never got through.] ... It is a problem if a method used to measure the randomness of a sequence of numbers
Message 3 of 20 , Mar 26 4:57 PM
• 0 Attachment
[Repost of a message I sent 24 hours ago which never got through.]

Martin Sewell wrote:
> > The problem with using Kolmogorov Complexity as a measurement of
> randomness
> > is that it implies that the sequence of numbers represented by pi (which
> > has never failed a frequency based statistical test for randomness) aren't
> > random.

At 10:23 26/03/2002 +1200, Mariusz Nowostawski wrote:
>So? What is "the problem"?

It is a problem if a method used to measure the "randomness" of a sequence
of numbers judges a sequence of numbers which intuitively look as though
they were generated by a random process as non random.

>Maybe pure "frequency based statistical tests" are not the whole picture here.

There are various methods of measuring "randomness" in this sense, but
there is nothing *but* statistics in the real world.

>If you create a class of all "random" sequences based on "frequency based
>statistical tests", the Kolmogorov-random sequences will be a subset of
>it, in a sense.

Okay.

>The remaining difference will be precisely discriminated by the Kolmogorov
>measure -- unlike "frequency based statistical tests" which cannot
>discriminate it for you.

Nonsense.

>For pi it simply means "even though the frequency based statistical tests
>show that the sequence has some properties typical to random sequences, it
>is really as random as the length of the program outputing it".

More usefully, "there are cases where this test for randomness is quite
unsatisfactory and intuitively wrong."

>Pi is not as random as "real world", and it does not need "real world" to
>produce it (following a good example with "real world" as a source of
>randomness given by someone earlier).

I assume that by "real world" you mean "generated by a truly random
process, such as radioactive decay", in which case, what evidence do you
have to support your above statement?

Using approximate entropy to define "randomness", Pincus and Kalman (1997)
found that pi was the most random number they tested.

> > It would also show the sequence of numbers produced by pseudo-random
> number
> > generators as being far from random.
>
>No, it would qualitatively and precisely show how random a given random
>sequence is. For true random sequences Kolmogorov measure is equal the
>length of that sequence (plus a constant).
>Good (algorithmic) random number generators will be as good as they can;
>and without a doubt, (good) bigger will be better than smaller. And the
>ones which use "real world" as a source of randomness will outperform pure
>algorithmic ones.

The whole point of an efficient, clever, pseudo-random number generator is
that the code is kept as small as possible, so it's not a very useful
measure here either.

Regards

Martin
• ... sequence ... Is pi generated by random process or equivalent to random process? Kolmogorov measure is simply saying it is not, and to me it is quite fair
Message 4 of 20 , Mar 26 7:48 PM
• 0 Attachment
Martin Sewell wrote:

>> What is "the problem"?
> It is a problem if a method used to measure the "randomness" of a
sequence
> of numbers judges a sequence of numbers which intuitively look as though
> they were generated by a random process as non random.

Is pi generated by random process or equivalent to random process?
Kolmogorov measure is simply saying it is not, and to me it is quite
fair verdict.

>>The remaining difference will be precisely discriminated by the
Kolmogorov
>>measure -- unlike "frequency based statistical tests" which cannot
>>discriminate it for you.
>
> Nonsense.

Right, badly formulated, my fault. I wanted to point out that we're
dealing with two different "things" here, which cannot be compared
with each other directly. Statistics will tell you that any sequence of
6 numbers from a Lotto draw (eg. 6 out of 49) is equally random.
Kolmogorov complexity will tell you though, that some sequences are more
random than others (because some can be obtained by simpler processes
than the others).

>>Pi is not as random as "real world", and it does not need "real
world" to
>>produce it (following a good example with "real world" as a source of
>>randomness given by someone earlier)
>
> I assume that by "real world" you mean "generated by a truly random
> process, such as radioactive decay", in which case, what evidence do you
> have to support your above statement?

I do not know what "truly random process" is, but I have the 27 lines of
C code generating pi, and I am sure the model calculating the
radioactive decay would be much longer than 27 lines.

> Using approximate entropy to define "randomness", Pincus and Kalman
(1997)
> found that pi was the most random number they tested.

As random as e.g. any binary number obtained by tossing a fair 0/1 coin?
How long expansion they have taken into account?

best regards
Mariusz
• ... If by model calculating the radioactive decay you mean an algorithm for predicting the timing of radioactive decay (and not just probabilistically), then
Message 5 of 20 , Mar 26 9:42 PM
• 0 Attachment
At 3:48 PM +1200 3/27/02, Mariusz Nowostawski wrote:
>> I assume that by "real world" you mean "generated by a truly random
>> process, such as radioactive decay", in which case, what evidence do you
>> have to support your above statement?
>
>I do not know what "truly random process" is, but I have the 27 lines of
>C code generating pi, and I am sure the model calculating the
>radioactive decay would be much longer than 27 lines.

If by "model calculating the radioactive decay" you mean an algorithm for
predicting the timing of radioactive decay (and not just
probabilistically), then there is NO such model of any size (barring a
fundamental revolution in the foundations of quantum mechanics).

-Lee
--
Lee Spector
Associate Professor of Computer Science lspector@...
Cognitive Science, Hampshire College http://hampshire.edu/lspector/
Amherst, MA 01002 413-559-5352, Fax: 413-559-5438
• ... Exactly this was my point. Kolmogorov complexity tells us that: pi and any number generated from (for example) radioactive decay belong to two different
Message 6 of 20 , Mar 26 10:49 PM
• 0 Attachment
>>>I assume that by "real world" you mean "generated by a truly random
>>>process, such as radioactive decay", in which case, what evidence do you
>>>have to support your above statement?
>>>
>>I do not know what "truly random process" is, but I have the 27 lines of
>>C code generating pi, and I am sure the model calculating the
>>radioactive decay would be much longer than 27 lines
>
> If by "model calculating the radioactive decay" you mean an algorithm for
> predicting the timing of radioactive decay (and not just
> probabilistically), then there is NO such model of any size (barring a
> fundamental revolution in the foundations of quantum mechanics).

Exactly this was my point. Kolmogorov complexity tells us that: pi and
any number generated from (for example) radioactive decay belong to two
different classes of randomness. Martin Sewell said these are same
classes -- pi and radioactive decay-based sequence are in the same type
of randomness. And this was "the problem", because Kolmogorov complexity
puts it into two very different classes.

I intuitively understand it that "truly random process" producing random
sequence S cannot be compressed to a simpler process producing same
random sequence S. That's all. Radioactive decay cannot be modelled by
small algorithm predicting the sequence, pi can.

best regards
Mariusz
• ... Humm .. it makes me wonder how to apply Kolmogorov complexity in the context of quantum computation. In principle, classical computers are quantum
Message 7 of 20 , Mar 26 11:50 PM
• 0 Attachment
> I intuitively understand it that "truly random process" producing random
> sequence S cannot be compressed to a simpler process producing same
> random sequence S. That's all. Radioactive decay cannot be modelled by
> small algorithm predicting the sequence, pi can.

Humm .. it makes me wonder how to apply Kolmogorov complexity in the
context of quantum computation. In principle, classical computers are
quantum computers that operate using only the pure states of |0> and |1>.
And considering that we can already do 7 qbit quantum computations, we can
write very simple algorithms to produce what we currently consider to be a
truly random sequence:

|0> ---[H]---> |0>+|1> -----|| (measure)

[In English: take a 0 qbit, apply the Hadamard transform to get 0+1, and
then measure it.] Repeat the process for more digits.

Our measurement will randomly return a 0 or 1 with probability of %50
each. My circuit is only one line long. Any insight on how to measure
randomness in this case? And how would it compare to Pi digits generated
by a quantum computer? [Note: we know how to implement any classical gate
using quantum gates, the problem is scaling up to more than 7 bits]

TAA

----------------------------------------------------------
Tony Abou-Assaleh
Graduate Student, Department of Computer Science
University of Waterloo, Waterloo, ON, Canada, N2L 3G1
Office: DC2503
Voice: (519) 888-4567 Ext. 3399
Fax: (519) 885-1208
Email: taa@...
-------------------------[THE END]------------------------
• ... this algorithm does not generate the random sequence since the actual numbers depends on the measurement (or the underlying process, wich is actualy
Message 8 of 20 , Mar 27 2:32 AM
• 0 Attachment
> And considering that we can already do 7 qbit quantum computations, we can
> write very simple algorithms to produce what we currently consider to be a
> truly random sequence:
>
> |0> ---[H]---> |0>+|1> -----|| (measure)
>
> [In English: take a 0 qbit, apply the Hadamard transform to get 0+1, and
> then measure it.] Repeat the process for more digits.
>

this algorithm does not "generate" the random sequence since the actual
numbers depends on the measurement (or the underlying process, wich is
actualy non-algorithmic, as Bell Theorem proves).
so it's a big difference, as pi _can_ be generated by an algorithm.

The problem here could be formuled this way "Does this Kolmogorov separation
between pi and the quantum sequence has any significant effect when using
with an AI algorithm?".
There is also the posibility about those truly random quantum sequences ->
although it is proved that they can't be generated by _any_ algorithm, they
could be solutions to deterministic equations (it is mathematicaly
possible). If so, wouldn't be intuitivly correct that this fact, or that
equation itself can be very important when we use the numbers to AI?
If this is true, it's clear that the Kolmogorov definition of randomness
it's not enough for AI and those non-algorithmic-but-deterministic equations
should be studied. Of course, these are all asumptions :) but the
possibility exists and, from my knowledge it's not been proven either case.

regards,
calin.
• A little plug: I m giving a introductory-level tutorial on quantum computing at GECCO-2002 this summer; anyone who s interested in this stuff (and registered
Message 9 of 20 , Mar 27 7:15 AM
• 0 Attachment
A little plug: I'm giving a introductory-level tutorial on quantum
computing at GECCO-2002 this summer; anyone who's interested in this stuff
(and registered for the conference!) is welcome to attend. (Though I don't
think I'll have much to say about random number generation or quantum
Kolmogorov complexity... The focus will be on introducing the concepts and
formal theory of quantum computing, along with a description of how to use
evolutionary computation to search for new quantum algorithms.)

-Lee

>> And considering that we can already do 7 qbit quantum computations, we can
>> write very simple algorithms to produce what we currently consider to be a
>> truly random sequence:
>>
>> |0> ---[H]---> |0>+|1> -----|| (measure)
>>
>> [In English: take a 0 qbit, apply the Hadamard transform to get 0+1, and
>> then measure it.] Repeat the process for more digits.
>>
>
>this algorithm does not "generate" the random sequence since the actual
>numbers depends on the measurement (or the underlying process, wich is
>actualy non-algorithmic, as Bell Theorem proves).
>so it's a big difference, as pi _can_ be generated by an algorithm.
>
>The problem here could be formuled this way "Does this Kolmogorov separation
>between pi and the quantum sequence has any significant effect when using
>with an AI algorithm?".
>There is also the posibility about those truly random quantum sequences ->
>although it is proved that they can't be generated by _any_ algorithm, they
>could be solutions to deterministic equations (it is mathematicaly
>possible). If so, wouldn't be intuitivly correct that this fact, or that
>equation itself can be very important when we use the numbers to AI?
>If this is true, it's clear that the Kolmogorov definition of randomness
>it's not enough for AI and those non-algorithmic-but-deterministic equations
>should be studied. Of course, these are all asumptions :) but the
>possibility exists and, from my knowledge it's not been proven either case.
>
>regards,
> calin.
>
>
>
--
Lee Spector
Associate Professor of Computer Science lspector@...
Cognitive Science, Hampshire College http://hampshire.edu/lspector/
Amherst, MA 01002 413-559-5352, Fax: 413-559-5438
• ... No, I ve not. ... No, you can t; the sequence of numbers are equally likely to have been taken from any normal number. ... Yes we are, see Bailey, Borwein
Message 10 of 20 , Mar 27 8:22 AM
• 0 Attachment
At 14:10 26/03/2002 -0500, Tony Abou-Assaleh wrote:
> > To assert that "pi is not random" is meaningless.
> >
> > Random numbers are a sequence of numbers with the property that no member
> > can be predicted from the preceding elements; in particular these cannot
> > form a progression or follow any regular or repetitive pattern. The
> > sequence of digits which we represent by pi satisfies this definition.
>
>You have just proven (partially) that Pi is not random.

No, I've not.

>Given a sequence of numbers taken from Pi, one may observe that they are
>taken from Pi and
>thus generate the next number.

No, you can't; the sequence of numbers are equally likely to have been
taken from any normal number.

>Of course, my argument depends on the fact that generating the more
>significant digits of Pi is easier than the less significant, and that at
>the present we are unable to generate an arbitrary subsequence of digits
>of Pi.

Yes we are, see Bailey, Borwein & Plouffe (1996).

>One way to look at it, Pi digits (as far as we know now) are random but we
>are unable to truly benefit from this randomness because computers have
>sequence. Does this make any sense?

pseudo-random number generator, but there are simpler and faster algorithms.

> > Whilst proving randomness is impossible and measuring randomness is an area
> > of debate; randomness is already precisely defined, thus:
> > A sequence of numbers is random if no member can be predicted from the
> > preceding elements.
> >
> > Whilst Kolmogorov Complexity is *a* (rather good) definition of randomness,
> > which plays a central role in algorithmic information theory, it is by no
> > means universally accepted as *the* definition of randomness.
>
>Actually, Martin's definition seems to be the most known, intuitive, and
>undebatable definition. I just want to add that statistical measures give
>us the distribution of the numbers, which is not the same as randomness.

A necessary condition for an infinite sequence to be considered random is
that the number which gives rise to the decimal expansion is
normal. Statistical (distribution) measures are necessary, but not
sufficient, for randomness.

>A particular true random sequence may have the same number repeating for
>100 times and then never occurring again in finite sequence.

True, but this is not the case for an infinite sequence.

>The quality of a sequence and it's suitability for a particular
>application should not be confused with randomness.

True, unless "randomness" is the quality which you're looking for.

>[...]

Regards

Martin
• ... I didn t say that the were in the same class : pi is calculable and probably normal (unproven) and the decimal expansion is probably random (unproven).
Message 11 of 20 , Mar 27 9:09 AM
• 0 Attachment
At 18:49 27/03/2002 +1200, Mariusz Nowostawski wrote:

>Exactly this was my point. Kolmogorov complexity tells us that: pi and any
>number generated from (for example) radioactive decay belong to two
>different classes of randomness. Martin Sewell said these are same classes
>-- pi and radioactive decay-based sequence are in the same type of
>randomness. And this was "the problem", because Kolmogorov complexity puts
>it into two very different classes.

I didn't say that the were in the "same class":
pi is calculable and probably normal (unproven) and the decimal expansion
is probably random (unproven).
Radioactive decay is a truly random process.

>I intuitively understand it that "truly random process" producing random
>sequence S cannot be compressed to a simpler process producing same random
>sequence S. That's all. Radioactive decay cannot be modelled by small
>algorithm predicting the sequence, pi can.

The expression "truly random" generally refers to the real
world. Everything in the universe except radioactive decay and some
quantum effects is deterministic. The tossing of a coin is purely
deterministic, but apparently random; therefore "random" rather than "truly
random".

Cheers

Martin

PS Cartoon: http://www.cs.ucl.ac.uk/staff/M.Sewell/random.gif
• ... How is it so? Let s say we have a very dump Pi-adversary that only tries to guess the next number the program will use by looking at Pi digits. Given that
Message 12 of 20 , Mar 27 10:03 AM
• 0 Attachment
> >Given a sequence of numbers taken from Pi, one may observe that they are
> >taken from Pi and
> >thus generate the next number.
>
> No, you can't; the sequence of numbers are equally likely to have been
> taken from any normal number.

How is it so? Let's say we have a very dump Pi-adversary that only tries
to guess the next number the program will use by looking at Pi digits.
Given that the program have finite resources, it can use only a finite
subsequence of Pi digits. With enough (finite) resources, our dump
Pi-adversary can correctly predict the next number after looking at a
sufficiently large sequence of outputs. This Pi-adversary might fail
(unproven yet, but very likely) with any other source of pseudo random
number generator. But in this particular case, the output would appear
completely predictable.

> >Of course, my argument depends on the fact that generating the more
> >significant digits of Pi is easier than the less significant, and that at
> >the present we are unable to generate an arbitrary subsequence of digits
> >of Pi.
>
> Yes we are, see Bailey, Borwein & Plouffe (1996).

Thanks for the reference Martin! But this doesn't change my argument,
from the abstract of the paper:

"... feature run times that scale nearly linearly with the order of the
digit desired."

This implies that with finite resources, you can use only a subset of a
finite subsequence of digits that starts at the first digit! You cannot
start from an n-th digits if n is very large (arguably beyond practical
uses, but we don't have human level AI yet, so maybe still of practical
use).

Cheers,

TAA

----------------------------------------------------------
Tony Abou-Assaleh
Graduate Student, Department of Computer Science
University of Waterloo, Waterloo, ON, Canada, N2L 3G1
Office: DC2503
Voice: (519) 888-4567 Ext. 3399
Fax: (519) 885-1208
Email: taa@...
-------------------------[THE END]------------------------
• Well, I hate to discourage activity on the GP list, but there have been a large number of messages in this thread over the past few days, a number of which
Message 13 of 20 , Mar 27 10:24 AM
• 0 Attachment
Well, I hate to discourage activity on the GP list, but there have
been a large number of messages in this thread over the past few days,
a number of which have very little to do with GP. While any
discussion of the suitability of different RNGs for GP or evolutionary
computation in general or the theory behind this would certainly be
welcome, I would encourage people who are interested in discussing
the abstract mathematical, physical, or philosophical aspects of
randomness to either email each other personally or to take this
discussion to another forum. Thank you.

Matt Streeter
• ... I disagree and would like to see this discussion (and others like it that may wander a bit from core GP topics) continue on the GP list. For one thing the
Message 14 of 20 , Mar 27 4:55 PM
• 0 Attachment
At 6:24 PM +0000 3/27/02, Matt Streeter wrote:
>Well, I hate to discourage activity on the GP list, but there have
>been a large number of messages in this thread over the past few days,
>a number of which have very little to do with GP. While any
>discussion of the suitability of different RNGs for GP or evolutionary
>computation in general or the theory behind this would certainly be
>welcome, I would encourage people who are interested in discussing
>the abstract mathematical, physical, or philosophical aspects of
>randomness to either email each other personally or to take this
>discussion to another forum. Thank you.

I disagree and would like to see this discussion (and others like it that
may wander a bit from core GP topics) continue on the GP list. For one
thing the present thread hasn't even wandered particularly far. GP is a
stochastic algorithm and properties of underlying random number generators
may impact performance -- at least it is a question that has been discussed
in the literature (e.g. Meysenburg and Foster GECCO-1999, something I seem
to remember by Daida but can't find at the moment, etc.). It could
conceivably do the field some good for more of us to understand more about
mathematical concepts of randomness. In addition several of the tangents in
this discussion (quantum computing, Kolmogorov complexity) are of
independent interest in conjunction with EC/GP, as witnessed by recent
GECCO/CEC/etc papers, sessions, and tutorials. Even when there's no obvious
connection to GP I hope we will err on the side of open, creative
discussion in-and-around our research topics. It is much easier for people
to delete run-away threads than it is to encourage vibrant research
discussions while simultaneously shushing people for straying.

>Everything in the universe except radioactive decay and some
>quantum effects is deterministic.

Everything in the universe is deterministic except for things built out of
quantum mechanical materials... in other words except for everything! Yes,
most macroscopic systems are nearly deterministic, but even this isn't true
of systems carefully constructed to amplify quantum phenomena (like Geiger
counters and quantum computers). Quantum systems actually provide something
more valuable than non-determinism -- entanglement -- and there are still
many open questions about what GP-on-a-QC might be able to do and about
what role quantum effects might have in biological evolution or even in
cognition (though I share the majority-view skepticism on these last two).

-Lee
--
Lee Spector
Associate Professor of Computer Science lspector@...
Cognitive Science, Hampshire College http://hampshire.edu/lspector/
Amherst, MA 01002 413-559-5352, Fax: 413-559-5438
• Obviously there is disagreement about the extent to which this thread has wandered from topics of immediate relevance to GP. I am not going to prohibit anyone
Message 15 of 20 , Mar 27 6:06 PM
• 0 Attachment
Obviously there is disagreement about the extent to
which this thread has wandered from topics of
immediate relevance to GP. I am not going to prohibit
anyone from posting additional messages in this
thread, or on whatever topics might emerge from it,
but I do think there are people on this list who will
appreciate it if we keep in who the audience for these
posts is, and the range of topics that are of likely
interest to them as opposed to scientists as a whole.

So in summary: go for it.

Matt

--- Lee Spector <lspector@...> wrote:
> At 6:24 PM +0000 3/27/02, Matt Streeter wrote:
> >Well, I hate to discourage activity on the GP list,
> but there have
> >been a large number of messages in this thread over
> the past few days,
> >a number of which have very little to do with GP.
> While any
> >discussion of the suitability of different RNGs for
> GP or evolutionary
> >computation in general or the theory behind this
> would certainly be
> >welcome, I would encourage people who are
> interested in discussing
> >the abstract mathematical, physical, or
> philosophical aspects of
> >randomness to either email each other personally or
> to take this
> >discussion to another forum. Thank you.
>
> I disagree and would like to see this discussion
> (and others like it that
> may wander a bit from core GP topics) continue on
> the GP list. For one
> thing the present thread hasn't even wandered
> particularly far. GP is a
> stochastic algorithm and properties of underlying
> random number generators
> may impact performance -- at least it is a question
> that has been discussed
> in the literature (e.g. Meysenburg and Foster
> GECCO-1999, something I seem
> to remember by Daida but can't find at the moment,
> etc.). It could
> conceivably do the field some good for more of us to
> mathematical concepts of randomness. In addition
> several of the tangents in
> this discussion (quantum computing, Kolmogorov
> complexity) are of
> independent interest in conjunction with EC/GP, as
> witnessed by recent
> GECCO/CEC/etc papers, sessions, and tutorials. Even
> when there's no obvious
> connection to GP I hope we will err on the side of
> open, creative
> discussion in-and-around our research topics. It is
> much easier for people
> to delete run-away threads than it is to encourage
> vibrant research
> discussions while simultaneously shushing people for
> straying.
>
> Back to the thread itself:
> >Everything in the universe except radioactive decay
> and some
> >quantum effects is deterministic.
>
> Everything in the universe is deterministic except
> for things built out of
> quantum mechanical materials... in other words
> except for everything! Yes,
> most macroscopic systems are nearly deterministic,
> but even this isn't true
> of systems carefully constructed to amplify quantum
> phenomena (like Geiger
> counters and quantum computers). Quantum systems
> actually provide something
> more valuable than non-determinism -- entanglement
> -- and there are still
> many open questions about what GP-on-a-QC might be
> able to do and about
> what role quantum effects might have in biological
> evolution or even in
> cognition (though I share the majority-view
> skepticism on these last two).
>
> -Lee
> --
> Lee Spector
> Associate Professor of Computer Science
> lspector@...
> Cognitive Science, Hampshire College
> http://hampshire.edu/lspector/
> Amherst, MA 01002
> 413-559-5352, Fax: 413-559-5438
>

__________________________________________________
Do You Yahoo!?
Yahoo! Movies - coverage of the 74th Academy Awards�
http://movies.yahoo.com/
• Thanks, and well said Lee. I totally agree with you. Being interested in such a fundamental scientific issue is really what distinguishes a scientist. It is
Message 16 of 20 , Mar 27 9:42 PM
• 0 Attachment
Thanks, and well said Lee. I totally agree with you.

Being interested in such a fundamental scientific issue is really what
distinguishes a scientist. It is actually rather encouraging to find such
constructive scientific dialogue continue for a few days to discuss one
matter. There is so much more to this issue that remains untouched.

For those uninterested in what is discusses, discard the email. The topic
is known from the 'subject' line.

Mak

At 07:55 PM 3/27/2002 -0500, Lee Spector wrote:
>At 6:24 PM +0000 3/27/02, Matt Streeter wrote:
>>Well, I hate to discourage activity on the GP list, but there have
>>been a large number of messages in this thread over the past few days,
>>a number of which have very little to do with GP. While any
>>discussion of the suitability of different RNGs for GP or evolutionary
>>computation in general or the theory behind this would certainly be
>>welcome, I would encourage people who are interested in discussing
>>the abstract mathematical, physical, or philosophical aspects of
>>randomness to either email each other personally or to take this
>>discussion to another forum. Thank you.
>
>I disagree and would like to see this discussion (and others like it that
>may wander a bit from core GP topics) continue on the GP list. For one
>thing the present thread hasn't even wandered particularly far. GP is a
>stochastic algorithm and properties of underlying random number generators
>may impact performance -- at least it is a question that has been discussed
>in the literature (e.g. Meysenburg and Foster GECCO-1999, something I seem
>to remember by Daida but can't find at the moment, etc.). It could
>conceivably do the field some good for more of us to understand more about
>mathematical concepts of randomness. In addition several of the tangents in
>this discussion (quantum computing, Kolmogorov complexity) are of
>independent interest in conjunction with EC/GP, as witnessed by recent
>GECCO/CEC/etc papers, sessions, and tutorials. Even when there's no obvious
>connection to GP I hope we will err on the side of open, creative
>discussion in-and-around our research topics. It is much easier for people
>to delete run-away threads than it is to encourage vibrant research
>discussions while simultaneously shushing people for straying.
>
>>Everything in the universe except radioactive decay and some
>>quantum effects is deterministic.
>
>Everything in the universe is deterministic except for things built out of
>quantum mechanical materials... in other words except for everything! Yes,
>most macroscopic systems are nearly deterministic, but even this isn't true
>of systems carefully constructed to amplify quantum phenomena (like Geiger
>counters and quantum computers). Quantum systems actually provide something
>more valuable than non-determinism -- entanglement -- and there are still
>many open questions about what GP-on-a-QC might be able to do and about
>what role quantum effects might have in biological evolution or even in
>cognition (though I share the majority-view skepticism on these last two).
>
> -Lee
>--
>Lee Spector
>Associate Professor of Computer Science lspector@...
>Cognitive Science, Hampshire College http://hampshire.edu/lspector/
>Amherst, MA 01002 413-559-5352, Fax: 413-559-5438
>
>
>To unsubscribe from this group, send an email to:
>genetic_programming-unsubscribe@yahoogroups.com
>
>
>
>Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
• Several people have said that radioactive decay is truly random. I guess what they mean is that the theory of radioactive decay is that it is truly random,
Message 17 of 20 , Mar 28 12:46 AM
• 0 Attachment
Several people have said that radioactive decay is "truly" random. I guess
what they mean is that the theory of radioactive decay is that it is truly
random, and that so far the real world fits the model quite well.

In other words, we can't look to radioactive decay as a natural example of
true randomness because when we do so we are in fact only looking at our

Radioactive decay is not a holy grail - it is a red herring. Looking for
natural sources of randomness is a wild goose chase! :-)

--
Norman Paterson, University of St Andrews LetsGoTrekking with John Peel!
http://www.dcs.st-and.ac.uk/~norman/
• Most of what I know about radioactive decays came from the discussion on this list. But on the quantum side, preparing (independent) N qbits in the state
Message 18 of 20 , Mar 28 1:04 AM
• 0 Attachment
Most of what I know about radioactive decays came from the discussion on
this list. But on the quantum side, preparing (independent) N qbits in the
state |0>+|1> and measuring the qbit will give you 0 with probability %50
and 1 with probability %50 for each qbit independently.

One may argue in principle that the whole world is a single entangled
system. Experimentally, we are able to isolate qbits so that their
interaction with the surroundings is insignificant.

As a general note, quantum computing can be counter intuitive in some
cases. A moderate understanding of the basics is needed to grasp any
related discussion. I say this from personal experience. I can give
pointers and references privately to interested persons.

Cheers,

TAA

----------------------------------------------------------
Tony Abou-Assaleh
Graduate Student, Department of Computer Science
University of Waterloo, Waterloo, ON, Canada, N2L 3G1
Office: DC2503
Voice: (519) 888-4567 Ext. 3399
Fax: (519) 885-1208
Email: taa@...
-------------------------[THE END]------------------------

On Thu, 28 Mar 2002, Norman Paterson wrote:

> Several people have said that radioactive decay is "truly" random. I guess
> what they mean is that the theory of radioactive decay is that it is truly
> random, and that so far the real world fits the model quite well.
>
> In other words, we can't look to radioactive decay as a natural example of
> true randomness because when we do so we are in fact only looking at our
> mathematical model of radioactive decay.
>
> Radioactive decay is not a holy grail - it is a red herring. Looking for
> natural sources of randomness is a wild goose chase! :-)
>
> --
> Norman Paterson, University of St Andrews LetsGoTrekking with John Peel!
> http://www.dcs.st-and.ac.uk/~norman/
>
>
>
>
> To unsubscribe from this group, send an email to:
> genetic_programming-unsubscribe@yahoogroups.com
>
>
>
> Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
>
>
>
• ... To confuse things even more: If I am not mistaken, radioactivity decreases over time (period of the radio-element). So is it really *truly* random ? :-)))
Message 19 of 20 , Mar 28 1:19 AM
• 0 Attachment
> From: Norman Paterson [mailto:norman@...-and.ac.uk]
>
> Several people have said that radioactive decay is "truly"
> random. I guess
> what they mean is that the theory of radioactive decay is that it is truly
> random, and that so far the real world fits the model quite well.

To confuse things even more:
If I am not mistaken, radioactivity decreases over time (period of the

So is it really *truly* random ? :-)))

my 2 eurocents,

Pierre COLLET
• ... truly ... Radio-activity decreasing over time == not random? Random (as far as physicists know), but not uniform. The distribution is exponential (assuming
Message 20 of 20 , Mar 29 8:24 PM
• 0 Attachment
> > From: Norman Paterson [mailto:norman@...-and.ac.uk]
> >
> > Several people have said that radioactive decay is "truly"
> > random. I guess
> > what they mean is that the theory of radioactive decay is that it is
truly
> > random, and that so far the real world fits the model quite well.
>
> To confuse things even more:
> If I am not mistaken, radioactivity decreases over time (period of the
>
> So is it really *truly* random ? :-)))
>
> my 2 eurocents,
>
> Pierre COLLET

Radio-activity decreasing over time == not random?

Random (as far as physicists know), but not uniform. The distribution
is exponential (assuming a large number of unstable nuclei), or step-wise
uniform for smaller numbers of nuclei (ie, the probability proportional
to period and number of nuclei).

[Random is still "with respect to" a distribution/process. Of course,
you can have philosophical speculations which go beyond this,
and have random selection of processes, etc. That evades the
issue. Random == prediction about next (and subsequent) events
is not better than chance due to no information, eg, given an
average rate if available. Chaotic == prediction about subsequent
events becomes closer to chance, over time, due to
disappearance of significant information].

Physicists assume a random decay process (given by a probability
in a time T interval of lambda*T) for a single nucleus (hence half-lives,
etc). [NB: The rate, lambda, can be increased by bombardment by
neutrons - depending on nucleus - and other particles, which change
the nucleus into something more unstable. Hence chain reactions].

Some psychic researchers claim they can influence the rate, which goes to
show that some people will believe just about anything.

--

An alternative "random" sequence for the pragmatists out there: Take some
financial time-series (eg, USD-AUD) and build a suite of predictor models.
Combine (bag) the models. Keep the residuals of the bagged models (as
the pragmatically random sequence), as your predictions pulled out as
much information (as your skill would allow).

Tom.
Your message has been successfully submitted and would be delivered to recipients shortly.