3 ms·

The top answer is an excellent demonstration of the central limit theorem and why the question's assumption that rand() and rand() * rand() are "equally random"

by drblast 16y ago

The top answer is an excellent demonstration of the central limit theorem and why the question's assumption that rand() and rand() * rand() are "equally random" is wrong. The central limit theorem is one of the most initially surprising and fascinating things in all of math. Please support the central limit theorem by learning about it on Wikipedia, or wherever fine theorems are discussed. Edit to add: If you haven't learned about this enough to know that implementing systems that depend on randomness, like cryptographic systems, is really, really difficult and error-prone, please just use a standard library instead. It's the most counter-intuitive thing in the world that rand() * rand() is less secure than rand(); shouldn't it be twice as unpredictable? But it's not. Cryptography and related fields are rife with counter-intuitive gotchas.

jpr 16y ago
A link for the lazy: http://en.wikipedia.org/wiki/Central_limit_theorem http://en.wikipedia.org/wiki/Central_limit_theorem
- sophacles 16y ago
  Oh man, I would totally upvote you in thanks, but I'm too lazy. Not to mention the moralist in me wanting to instead berate you for keeping the lazy that way. Luckily the karma whore in me has trumped all that and convince the rest to reply with snark :)
hvs 16y ago
My favorite quote from that page: Don't take Statistics and Intuition to the same party ....
- Eliezer 16y ago
  It's my favorite quote too, but intuitions, unlike probability theory, can be changed.
cdavidcash 16y ago
It's the most counter-intuitive thing in the world that rand() rand() is less secure than rand(); shouldn't it be twice as unpredictable?* Under some reasonable assumptions, rand() + rand() mod 1 is twice as random! If both calls return independent samples, and at least one of the calls to rand() returns a uniform sample in [0,1], then the sum will be uniform on [0,1]. So if you assume you get at least one good shot and that the other is not specifically correlated to it, you'll be improving your randomness.
- thesz 16y ago
  I think, you meant "rand() + rand() mod 2". This is used to get more randomness from not-so-random source. Just an example. If our rand() returns 0 2/3 of time and 1 1/3 of time, our rand() + rand() mod 2 will return: 0 + 0 mod 2 = 0 2/32/3 = 4/9 times, 1 + 0 mod 2 = 1 1/32/3 = 2/9 times, 0 + 1 mod 2 = 1 2/31/3 = 2/9 times and 1 + 1 mod 2 = 0 1/31/3 = 1/9 times. So we will get 0 5/9 times and 1 4/9 times. Now we get random source that is much more uniform. I think it is possible to obtain random bits even from source with correlated samples.
onedognight 16y ago
Here's some intuition about why rand() * rand() is different than rand(). Let's say you are doing rand(2) which produces either 0 or 1, each equally often, then rand(2) * rand(2) will produce 0 much more often than 1. 0 * 0 = 0 0 * 1 = 0 1 * 0 = 0 1 * 1 = 1 Addition has a similar problem. 0 + 0 = 0 0 + 1 = 1 1 + 0 = 1 1 + 1 = 2 If you use the right range and wrap the result. e.g. if you do mod(rand(2^n) + rand(2^n), 2^n) then addition will not affect the distribution of your numbers.
- danger 16y ago
  Or you could argue formally by pointing out that the maximum entropy distribution on the interval [0,1] is the uniform distribution, so modifying that distribution will only decrease its entropy, which means that it's "more predictable". http://en.wikipedia.org/wiki/Entropy_(information_theory) http://en.wikipedia.org/wiki/Entropy_(information_theory) http://en.wikipedia.org/wiki/Maximum_entropy_probability_distribution#Uniform_and_piecewise_uniform_distributions http://en.wikipedia.org/wiki/Maximum_entropy_probability_dis...
pjscott 16y ago
I remember when I first learned about the central limit theorem, having this sudden realization: So that's where all those normal distributions come from! In the statistics classes that most people take, they just dump this weird equation on you, and say that the normal distribution often arises in the real world. But they don't explain why, or in what kinds of situations you're likely to see things being normally distributed. It's like suddenly finding a walrus in your living room: everybody assures you that it's supposed to be there, but where the hell did it come from? The central limit theorem de-mystifies the normal distribution and makes the world easier to understand.

by drblast 16y ago

jpr 16y ago

A link for the lazy: http://en.wikipedia.org/wiki/Central_limit_theorem http://en.wikipedia.org/wiki/Central_limit_theorem

sophacles 16y ago
Oh man, I would totally upvote you in thanks, but I'm too lazy. Not to mention the moralist in me wanting to instead berate you for keeping the lazy that way. Luckily the karma whore in me has trumped all that and convince the rest to reply with snark :)

hvs 16y ago

My favorite quote from that page: Don't take Statistics and Intuition to the same party ....

Eliezer 16y ago
It's my favorite quote too, but intuitions, unlike probability theory, can be changed.

cdavidcash 16y ago

It's the most counter-intuitive thing in the world that rand() rand() is less secure than rand(); shouldn't it be twice as unpredictable?* Under some reasonable assumptions, rand() + rand() mod 1 is twice as random! If both calls return independent samples, and at least one of the calls to rand() returns a uniform sample in [0,1], then the sum will be uniform on [0,1]. So if you assume you get at least one good shot and that the other is not specifically correlated to it, you'll be improving your randomness.

thesz 16y ago
I think, you meant "rand() + rand() mod 2". This is used to get more randomness from not-so-random source. Just an example. If our rand() returns 0 2/3 of time and 1 1/3 of time, our rand() + rand() mod 2 will return: 0 + 0 mod 2 = 0 2/32/3 = 4/9 times, 1 + 0 mod 2 = 1 1/32/3 = 2/9 times, 0 + 1 mod 2 = 1 2/31/3 = 2/9 times and 1 + 1 mod 2 = 0 1/31/3 = 1/9 times. So we will get 0 5/9 times and 1 4/9 times. Now we get random source that is much more uniform. I think it is possible to obtain random bits even from source with correlated samples.

onedognight 16y ago

Here's some intuition about why rand() * rand() is different than rand(). Let's say you are doing rand(2) which produces either 0 or 1, each equally often, then rand(2) * rand(2) will produce 0 much more often than 1. 0 * 0 = 0 0 * 1 = 0 1 * 0 = 0 1 * 1 = 1 Addition has a similar problem. 0 + 0 = 0 0 + 1 = 1 1 + 0 = 1 1 + 1 = 2 If you use the right range and wrap the result. e.g. if you do mod(rand(2^n) + rand(2^n), 2^n) then addition will not affect the distribution of your numbers.

danger 16y ago
Or you could argue formally by pointing out that the maximum entropy distribution on the interval [0,1] is the uniform distribution, so modifying that distribution will only decrease its entropy, which means that it's "more predictable". http://en.wikipedia.org/wiki/Entropy_(information_theory) http://en.wikipedia.org/wiki/Entropy_(information_theory) http://en.wikipedia.org/wiki/Maximum_entropy_probability_distribution#Uniform_and_piecewise_uniform_distributions http://en.wikipedia.org/wiki/Maximum_entropy_probability_dis...

pjscott 16y ago

I remember when I first learned about the central limit theorem, having this sudden realization: So that's where all those normal distributions come from! In the statistics classes that most people take, they just dump this weird equation on you, and say that the normal distribution often arises in the real world. But they don't explain why, or in what kinds of situations you're likely to see things being normally distributed. It's like suddenly finding a walrus in your living room: everybody assures you that it's supposed to be there, but where the hell did it come from? The central limit theorem de-mystifies the normal distribution and makes the world easier to understand.