3 ms·
The simple reason is because a pseudorandom number generator is a complexity theoretic thing, but an information theoretic thing. In order for it to be robust,
by throwawaymath 8y ago
The simple reason is because a pseudorandom number generator is a complexity theoretic thing, but an information theoretic thing. In order for it to be robust, it must be indistinguishable from true random for any polynomial time algorithm. Since we have algorithms which can calculate Pi in polynomial time, as long as the computer recognized the sequence (or the deterministic seed of the sequence as Pi), it could with certainty predict the next digit of the sequence.
As for why converting digits in this way matters - a lot of randomness is expressed by the entropy. It's harder for you to correctly guess the sequence {1,7,9,3,6,8,2,4} than it is to guess the sequence {1,1,1,1,0,0,0,0}.
If I ask you to guess a decimal digit I've chosen "randomly", you have a 1/10 chance of being correct. If I ask you to do the same for binary digits, you have a 1/2 chance of being correct.
Basically you want to think of these as subsequences, not individual numbers. If Pi is normal (which is a big if), then Pi is normal in every single base, including decimal or binary. But it's not generally true that a normal number generates another normal number by mapping each digit to the digit's parity.
- deleted 8y ago[deleted]
- pbhjpbhj 8y ago> it could with certainty predict the next digit of the sequence // If pi is [absolutely] normal though all sequences exist in it at equal frequency. Meaning that for any given sequence there is an infinite number of positions in pi to find it and that all the possible following digit sequences are equally likely. So the computer could never know the next digit. Aside: guessing a D16 roll seems way more likely than guessing a nibble of binary, and perhaps a little less likely than guessing 4 coin flips!??