Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I've been thinking about ways to compress the output from a (supposedly) random number generator. Let's assume for a moment that my computer can produce high-quality random numbers. I'm certainly not an expert in this field, so please correct me wherever.

Let's say I need random numbers between zero and 199 inclusive, however I can only read a minimum of a byte at a time from the RNG, so I use some compression function to reduce the 256 possible values of the byte to 200 different values. I'm considering using the modulo operation as a compression function, in that the modulo operation will cause a wraparound of the value should it exceed 199.

I think I've immediately spotted a flaw with using modulo in that it's twice as likely for the values 0-55 to occur. Would you say this assessment of the modulo operation is correct, or is there something about the properties of random numbers (entropy or whatever) that means that this doesn't matter? Also, if not modulo, could you suggest a good method of reducing the number of possible values of a RNG which effectively preserves their 'randomness'?

share|improve this question
    
Well, if you have a random variable $\xi$ with a distribution $\mu_\xi$ and you apply some function on $\xi$, e.g. $$ f(\xi) = \xi\mod{200} $$ then the distribution of $f(\xi)$ is in general different from $\xi$, and is called an image distribution (under the map $f$). As you correctly noticed, in case $\xi$ is uniformly distributed over $[0;255]$, any number from $[0;55]$ is 2 times more probable than any one from $[56;199]$. –  Ilya Apr 4 '13 at 12:10
    
One method is to throw away 56 of the possible byte values. The remaining 200 will be random (well, as random as the RNG allows). On average, you'll have to produce $1.28$ bytes to get one you can use. –  Gerry Myerson Apr 4 '13 at 12:25
    
@GerryMyerson Would dividing the output of the RNG by 1.28 and ensuring that the result was rounded to the nearest integer have this effect? –  Doddy Apr 4 '13 at 12:35
    
No! That would make some of the 200 values twice as likely as others. –  Gerry Myerson Apr 5 '13 at 12:03
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.