5 ms·

Because the sets of decimal and binary digits are: {0,1,2,3,4,5,6,7,8,9} {0,1} respectively. Any subsequence of digits of Pi, such as {1,1,3,9,3,5}, i

Because the sets of decimal and binary digits are: {0,1,2,3,4,5,6,7,8,9} {0,1} respectively. Any subsequence of digits of Pi, such as {1,1,3,9,3,5}, is equal to the subsequence {7,9,3,5,3,3} under the proposed function. They have the same image. That completely mucks with your probability because you've eliminated so much uncertainty. You're selecting from a space of 10 digits for inputs, but the computer only has to guess from a space of 2 digits for outputs.

umvi 8y ago
I'm no math expert, but to me the only question that should matter is: how random is the parity distribution of digits in pi? If the answer is "perfectly random", then that means each digit in pi should have a perfectly random parity. If the answer is not "perfectly random" then that means you should be able to predict the parity of the next digit based on the parity of previous digits with probability >50% in the long run, which I don't think holds true for pi (I could be wrong).
- throwawaymath 8y ago
  That's an interesting point I hadn't really thought about. The set of all even naturals is isomorphic to the set of all odd naturals, so technically speaking you'd be right. If every number appears with equal likelihood in a sequence, you'd have evens and odds appearing with equal likelihood.
- gus_massa 8y ago
  > how random is the parity distribution of digits in pi? If the answer is "perfectly random" Nobody knows! Everyone in math is sure that it is, but nobody had found a proof yet. (It may be false...) An extension to this question is if pi is a "normal number". More details: https://en.wikipedia.org/wiki/Normal_number https://en.wikipedia.org/wiki/Normal_number http://mathworld.wolfram.com/NormalNumber.html http://mathworld.wolfram.com/NormalNumber.html
gus_massa 8y ago
No. [There are some technical details because pi is not a random number, but for the sake of simplicity, let's assume that pi is a random number.] It's much easier if we'd live in a word that use base 8 instead of base 10. Let's suppose that we have the sequence of digits of pi in base 8.The algorithm of the GP is to replace {0,2,4,6}->0 and {1,3,5,7}->1 to obtain a binary "random" sequence. Your alternative is to write pi in binary, and use it as a "random" sequence. But if this is a good "random" sequence then you can pick every third digit and get another good "random" sequence. [Here good means something like iid with uniform distribution] But if you start at the correct position, it's equivalent to pick every third number of the binary representation and to classify the digits in the base 8 representation as even or odd. If you choose other starting points to pick every third digit, you get alternative maps: * low and high: {0,1,2,3}->0 and {4,5,6,7}->1 (like in the roulette[1]) * crazy: {0,1,4,5}->0 and {2,3,6,7}->1 These other two selections produce also good "random" sequences. The important part is that the projection that is selected maps the same number of elements to each element. In this case the three methods maps 4 elements to 1. This ensures that it maps iid with an uniform distribution to an iid with a uniform distribution. Moreover, you can pick any arbitrary 4 numbers and map them to 0 and map the other 4 to 1 and it will work as well as the other three maps I used. (This is like the red/black option in the roulette[1].) --- Back to base 10. Any map that maps 5 number to 1 will maps iid with an uniform distribution to an iid with a uniform distribution. In particular the even/odd map that the GP is using is fine. With this map you loose a lot of entropy, but since there is infinite entropy you can drop a lot of it and still keep infinite entropy. It's not as efficient as using the base 2, but it correct. [1] An ilegal fair roulette, with 36 numbers, without the green 0.
- throwawaymath 8y ago
  Yes you're correct. I neglected to account for the bijection between even naturals and odd naturals, and was only considering finite strings. Since we're talking about infinite (or potentially infinite) strings here, the reduction in entropy is alright as you've stated since even and odds occur with equal probability if every digit of Pi occurs with equal probability.
- mark-r 8y ago
  You could use rejection sampling to simply drop the digits that are 8 or 9, then you'd have a base 8 number to work with.

umvi 8y ago

I'm no math expert, but to me the only question that should matter is: how random is the parity distribution of digits in pi? If the answer is "perfectly random", then that means each digit in pi should have a perfectly random parity. If the answer is not "perfectly random" then that means you should be able to predict the parity of the next digit based on the parity of previous digits with probability >50% in the long run, which I don't think holds true for pi (I could be wrong).

throwawaymath 8y ago
That's an interesting point I hadn't really thought about. The set of all even naturals is isomorphic to the set of all odd naturals, so technically speaking you'd be right. If every number appears with equal likelihood in a sequence, you'd have evens and odds appearing with equal likelihood.
gus_massa 8y ago
> how random is the parity distribution of digits in pi? If the answer is "perfectly random" Nobody knows! Everyone in math is sure that it is, but nobody had found a proof yet. (It may be false...) An extension to this question is if pi is a "normal number". More details: https://en.wikipedia.org/wiki/Normal_number https://en.wikipedia.org/wiki/Normal_number http://mathworld.wolfram.com/NormalNumber.html http://mathworld.wolfram.com/NormalNumber.html

gus_massa 8y ago

No. [There are some technical details because pi is not a random number, but for the sake of simplicity, let's assume that pi is a random number.] It's much easier if we'd live in a word that use base 8 instead of base 10. Let's suppose that we have the sequence of digits of pi in base 8.The algorithm of the GP is to replace {0,2,4,6}->0 and {1,3,5,7}->1 to obtain a binary "random" sequence. Your alternative is to write pi in binary, and use it as a "random" sequence. But if this is a good "random" sequence then you can pick every third digit and get another good "random" sequence. [Here good means something like iid with uniform distribution] But if you start at the correct position, it's equivalent to pick every third number of the binary representation and to classify the digits in the base 8 representation as even or odd. If you choose other starting points to pick every third digit, you get alternative maps: * low and high: {0,1,2,3}->0 and {4,5,6,7}->1 (like in the roulette[1]) * crazy: {0,1,4,5}->0 and {2,3,6,7}->1 These other two selections produce also good "random" sequences. The important part is that the projection that is selected maps the same number of elements to each element. In this case the three methods maps 4 elements to 1. This ensures that it maps iid with an uniform distribution to an iid with a uniform distribution. Moreover, you can pick any arbitrary 4 numbers and map them to 0 and map the other 4 to 1 and it will work as well as the other three maps I used. (This is like the red/black option in the roulette[1].) --- Back to base 10. Any map that maps 5 number to 1 will maps iid with an uniform distribution to an iid with a uniform distribution. In particular the even/odd map that the GP is using is fine. With this map you loose a lot of entropy, but since there is infinite entropy you can drop a lot of it and still keep infinite entropy. It's not as efficient as using the base 2, but it correct. [1] An ilegal fair roulette, with 36 numbers, without the green 0.

throwawaymath 8y ago
Yes you're correct. I neglected to account for the bijection between even naturals and odd naturals, and was only considering finite strings. Since we're talking about infinite (or potentially infinite) strings here, the reduction in entropy is alright as you've stated since even and odds occur with equal probability if every digit of Pi occurs with equal probability.
mark-r 8y ago
You could use rejection sampling to simply drop the digits that are 8 or 9, then you'd have a base 8 number to work with.