What is the proper/canonical way to do this?

For example, $0 < r1 < 1$ and $0 < r2 < 1$. Presuming uniformly distributed probabilities for the two, combining/averaging them is going to bias very quickly towards $0.5$.

The specific use case I have is a game/simulation I'm programming. An entity has a random number it was given that's specific to it; Their individual behaviours also have random numbers associated with them. For the purposes of most behavioural calculations, I only use the behaviour random number, but for a few I want to incorporate the entity's random number. Simply averaging them will result in less randomness.

Desired Outcome : Deterministically combine more than one source of entropy

So “Entity A” may have a small random number, and so most of its attributes are skewed small. It's behaviour random number happens to be big, so most of its behaviour attributes are skewed large. When combined the two random numbers deterministically result in $n$, and so some of its behaviour attributes skew towards $n$.

RE: Off-Topic

My question is not specific to game development. The particular use case is. How do cryptographers deterministically combine sources of entropy? I assume they have uses case for this outcome.

  • 2
    $\begingroup$ can't you just hash them and map the hash to 0..1? $\endgroup$ Jan 4 '14 at 23:18
  • $\begingroup$ @CodesInChaos huh, yes I could. Is that the proper way to combine two sources of entropy? [fwiw, it's javascript, so I have Math.random for free, but would need to implement sha1/another hash in code.] $\endgroup$
    – Shad
    Jan 4 '14 at 23:27
  • $\begingroup$ I think the canonical way to combine two numbers uniformly distributed between 0 and n is to just add them mod n. (Eg, XOR is often used for doing so, and it is just bitwise addition mod 2.) In the case of floating point, however, it may introduce precision bias due to precision limitations. $\endgroup$
    – B-Con
    Jan 5 '14 at 0:18
  • 1
    $\begingroup$ cleaned up some comments $\endgroup$
    – mikeazo
    Jan 8 '14 at 14:04
  • 2
    $\begingroup$ Note of dangers of combining many sources of entropy for cryptography: blog.cr.yp.to/20140205-entropy.html $\endgroup$
    – catpnosis
    Feb 10 '14 at 16:35

Set $r = r_1 + r_2 - \mathsf{floor}(r_1 + r_2)$. One (possible) advantage of this approach is that the result will be uniformly random in [0, 1] even if only one of $r_1$, $r_2$ is uniformly random. (Assuming the two values are independent.)

In Python you can also express this as

r = (r1 + r2) % 1.0
  • $\begingroup$ In some languages there is a frac(x) which equals x - floor(x) for non-negative values of x (I'm not sure how it behaves for negative values) $\endgroup$
    – leemes
    Jan 6 '14 at 18:58

Combining two independent random variables that are uniformly distributed between $0$ and $2^n-1$ is rather easy: Both are $n$-bit numbers and every bit is set to $1$ with probability $\frac12$. Therefore, the same is true for their exclusive OR, which will also be uniformly distributed between $0$ and $2^n-1$.

Now, JavaScript's Math.random() pseudo-randomly returns a number in $(0,1)$. Converting that number into an integer $n$-bit integer is easy enough:

var r1 = Math.floor(Math.random() * Math.pow(2,n));

$n$ cannot be greater than 32 in my browser (other implementations may vary) or the resulting integer will always be even.

Now, to combine two of those integers, you can use exclusive OR:

var r = r1 ^ r2;

JavaScript operates on signed 32-bit integers, so $n$ has to be less than 31 to avoid wrapping and signs.

To convert the obtained integer into a value in $(0,1)$, just do this:

r = (r + 1/2) / Math.pow(2,n);
  • $\begingroup$ Awesome, thanks! any reference you can provide regarding the 0 -- 2^n - 1 would be appreciated! $\endgroup$
    – Shad
    Jan 5 '14 at 14:33
  • $\begingroup$ I'm not sure I know what you mean. Are you talking about deriving an integer from a pseudo-randomly generated floating point number or about the uniform distribution of the exclusive OR? $\endgroup$
    – Dennis
    Jan 5 '14 at 18:00
  • $\begingroup$ hah, sry, when I first saw that expression, I was thinking it was something like a trigonometric identity (e.g. 1 - sin^2 x); But I see now it's just a reference to binary order-of-magnitude. $\endgroup$
    – Shad
    Jan 5 '14 at 20:56

If you just want to combine them, you can just add them. You will get an even distribution between 0 < r < 2. An alternative is to get the bytes of the floating point numbers, and XOR them. The result may not be a valid floating point number however. You may also convert the floating point numbers to a string, with arbitrary precision that suits you, and hash them together. Either hash(r1) + hash(r2), or hash(r1+r2), or hash(hash(r1)+hash(r2)), where + is Javascript concatenation for strings. There are public hash libraries for SHA, BCrypt, etc.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.