Hacker News new | ask | show | jobs
by wgx 4118 days ago
"almost all 0" is still random. :)
1 comments

No it isn't. If you can predict with more than 50% what the next bit will be - it's not random.
Or you're lucky. One time a friend of mine was describing his fool-proof plan to win at Roulette. I jokingly asked, "What, double your bet when you lose?". He replied—in all seriousness—"No, triple it!"

I then argued with him about the money he would likely lose implementing his plan. He said, "what are the odds the ball will land on red five times in a row?". (We were ignoring the existence of the green 0 and 00). I took out a quarter, flipped it seven times, and it landed heads every time. This happened straight-away.

That was a random sequence, it was all 0s, and I'd like to think he was lucky that it happened that way, and convinced him to abandon his plan.

But I was also lucky. I had intended to demonstrate this, and was prepared to be flipping the coin hundreds of times until the run of 0s came up. You could say I was predicting the next result correctly 100% of the time on those first 7 flips. But my ability to predict the results didn't show their non-randomness, instead it showed my "luckiness". Which really means they weren't predictions at all, I guess.

That's called the Martingale betting system, and yeah it requires a gambler with infinite wealth
And a table with no maximum betting limit.
Just because it's biased towards 0 it doesn't mean there's no entropy in it. Even the raw output of an entropy source based on radioactive decay or thermal noise is biased.

To generate a highly random output that appears independent from the source and uniformly distributed a randomness extractor [1] has to beapplied. The most well know is the Von Neumann extractor.

[1] http://en.wikipedia.org/wiki/Randomness_extractor

You're talking about a cryptographically secure random. Normal random can really contain any sequence, including a repeating string of 1's or 0's. The infinite monkey theorem proves it :)
I'm of the opinion that any definition of random string that says the same string S is random or not depending on how we got it is just silly.

IMHO random string = string that has Kolmogorov complexity = length of this string.

Almost all strings we got from random variables with uniform distribution are random, but not all.