Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|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
See this answer – leonbloy May 25 at 22:44

Yes, your assessment of modulo os correct.

You can't compress random numbers. Compression works by removing the non-randomness of the input stream. Because it is non-random, you can reconstruct it at the other end.

You could possibly do lossy compression - discard some of the randomness and replace it with pseudo-randomness on the other end that looks close enough for the application. This is effectively what lossy algorithms like JPG or MP3 do.

share|cite|improve this answer

Your Answer


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

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