Question: theoretical compression ratio limit

[lemire]

Question: theoretical compression ratio limit

[lemire]

What is rand() in this context?

[marsupialtail]

let's say it is a random number with uniform or normal distribution from 0 to 10k

[searchivarius]

@marsupialtail with most lightweight integer encoding schemes the lower bound is equal to the number of binary digits necessary to encode the number. However, this doesn't include the length of the code. So if the length is a random variable X, the mean of this variable is a lower bound for the average number of bits per code (if I don't get something wrong). It will be about log_2 10K / 2 for uniform. What is a normal distribution is not clear since we cannot have negative numbers for most encoding schemes.

There's also some overhead (to encode code length) that might be sometimes tricky to compute.

However, this number, is not an absolute theoretical minimum, because it depends on the encoding scheme and statistical properties of the data, e.g., on repetitiveness. If you have a single number repeated gazillion of times, little space is needed.

[lemire]

Let me add that by information theoretical arguments, it is a impossible to consistently store sequences of random integers between 0 and N using less than log N bits per integer on average. If you beat this, either you do not use true random integers or you have made a mistake.

In effect, random numbers cannot be compressed… and that’s a tautology because that is one definition of random (cannot be compressed).

[searchivarius]

Only if they are independent. If independence isn't there, an easy counter example:
generate a random number in [0, N] then repeat it a random number [1, M] times.
repeat this procedure many times.
Although the numbers are random, this procedure generates highly compressible sequences when the median number of repetitions is high.