4 ms·

When I see the word "random" I parse it as "unpredictable", since this is usually what people mean (even if they don't realise it) and can clear up many argumen

When I see the word "random" I parse it as "unpredictable", since this is usually what people mean (even if they don't realise it) and can clear up many arguments. The concept of 'random' is interesting in some cases, but the vast majority of the time it's far stronger than what is required. In this case, the question is: > If a number generator is uniformly distributed, why might that not be 'random enough'? If we rephrase this as: > If a number generator is uniformly distributed, why might that be 'too predictable'? This makes the flaw obvious: there are many ways to choose numbers uniformly which are completely predictable. For example, choose the smallest value first, then choose a value which is furthest from any previously-chosen value (in, say, lexicographic gray-code order). The point here is that 'uniformity' is not the property we care about; it is a consequence of the property we care about (unpredictability). If a distribution were non-uniform, we would be better able to predict it (by biasing out predictions to match the distribution), hence the least-predictable distribution is necessarily a uniform one. Other times this comes up: > Are quantum measurements 'truly random'? That's untestable, but we can test whether they're predictable or not. > This encryption algorithm requires a source of random bits. It would work just as well with a source of bits that are merely unpredictable. > This strategy can only be defeated by a random opponent. It can also be defeated by an opponent which you can't predict. And so on.

dllthomas 13y ago
"[T]he vast majority of the time it's far stronger than what is required." Oftentimes it's also just not what is actually required. Often you want uniform spacing with some jitter, not points drawn from a uniform distribution.
sdevlin 13y ago
That is a good way to think of it. Indeed, that is how cryptographic randomness is typically defined. Simply put: given the first k bits of a random stream, can you predict the k+1th bit (more than 50% of the time)? A generator that passes this test will pass any statistical randomness test, but the converse is not necessarily true. For example Mersenne Twister is a good generator from a statistical perspective, but it's actually quite easy to recover its internal state by observing a small amount of output. (Around 20k bits, if I recall correctly.)
- dalke 13y ago
  > Simply put: given the first k bits of a random stream, can you predict the k+1th bit (more than 50% of the time)? This definition isn't sufficient. Suppose you have a random stream, and one predictor which asserts the next bit is "1" and another predictor which says that next bit is "0". As k increases, there's a nearly 100% chance that one of the two predictors will be correct more than 50% of the time. Even if you pick a single predictor, say, that all-1s predictor, there's an almost 50% chance that for a given random stream and k that it will have better than 50% predictive ability. Just because Guildenstern's coin is heads 92 times in a row doesn't mean that it's not random. Only that it's very unlikely to be random.
  - sesqu 13y ago
    > very unlikely to be random. Speaking of word replacements, "random" does not mean "uniformly distributed". An unfair coin toss is still random.

dllthomas 13y ago

"[T]he vast majority of the time it's far stronger than what is required." Oftentimes it's also just not what is actually required. Often you want uniform spacing with some jitter, not points drawn from a uniform distribution.

sdevlin 13y ago

That is a good way to think of it. Indeed, that is how cryptographic randomness is typically defined. Simply put: given the first k bits of a random stream, can you predict the k+1th bit (more than 50% of the time)? A generator that passes this test will pass any statistical randomness test, but the converse is not necessarily true. For example Mersenne Twister is a good generator from a statistical perspective, but it's actually quite easy to recover its internal state by observing a small amount of output. (Around 20k bits, if I recall correctly.)

dalke 13y ago
> Simply put: given the first k bits of a random stream, can you predict the k+1th bit (more than 50% of the time)? This definition isn't sufficient. Suppose you have a random stream, and one predictor which asserts the next bit is "1" and another predictor which says that next bit is "0". As k increases, there's a nearly 100% chance that one of the two predictors will be correct more than 50% of the time. Even if you pick a single predictor, say, that all-1s predictor, there's an almost 50% chance that for a given random stream and k that it will have better than 50% predictive ability. Just because Guildenstern's coin is heads 92 times in a row doesn't mean that it's not random. Only that it's very unlikely to be random.
- sesqu 13y ago
  > very unlikely to be random. Speaking of word replacements, "random" does not mean "uniformly distributed". An unfair coin toss is still random.