How significantly decreased is the entropy of rand() ^ rand()?

Question

Assuming a language-agnostic setup in which the rand() function has a flawless implementation and returns a very large (let's say 128 bits), strong random unsigned integer, I should have fairly low chances of getting the same number twice considering the period of the RNG would be astronomically huge.

a = rand(); // very very low chances of getting twice the same number

However, if I XOR two such random integers, how significantly is the entropy of the oputput decreased? In other words, how worse are the chances that such a function:

def xorRand(): return rand() ^ rand();

returns twice the same number, compared to my hypothetical rand() alone?

Why would you do that? I doubt the entrophy will get any better from that (if so, the generator would already do it, wouldn't it?), so it wouldn't be useful for a PRNG either. — , May 09 '11 at 15:54
I know the entropy can't be increased and I suspect it would be worse, and as such I wouldn't do that. I'm simply wondering _how worse_ it would be. It's more a theoretical issue than a practical issue. — zneak, May 09 '11 at 15:57
Like everything in probability, the odds are 50:50: It either happens, or it doesn't. — Marc B, May 09 '11 at 15:57
@Marc Therefore, since everyone is either killed by a freak badger attack or not, 50% of people are killed by badgers. — Nick Johnson, May 09 '11 at 18:46
Those badgers can get very angry when suddenly confronted with a mushroom... — Marc B, May 09 '11 at 19:01

score 4 · Answer 1 · answered May 09 '11 at 15:58

4

Suppose you had a 1-bit PRNG. The possible outcomes are:

1 ^ 1  -> 0
1 ^ 0  -> 1
0 ^ 1  -> 1
0 ^ 0  -> 0

So it looks to me as if it makes no difference.

answered May 09 '11 at 15:58

Well reasoned. For what it's worth, I came to the same conclusion after reading the question (although my proof isn't nearly as simple). – David Wolever May 09 '11 at 16:10

score 3 · Accepted Answer · edited May 23 '17 at 12:19

If the rand() function is a good implementation as you said, there's no difference between using rand() or xorRand() except that the latter takes twice the time.

If all of the 128 output bits are used, rand() will return each number with the same probability, so it will have chance 1:2**128 to return the same number as before. Same for xorRand(), as the XOR function is "symmetric" and returns equally distributed outputs for two equally distributed inputs.

This will only change if you either use a bad rand() implementation or a different "assymetric" operator like AND.

Note that using xorRand() often will even improve entropy for bad rand() implementations, f.e. think of a rand() that alternately returns a good random number and 0.

By the way, if you want to prevent your random function to generate the same number twice, do it yourself, f.e. by using a shuffle algorithm. There are many SO questions and answers that deal with this (like this one).

How significantly decreased is the entropy of rand() ^ rand()?

2 Answers2