I'm not sure why, but I struggled with the concept of randomness in my algorithms class. On the last day of class, the professor signed his book, "May you one day explain randomness to all of us"
The Art of Computer Programming: Random Numbers
21–29 of 29 posts
Re: The Art of Computer Programming: Random Numbers
#22Earlier quoted context omitted.
You are 100% mistaken that this implies we had a good definition of random sequences before Knuth. In the article you link, they discuss the uniform distribution, but any distribution (and the modern notion of probability in general) absolutely depends on a mathematically precise notion of random sequences. If you don't believe me, read the chapter. Early probability theorists (e.g., von Mises, Kolmogorov) literally…
I skimmed through the extract presented (didn't have time to go into detail) but I don't see a formal definition of any kind presented in the extract. Could you point me to where it is? And if it's not in the extract, then could you quote it here? Pseudorandomness is not the same thing as randomness but most algorithms today work on pseudorandom numbers so the concept is important. My impression was that that's what…
So, the excerpt here is chapter 3, section 1. The actual definition happens in chapter 3 section 5 ("What Is a Random Sequence?"). I have the book at home, though, so I can't quote it here. Sorry. But the intuition is, if you have an infinite sequence of random numbers, then the numbers in all infinite subsequences should be equidistributed. So, like, if you a stream of random 0's and 1's, then if you pick only every other number, the 0's and 1's have to be equiprobable, and if you pick every third number, they still have to be equiprobable, etc. This is slightly wrong, but it's on the right track to the actual definition.
re: Pseudorandomness, the point of pseudorandomness is the following.
1. A lot of algorithms use randomness to make pathologically bad cases extremely unlikely. For example, choosing a random pivot in quicksort makes the worst case very unlikely.
2. But in a lot of cases, this leads to huge amounts of space consumption. For example, most frequency moment estimations involve a matrix of random numbers. So if you're getting those numbers from a "truly random" source, then you have to store the entire matrix, which can be huge.
3. So, a better solution is to use a pseudorandom number generator! That way you can store a seed of s bits, and do something clever, like deterministically re-generate the matrix as you need it, rather than storing it outright.
Notice though, that this is not independent of the notion of randomness! In fact they are quite intimately tied together.
Re: The Art of Computer Programming: Random Numbers
#23Earlier quoted context omitted.
I skimmed through the extract presented (didn't have time to go into detail) but I don't see a formal definition of any kind presented in the extract. Could you point me to where it is? And if it's not in the extract, then could you quote it here? Pseudorandomness is not the same thing as randomness but most algorithms today work on pseudorandom numbers so the concept is important. My impression was that that's what…
So, the excerpt here is chapter 3, section 1. The actual definition happens in chapter 3 section 5 ("What Is a Random Sequence?"). I have the book at home, though, so I can't quote it here. Sorry. But the intuition is, if you have an infinite sequence of random numbers, then the numbers in all infinite subsequences should be equidistributed. So, like, if you a stream of random 0's and 1's, then if you pick only every…
Your definition relies on the notion of probability though. So I'm not sure why you seemingly view Knuth's work as more fundamental than Kolmogorov's, etc.
Re: The Art of Computer Programming: Random Numbers
#24Earlier quoted context omitted.
So, the excerpt here is chapter 3, section 1. The actual definition happens in chapter 3 section 5 ("What Is a Random Sequence?"). I have the book at home, though, so I can't quote it here. Sorry. But the intuition is, if you have an infinite sequence of random numbers, then the numbers in all infinite subsequences should be equidistributed. So, like, if you a stream of random 0's and 1's, then if you pick only every…
Your definition relies on the notion of probability though. So I'm not sure why you seemingly view Knuth's work as more fundamental than Kolmogorov's, etc.
Because the trick Knuth pulls is to express this intuition without appealing to the definition of probability. It's quite clever.
Re: The Art of Computer Programming: Random Numbers
#25This reminds me of a (somewhat) funny situation that happened to me one time. My parents bought some Lotto tickets and wanted to play, so they filled most of the combinations themselves and left two of them for me. I was annoyed by having to do that, so I take the tickets, and ask my dad, "So, you know that every combination is equally likely to win?", and he casually replies something like, "Yeah, sure, I'm not dumb…
I ran through the same script with my dad once, except he answered "Yeah, but you'll have to split the pot with more smartasses like you."
"You know, the most amazing thing happened to me tonight. I was coming here, on the way to the lecture, and I came in through the parking lot. And you won't believe what happened. I saw a car with the license plate ARW 357. Can you imagine? Of all the millions of license plates in the state, what was the chance that I would see that particular one tonight? Amazing!" -- Feynman
Re: The Art of Computer Programming: Random Numbers
#26I feel compelled to share this quote from the author of cfengine with whom I have had some emails of late, because it neatly summarizes a more holistic, physics-inspired approach to the computational world's obsession with invariance, which could be seen as present in the quest for 'randomness'.
The simplest idea of stability is constancy, or invariance. A thing that has no possibility to change is, by definition, immune to external pertubations. [...] Invariance is an important concept, but also one that has been shattered by modern ideas of physics. What was once considered invariant, is usually only apparently invariant on a certain scale. When one looks in more detail, we find that we may only have invariance of an average. - Mark Burgess, In Search of Certainty: The Science of Our Information Infrastructure (2013)
This accords well with the opening quotation Lest men suspect your tale untrue, Keep probability in view. - John Gay, English poet and dramatist and member of the Scriblerus Club (1727) https://en.wikipedia.org/wiki/John_Gay
Re: The Art of Computer Programming: Random Numbers
#27Do the Monte Carlo people all know about Barash and Shchur's work? They made an RNGSSELIB and PRAND (using NVIDIA cards), but the main contribution is that they incorporated a new way to generate multiple streams not by re-seeding the generator but by skipping ahead, even with Mersenne twisters. It is the only simple way to get parallel streams, and it didn't exist just a few years ago. You still need to be careful i…
If you're interested in Monte Carlo techniques for statistical physics, I'll recommend Kurt Binder's "Monto Carlo Simulation in Statistical Physics" (http://www.springer.com/physics/theoretical%2C+mathematical+...).
Re: The Art of Computer Programming: Random Numbers
#28Earlier quoted context omitted.
Your definition relies on the notion of probability though. So I'm not sure why you seemingly view Knuth's work as more fundamental than Kolmogorov's, etc.
Because the trick Knuth pulls is to express this intuition without appealing to the definition of probability. It's quite clever.
What's the sketch of the trick? I can define randomness by appealing to some of the same basic theory used to develop probability, but it's not really independent despite looking that way from the outside. Does Knuth do this uniquely?
Re: The Art of Computer Programming: Random Numbers
#29Once you've got pseudorandom bits working, the next step is generating variates from different distributions. Luc Devroye has a nice book on this freely available online, "Non-Uniform Random Variate Generation". http://luc.devroye.org/rnbookindex.html
This book deserves lots of recommendations. Luc Devroye does generally, as well.