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