Re: Pi: Less Random Than We Thought
At 03:55 PM 5/6/05 -0400, Tyler Durden wrote: Yes, but only provided the universe lasts long enough for those digits to be computed! -TD Actually, a few years ago someone discovered an algorithm for the Nth (hex) digit of Pi which doesn't require computing all the previous digits. Mind blowing.
Re: Pi: Less Random Than We Thought
http://cypherpunks.venona.com/date/1993/05/msg00213.html Back in the old days, Tim May would occasionally talk about the Kolmogorov-Chaitin theories about randomness - Kolmogorov complexity gives you a lot of deep explanations about this sort of problem. Alas, I never actually *read* those papers, but there's been a lot of mathematical thought about what randomness means.
Re: Pi: Less Random Than We Thought
http://cypherpunks.venona.com/date/1993/05/msg00213.html Back in the old days, Tim May would occasionally talk about the Kolmogorov-Chaitin theories about randomness - Kolmogorov complexity gives you a lot of deep explanations about this sort of problem. Alas, I never actually *read* those papers, but there's been a lot of mathematical thought about what randomness means.
Re: Pi: Less Random Than We Thought
--- Tyler Durden [EMAIL PROTECTED] wrote: Let us remember, of course, that the digits of pi are not random whatsoever: they are the digits of pi! Random is in the eye of the beholder. -TD Exactly. What an algorithm gives out is always deterministic. We try to see if there is some structure that allows us to cryptanalyze it. Sarad. __ Do you Yahoo!? Yahoo! Mail - Helps protect you from nasty viruses. http://promotions.yahoo.com/new_mail
Re: Pi: Less Random Than We Thought
hi, --- Gil Hamilton [EMAIL PROTECTED] wrote: For example, is this sequence of bits random: 01100100010? How about this one: 00? From a true random number generator, both are completely possible and equally valid. Random as in the sense guessable and thus posing a problem to the cryptosystem. Sarad. Yahoo! Mail Stay connected, organized, and protected. Take the tour: http://tour.mail.yahoo.com/mailtour.html
Re: Pi: Less Random Than We Thought
From: Sarad AV [EMAIL PROTECTED] Sent: May 5, 2005 8:43 AM To: [EMAIL PROTECTED] Cc: [EMAIL PROTECTED] Subject: Re: Pi: Less Random Than We Thought Well, if it were generated by a random process, we'd expect to see every n-bit substring in there somewhere, sooner or later, since the sequence never ends or repeats. Thus, the wonderful joke/idea about selling advertising space in the binary expansion of pi. Not only will your message last forever, but it will be seen by any advanced civilization that develops math and computers, even ones in other galaxies. --John
Re: Pi: Less Random Than We Thought
Yes, but only provided the universe lasts long enough for those digits to be computed! -TD From: John Kelsey [EMAIL PROTECTED] To: Sarad AV [EMAIL PROTECTED], [EMAIL PROTECTED] CC: [EMAIL PROTECTED] Subject: Re: Pi: Less Random Than We Thought Date: Fri, 6 May 2005 09:42:09 -0400 (GMT-04:00) From: Sarad AV [EMAIL PROTECTED] Sent: May 5, 2005 8:43 AM To: [EMAIL PROTECTED] Cc: [EMAIL PROTECTED] Subject: Re: Pi: Less Random Than We Thought Well, if it were generated by a random process, we'd expect to see every n-bit substring in there somewhere, sooner or later, since the sequence never ends or repeats. Thus, the wonderful joke/idea about selling advertising space in the binary expansion of pi. Not only will your message last forever, but it will be seen by any advanced civilization that develops math and computers, even ones in other galaxies. --John
Re: Pi: Less Random Than We Thought
--- Tyler Durden [EMAIL PROTECTED] wrote: Let us remember, of course, that the digits of pi are not random whatsoever: they are the digits of pi! Random is in the eye of the beholder. -TD Exactly. What an algorithm gives out is always deterministic. We try to see if there is some structure that allows us to cryptanalyze it. Sarad. __ Do you Yahoo!? Yahoo! Mail - Helps protect you from nasty viruses. http://promotions.yahoo.com/new_mail
Re: Pi: Less Random Than We Thought
From: Sarad AV [EMAIL PROTECTED] Sent: May 5, 2005 8:43 AM To: [EMAIL PROTECTED] Cc: [EMAIL PROTECTED] Subject: Re: Pi: Less Random Than We Thought Well, if it were generated by a random process, we'd expect to see every n-bit substring in there somewhere, sooner or later, since the sequence never ends or repeats. Thus, the wonderful joke/idea about selling advertising space in the binary expansion of pi. Not only will your message last forever, but it will be seen by any advanced civilization that develops math and computers, even ones in other galaxies. --John
Re: Pi: Less Random Than We Thought
hi, --- Gil Hamilton [EMAIL PROTECTED] wrote: For example, is this sequence of bits random: 01100100010? How about this one: 00? From a true random number generator, both are completely possible and equally valid. Random as in the sense guessable and thus posing a problem to the cryptosystem. Sarad. Yahoo! Mail Stay connected, organized, and protected. Take the tour: http://tour.mail.yahoo.com/mailtour.html
Re: Pi: Less Random Than We Thought
Yes, but only provided the universe lasts long enough for those digits to be computed! -TD From: John Kelsey [EMAIL PROTECTED] To: Sarad AV [EMAIL PROTECTED], [EMAIL PROTECTED] CC: [EMAIL PROTECTED] Subject: Re: Pi: Less Random Than We Thought Date: Fri, 6 May 2005 09:42:09 -0400 (GMT-04:00) From: Sarad AV [EMAIL PROTECTED] Sent: May 5, 2005 8:43 AM To: [EMAIL PROTECTED] Cc: [EMAIL PROTECTED] Subject: Re: Pi: Less Random Than We Thought Well, if it were generated by a random process, we'd expect to see every n-bit substring in there somewhere, sooner or later, since the sequence never ends or repeats. Thus, the wonderful joke/idea about selling advertising space in the binary expansion of pi. Not only will your message last forever, but it will be seen by any advanced civilization that develops math and computers, even ones in other galaxies. --John
Re: Pi: Less Random Than We Thought
hi, If you remember D.E Knuth's book on Semi-Numerical Algorithms he shows some annoying subsequences of pi in it which are far from random. Sarad. --- cypherpunk [EMAIL PROTECTED] wrote: This doesn't really make sense. Either the digits are random or they are not. You can't be a little bit random. Well, you can be, but the point is that you either pass the test or you don't. If pi's digits fail a test of randomness in a statistically significant way, that is big news. If they pass it, then there is no meaningful way to compare them with another RNG that also passes. It's just a statistical quirk due to random variation as to which will do better than another on any given test. The bottom line is still that either an RNG passes the tests acceptably or it does not. From what they say (or don't say), pi does pass. It doesn't make sense to say that other RNGs do better. CP Yahoo! Mail Stay connected, organized, and protected. Take the tour: http://tour.mail.yahoo.com/mailtour.html
Re: Pi: Less Random Than We Thought
Sarad writes: If you remember D.E Knuth's book on Semi-Numerical Algorithms he shows some annoying subsequences of pi in it which are far from random. I don't have Knuth's book handy to look at, but it's not really correct to speak of a particular sequence or subsequence of digits as being random or non-random. For example, is this sequence of bits random: 01100100010? How about this one: 00? From a true random number generator, both are completely possible and equally valid. (Furthermore, I would contend that the digits of pi are *non-random* by definition.) --- cypherpunk [EMAIL PROTECTED] wrote: This doesn't really make sense. Either the digits are random or they are not. You can't be a little bit random. Well, you can be, but the point is that you either pass the test or you don't. [snip] The bottom line is still that either an RNG passes the tests acceptably or it does not. From what they say (or don't say), pi does pass. It doesn't make sense to say that other RNGs do better. One can only do statistical analyses of sequences of digits to determine whether they *appear* to have a uniform distribution of individual digits and subsequences. Of course the result of such a test (positive *or* negative) doesn't positively confirm whether a given digit source is truly random. Wikipedia has a good article on randomness: http://en.wikipedia.org/wiki/Random GH _ Dont just search. Find. Check out the new MSN Search! http://search.msn.click-url.com/go/onm00200636ave/direct/01/
Re: Pi: Less Random Than We Thought
Cypherpunk: While I respect your forthrightness you are unfortunately wrong. Read the chapters on Randon Mumber generation from Numerical Recipes in C and you get just a small glimpse of how sticky the issue is, particularly when it comes to computers (which are innately non-random, by the way). As a very simple example, imagine that after 10 billion digits we found that the average value was actually 5.1. This would make it, in your book, not random at all, but I suspect that for almost many uses it would be random enough. And then, imagine that the cumulative average of the digits of pi oscillated around 5 (to one part in a zillion) with a period of 100 Billion...is this random enough for you? Let us remember, of course, that the digits of pi are not random whatsoever: they are the digits of pi! Random is in the eye of the beholder. I was hoping Cordian would grumpily reply...he's a number theorist or something. -TD From: Sarad AV [EMAIL PROTECTED] To: [EMAIL PROTECTED] CC: [EMAIL PROTECTED] Subject: Re: Pi: Less Random Than We Thought Date: Thu, 5 May 2005 05:43:35 -0700 (PDT) hi, If you remember D.E Knuth's book on Semi-Numerical Algorithms he shows some annoying subsequences of pi in it which are far from random. Sarad. --- cypherpunk [EMAIL PROTECTED] wrote: This doesn't really make sense. Either the digits are random or they are not. You can't be a little bit random. Well, you can be, but the point is that you either pass the test or you don't. If pi's digits fail a test of randomness in a statistically significant way, that is big news. If they pass it, then there is no meaningful way to compare them with another RNG that also passes. It's just a statistical quirk due to random variation as to which will do better than another on any given test. The bottom line is still that either an RNG passes the tests acceptably or it does not. From what they say (or don't say), pi does pass. It doesn't make sense to say that other RNGs do better. CP Yahoo! Mail Stay connected, organized, and protected. Take the tour: http://tour.mail.yahoo.com/mailtour.html
Re: Pi: Less Random Than We Thought
Cypherpunk: While I respect your forthrightness you are unfortunately wrong. Read the chapters on Randon Mumber generation from Numerical Recipes in C and you get just a small glimpse of how sticky the issue is, particularly when it comes to computers (which are innately non-random, by the way). As a very simple example, imagine that after 10 billion digits we found that the average value was actually 5.1. This would make it, in your book, not random at all, but I suspect that for almost many uses it would be random enough. And then, imagine that the cumulative average of the digits of pi oscillated around 5 (to one part in a zillion) with a period of 100 Billion...is this random enough for you? Let us remember, of course, that the digits of pi are not random whatsoever: they are the digits of pi! Random is in the eye of the beholder. I was hoping Cordian would grumpily reply...he's a number theorist or something. -TD From: Sarad AV [EMAIL PROTECTED] To: [EMAIL PROTECTED] CC: [EMAIL PROTECTED] Subject: Re: Pi: Less Random Than We Thought Date: Thu, 5 May 2005 05:43:35 -0700 (PDT) hi, If you remember D.E Knuth's book on Semi-Numerical Algorithms he shows some annoying subsequences of pi in it which are far from random. Sarad. --- cypherpunk [EMAIL PROTECTED] wrote: This doesn't really make sense. Either the digits are random or they are not. You can't be a little bit random. Well, you can be, but the point is that you either pass the test or you don't. If pi's digits fail a test of randomness in a statistically significant way, that is big news. If they pass it, then there is no meaningful way to compare them with another RNG that also passes. It's just a statistical quirk due to random variation as to which will do better than another on any given test. The bottom line is still that either an RNG passes the tests acceptably or it does not. From what they say (or don't say), pi does pass. It doesn't make sense to say that other RNGs do better. CP Yahoo! Mail Stay connected, organized, and protected. Take the tour: http://tour.mail.yahoo.com/mailtour.html
Re: Pi: Less Random Than We Thought
[1]Autoversicherung writes Physicists including Purdue's Ephraim Fischbach have completed a study [2]comparing the 'randomness' in pi to that produced by 30 software random-number generators and one chaos-generating physical machine. After conducting several tests, they have found that while sequences of digits from pi are indeed an acceptable source of randomness -- often an important factor in data encryption and in solving certain physics problems -- pi's digit string does not always produce randomness as effectively as manufactured generators do. 1. https://autoversicherung.einsurance.de/ 2. http://news.uns.purdue.edu/UNS/html4ever/2005/050426.Fischbach.pi.html This doesn't really make sense. Either the digits are random or they are not. You can't be a little bit random. Well, you can be, but the point is that you either pass the test or you don't. If pi's digits fail a test of randomness in a statistically significant way, that is big news. If they pass it, then there is no meaningful way to compare them with another RNG that also passes. It's just a statistical quirk due to random variation as to which will do better than another on any given test. The bottom line is still that either an RNG passes the tests acceptably or it does not. From what they say (or don't say), pi does pass. It doesn't make sense to say that other RNGs do better. CP
Re: Pi: Less Random Than We Thought
[1]Autoversicherung writes Physicists including Purdue's Ephraim Fischbach have completed a study [2]comparing the 'randomness' in pi to that produced by 30 software random-number generators and one chaos-generating physical machine. After conducting several tests, they have found that while sequences of digits from pi are indeed an acceptable source of randomness -- often an important factor in data encryption and in solving certain physics problems -- pi's digit string does not always produce randomness as effectively as manufactured generators do. 1. https://autoversicherung.einsurance.de/ 2. http://news.uns.purdue.edu/UNS/html4ever/2005/050426.Fischbach.pi.html This doesn't really make sense. Either the digits are random or they are not. You can't be a little bit random. Well, you can be, but the point is that you either pass the test or you don't. If pi's digits fail a test of randomness in a statistically significant way, that is big news. If they pass it, then there is no meaningful way to compare them with another RNG that also passes. It's just a statistical quirk due to random variation as to which will do better than another on any given test. The bottom line is still that either an RNG passes the tests acceptably or it does not. From what they say (or don't say), pi does pass. It doesn't make sense to say that other RNGs do better. CP
Pi: Less Random Than We Thought
Link: http://slashdot.org/article.pl?sid=05/05/01/1759240 Posted by: timothy, on 2005-05-01 18:26:00 from the at-least-statistically dept. [1]Autoversicherung writes Physicists including Purdue's Ephraim Fischbach have completed a study [2]comparing the 'randomness' in pi to that produced by 30 software random-number generators and one chaos-generating physical machine. After conducting several tests, they have found that while sequences of digits from pi are indeed an acceptable source of randomness -- often an important factor in data encryption and in solving certain physics problems -- pi's digit string does not always produce randomness as effectively as manufactured generators do. References 1. https://autoversicherung.einsurance.de/ 2. http://news.uns.purdue.edu/UNS/html4ever/2005/050426.Fischbach.pi.html - End forwarded message - -- Eugen* Leitl a href=http://leitl.org;leitl/a __ ICBM: 48.07078, 11.61144http://www.leitl.org 8B29F6BE: 099D 78BA 2FD3 B014 B08A 7779 75B0 2443 8B29 F6BE http://moleculardevices.org http://nanomachines.net signature.asc Description: Digital signature
