3 ms·
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, ca
by 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.