Hacker News Reader

Comment by throwawaymath | Hacker News Reader

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.

View on HN

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.

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

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.

> 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!??

> A huge amount of entropy is destroyed

And why is that a problem for generating random arrow presses?

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.

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.

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.

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.

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).

> 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 http://mathworld.wolfram.com/NormalNumber.html

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.

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

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.

> 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.

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.

Reply on news.ycombinator.com