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