3 ms·

Technically you should convert Pi to base 2 before doing that, because using each decimal digit's parity collapses a lot of information in a lossy way. If your

Technically you should convert Pi to base 2 before doing that, because using each decimal digit's parity collapses a lot of information in a lossy way. If your function is: f: π(k) --> δ(k) where π(k) is the kth digit of π and δ(k) = 0 if k is even and 1 if k is odd, then your function is injective. The image of every even under f is equal, likewise with the image of every odd under f. A huge amount of entropy is destroyed that way. So even if Pi could be used as a pseudorandom generator (and it actually can't be), you'd lose that property by defining an injective map from your domain of inputs to the codomain of outputs.

CapacitorSet 8y ago
Why can't pi be used as a PRNG, and why does converting each digit to its parity lose a possible PRNG property? Sure it removes a lot of entropy, but it does so by destroying information, not from creating/overwriting memory.
- jimktrains2 8y ago
  Pi can be as it's (thought to be) normal (all digits appear with uniform frequency), but like anything, it's how you use it. Imagine you selected a digit from pie and used it to decide rock, paper, or scissors (3 options, so let's take a digit and mod 3) 0: 0 Rock 1: 1 Paper 2: 2 Scissors 3: 0 Rock 4: 1 Paper 5: 2 Scissors 6: 0 Rock 7: 1 Paper 8: 2 Scissors 9: 0 Rock Now, let's check the frequency of each option: 0/Rock: 4 1/Paper: 3 2/Scissors: 3 Your RNG is biased towards 0 here. The same thing happens, and is very common, when people just take the system random number generator and mod it by the number of values they want. They always end up biasing the bottom section of their distribution. The common way of dealing with this is to "ignore" any number that would make the set biased. Here you would ignore 9 and you have an even distribution. So, you're playing 7 rounds of RPS and you go 3/R 1/P 4/P 1/P 5/S 9! SKIP! 2/S 6/R
- 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!??
Yajirobe 8y ago
> A huge amount of entropy is destroyed And why is that a problem for generating random arrow presses?
- throwawaymath 8y ago
  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
jimktrains2 8y ago
π is normal in all bases, so in the end it doesn't matter, you're just using up more data.
- throwawaymath 8y ago
  No, it's not known that Pi is normal. This is a very, very open question. We don't even have a way of tackling that question at the moment. You're correct that if Pi is normal, it's normal in all bases. But that's precisely the point I'm getting at - if Pi is normal, you need to use base 2 for this to work because your codomain is just {0,1}. Mapping a number to another number such that each digit becomes its own parity is materially different from converting that number to base 2. They aren't the same thing whatsoever, and you can't generally take a normal number and create another normal number this way. So even if we accept the reasonable conjecture that Pi is normal, you still need to map it to the same base as your codomain in order for its entropy to be preserved. The proposed function is injective and destroys entropy.
  - twanvl 8y ago
    > But that's precisely the point I'm getting at - if Pi is normal, you need to use base 2 for this to work because your codomain is just {0,1}. You can use any base that is a multiple of 2 (like 10) and then apply a parity function to the digits. If pi is normal, then the digit parity sequence is also normal. Sure you lose some entropy, but in some sense the digits of pi have 0 entropy anyway since they can be calculated. And in the other sense of treating the digits of pi as an unknown random sequence, there is infinite entropy, so throwing away 70% of it doesn't matter.
    - throwawaymath 8y ago
      Yeah someone else pointed out a similar point about the bijection of evens and odds, good point. My initial claim is incorrect, so I'll concede that. I was operating from the idea that there is no bijection between the naturals and a parity check function, but you're right that if one sequence is normal the second set should also be normal regardless of invertibility.

CapacitorSet 8y ago

Why can't pi be used as a PRNG, and why does converting each digit to its parity lose a possible PRNG property? Sure it removes a lot of entropy, but it does so by destroying information, not from creating/overwriting memory.

jimktrains2 8y ago
Pi can be as it's (thought to be) normal (all digits appear with uniform frequency), but like anything, it's how you use it. Imagine you selected a digit from pie and used it to decide rock, paper, or scissors (3 options, so let's take a digit and mod 3) 0: 0 Rock 1: 1 Paper 2: 2 Scissors 3: 0 Rock 4: 1 Paper 5: 2 Scissors 6: 0 Rock 7: 1 Paper 8: 2 Scissors 9: 0 Rock Now, let's check the frequency of each option: 0/Rock: 4 1/Paper: 3 2/Scissors: 3 Your RNG is biased towards 0 here. The same thing happens, and is very common, when people just take the system random number generator and mod it by the number of values they want. They always end up biasing the bottom section of their distribution. The common way of dealing with this is to "ignore" any number that would make the set biased. Here you would ignore 9 and you have an even distribution. So, you're playing 7 rounds of RPS and you go 3/R 1/P 4/P 1/P 5/S 9! SKIP! 2/S 6/R
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!??

Yajirobe 8y ago

> A huge amount of entropy is destroyed And why is that a problem for generating random arrow presses?

throwawaymath 8y ago
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

jimktrains2 8y ago

π is normal in all bases, so in the end it doesn't matter, you're just using up more data.

throwawaymath 8y ago
No, it's not known that Pi is normal. This is a very, very open question. We don't even have a way of tackling that question at the moment. You're correct that if Pi is normal, it's normal in all bases. But that's precisely the point I'm getting at - if Pi is normal, you need to use base 2 for this to work because your codomain is just {0,1}. Mapping a number to another number such that each digit becomes its own parity is materially different from converting that number to base 2. They aren't the same thing whatsoever, and you can't generally take a normal number and create another normal number this way. So even if we accept the reasonable conjecture that Pi is normal, you still need to map it to the same base as your codomain in order for its entropy to be preserved. The proposed function is injective and destroys entropy.
- twanvl 8y ago
  > But that's precisely the point I'm getting at - if Pi is normal, you need to use base 2 for this to work because your codomain is just {0,1}. You can use any base that is a multiple of 2 (like 10) and then apply a parity function to the digits. If pi is normal, then the digit parity sequence is also normal. Sure you lose some entropy, but in some sense the digits of pi have 0 entropy anyway since they can be calculated. And in the other sense of treating the digits of pi as an unknown random sequence, there is infinite entropy, so throwing away 70% of it doesn't matter.
  - throwawaymath 8y ago
    Yeah someone else pointed out a similar point about the bijection of evens and odds, good point. My initial claim is incorrect, so I'll concede that. I was operating from the idea that there is no bijection between the naturals and a parity check function, but you're right that if one sequence is normal the second set should also be normal regardless of invertibility.