Loading ...
Sorry, an error occurred while loading the content.

Randomness (was: AI)

Expand Messages
  • Martin Sewell
    ... 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, 2002
    • 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
    • Tony Abou-Assaleh
      ... 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, 2002
      • 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
        access to only a finite non-random subsequence of the infinite random
        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]------------------------
      • Martin Sewell
        [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, 2002
        • 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
        • Mariusz Nowostawski
          ... 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, 2002
          • 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
          • Lee Spector
            ... 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, 2002
            • 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
            • Mariusz Nowostawski
              ... 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, 2002
              • 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
              • Tony Abou-Assaleh
                ... 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, 2002
                • 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]------------------------
                • Calin Ardelean
                  ... 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, 2002
                  • 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.
                  • Lee Spector
                    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, 2002
                    • 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
                    • Martin Sewell
                      ... 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, 2002
                      • 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
                        >access to only a finite non-random subsequence of the infinite random
                        >sequence. Does this make any sense?

                        206,158,430,000 decimal digits isn't bad! (Kanada (1999)) Pi *is* a good
                        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
                      • Martin Sewell
                        ... 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, 2002
                        • 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
                        • Tony Abou-Assaleh
                          ... 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, 2002
                          • 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]------------------------
                          • genetic_programming_list
                            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, 2002
                            • 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
                            • Lee Spector
                              ... 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, 2002
                              • 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.

                                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
                              • Genetic Programming
                                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, 2002
                                • 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
                                  > 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.
                                  >
                                  > 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/
                                • Kaboudan
                                  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, 2002
                                  • 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.
                                    >
                                    >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
                                    >
                                    >
                                    >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/
                                  • Norman Paterson
                                    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, 2002
                                    • 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.st-and.ac.uk/~norman/
                                    • Tony Abou-Assaleh
                                      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, 2002
                                      • 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/
                                        >
                                        >
                                        >
                                      • Pierre COLLET
                                        ... 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, 2002
                                        • 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
                                          radio-element).

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

                                          my 2 eurocents,

                                          Pierre COLLET
                                        • Tom Osborn
                                          ... 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, 2002
                                          • 0 Attachment
                                            "Pierre COLLET" <Pierre.Collet@...> asked:
                                            > > 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
                                            > radio-element).
                                            >
                                            > 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.