Genetic Programming is a Public Group with 2093 members.
 Genetic Programming

 Public Group,
 2093 members
Primary Navigation
Randomness (was: AI)
Expand Messages
 0 Attachment
On Mon, 25 Mar 2002, Martin Sewell wrote:> > The problem with using Kolmogorov Complexity as a measurement of randomness
At 13:28 26/03/2002 +0000, Peter Ross wrote:
> > 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.
>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
Whilst proving randomness is impossible and measuring randomness is an area
>reasonable definition we have for what it means for a sequence to be random.
>[...]
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 0 Attachment
> To assert that "pi is not random" is meaningless.
You have just proven (partially) that Pi is not random. Given a sequence
>
> 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.
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
access to only a finite nonrandom subsequence of the infinite random
sequence. Does this make any sense?
> Whilst proving randomness is impossible and measuring randomness is an area
Actually, Martin's definition seems to be the most known, intuitive, and
> 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.
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 AbouAssaleh
Graduate Student, Department of Computer Science
University of Waterloo, Waterloo, ON, Canada, N2L 3G1
Office: DC2503
Voice: (519) 8884567 Ext. 3399
Fax: (519) 8851208
Email: taa@...
[THE END] 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
At 10:23 26/03/2002 +1200, Mariusz Nowostawski wrote:
> 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.
>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
Okay.
>statistical tests", the Kolmogorovrandom sequences will be a subset of
>it, in a sense.
>The remaining difference will be precisely discriminated by the Kolmogorov
Nonsense.
>measure  unlike "frequency based statistical tests" which cannot
>discriminate it for you.
>For pi it simply means "even though the frequency based statistical tests
More usefully, "there are cases where this test for randomness is quite
>show that the sequence has some properties typical to random sequences, it
>is really as random as the length of the program outputing it".
unsatisfactory and intuitively wrong."
>Pi is not as random as "real world", and it does not need "real world" to
I assume that by "real world" you mean "generated by a truly random
>produce it (following a good example with "real world" as a source of
>randomness given by someone earlier).
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 pseudorandom
The whole point of an efficient, clever, pseudorandom number generator is
> 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.
that the code is kept as small as possible, so it's not a very useful
measure here either.
Regards
Martin 0 Attachment
Martin Sewell wrote:
>> What is "the problem"?
sequence
> It is a problem if a method used to measure the "randomness" of a
> of numbers judges a sequence of numbers which intuitively look as though
Is pi generated by random process or equivalent to random process?
> they were generated by a random process as non random.
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
Right, badly formulated, my fault. I wanted to point out that we're
>>discriminate it for you.
>
> Nonsense.
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
I do not know what "truly random process" is, but I have the 27 lines 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?
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 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
If by "model calculating the radioactive decay" you mean an algorithm for
>> 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.
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 4135595352, Fax: 4135595438 0 Attachment
>>>I assume that by "real world" you mean "generated by a truly random
Exactly this was my point. Kolmogorov complexity tells us that: pi and
>>>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).
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 decaybased 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 0 Attachment
> I intuitively understand it that "truly random process" producing random
Humm .. it makes me wonder how to apply Kolmogorov complexity in the
> 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.
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 AbouAssaleh
Graduate Student, Department of Computer Science
University of Waterloo, Waterloo, ON, Canada, N2L 3G1
Office: DC2503
Voice: (519) 8884567 Ext. 3399
Fax: (519) 8851208
Email: taa@...
[THE END] 0 Attachment
> And considering that we can already do 7 qbit quantum computations, we can
this algorithm does not "generate" the random sequence since the actual
> 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.
>
numbers depends on the measurement (or the underlying process, wich is
actualy nonalgorithmic, 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 nonalgorithmicbutdeterministic 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. 0 Attachment
A little plug: I'm giving a introductorylevel tutorial on quantum
computing at GECCO2002 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 nonalgorithmic, 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 nonalgorithmicbutdeterministic 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 4135595352, Fax: 4135595438 0 Attachment
At 14:10 26/03/2002 0500, Tony AbouAssaleh wrote:> > To assert that "pi is not random" is meaningless.
No, I've not.
> >
> > 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
No, you can't; the sequence of numbers are equally likely to have been
>taken from Pi and
>thus generate the next number.
taken from any normal number.
>Of course, my argument depends on the fact that generating the more
Yes we are, see Bailey, Borwein & Plouffe (1996).
>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
206,158,430,000 decimal digits isn't bad! (Kanada (1999)) Pi *is* a good
>are unable to truly benefit from this randomness because computers have
>access to only a finite nonrandom subsequence of the infinite random
>sequence. Does this make any sense?
pseudorandom number generator, but there are simpler and faster algorithms.
> > Whilst proving randomness is impossible and measuring randomness is an area
A necessary condition for an infinite sequence to be considered random is
> > 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.
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
True, but this is not the case for an infinite sequence.
>100 times and then never occurring again in finite sequence.
>The quality of a sequence and it's suitability for a particular
True, unless "randomness" is the quality which you're looking for.
>application should not be confused with randomness.
>[...]
Regards
Martin 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
I didn't say that the were in the "same class":
>number generated from (for example) radioactive decay belong to two
>different classes of randomness. Martin Sewell said these are same classes
> pi and radioactive decaybased sequence are in the same type of
>randomness. And this was "the problem", because Kolmogorov complexity puts
>it into two very different classes.
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
The expression "truly random" generally refers to the real
>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.
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 0 Attachment
> >Given a sequence of numbers taken from Pi, one may observe that they are
How is it so? Let's say we have a very dump Piadversary that only tries
> >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.
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
Piadversary can correctly predict the next number after looking at a
sufficiently large sequence of outputs. This Piadversary 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
Thanks for the reference Martin! But this doesn't change my argument,
> >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).
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 nth 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 AbouAssaleh
Graduate Student, Department of Computer Science
University of Waterloo, Waterloo, ON, Canada, N2L 3G1
Office: DC2503
Voice: (519) 8884567 Ext. 3399
Fax: (519) 8851208
Email: taa@...
[THE END] 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 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
I disagree and would like to see this discussion (and others like it that
>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.
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 GECCO1999, 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 inandaround our research topics. It is much easier for people
to delete runaway 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
Everything in the universe is deterministic except for things built out of
>quantum effects is deterministic.
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 nondeterminism  entanglement  and there are still
many open questions about what GPonaQC might be able to do and about
what role quantum effects might have in biological evolution or even in
cognition (though I share the majorityview 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 4135595352, Fax: 4135595438 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
> GECCO1999, 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 inandaround our research topics. It is
> much easier for people
> to delete runaway 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 nondeterminism  entanglement
>  and there are still
> many open questions about what GPonaQC might be
> able to do and about
> what role quantum effects might have in biological
> evolution or even in
> cognition (though I share the majorityview
> 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
> 4135595352, Fax: 4135595438
>
Do You Yahoo!?
Yahoo! Movies  coverage of the 74th Academy Awards�
http://movies.yahoo.com/ 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 GECCO1999, 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 inandaround our research topics. It is much easier for people
>to delete runaway 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 nondeterminism  entanglement  and there are still
>many open questions about what GPonaQC might be able to do and about
>what role quantum effects might have in biological evolution or even in
>cognition (though I share the majorityview 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 4135595352, Fax: 4135595438
>
>
>To unsubscribe from this group, send an email to:
>genetic_programmingunsubscribe@yahoogroups.com
>
>
>
>Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/ 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
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.stand.ac.uk/~norman/ 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 AbouAssaleh
Graduate Student, Department of Computer Science
University of Waterloo, Waterloo, ON, Canada, N2L 3G1
Office: DC2503
Voice: (519) 8884567 Ext. 3399
Fax: (519) 8851208
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.stand.ac.uk/~norman/
>
>
>
>
> To unsubscribe from this group, send an email to:
> genetic_programmingunsubscribe@yahoogroups.com
>
>
>
> Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
>
>
> 0 Attachment
> From: Norman Paterson [mailto:norman@...and.ac.uk]
To confuse things even more:
>
> 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.
If I am not mistaken, radioactivity decreases over time (period of the
radioelement).
So is it really *truly* random ? :)))
my 2 eurocents,
Pierre COLLET 0 Attachment
"Pierre COLLET" <Pierre.Collet@...> asked:> > From: Norman Paterson [mailto:norman@...and.ac.uk]
truly
> >
> > 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
> > random, and that so far the real world fits the model quite well.
Radioactivity decreasing over time == not random?
>
> To confuse things even more:
> If I am not mistaken, radioactivity decreases over time (period of the
> radioelement).
>
> So is it really *truly* random ? :)))
>
> my 2 eurocents,
>
> Pierre COLLET
Random (as far as physicists know), but not uniform. The distribution
is exponential (assuming a large number of unstable nuclei), or stepwise
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 halflives,
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 timeseries (eg, USDAUD) 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.