converting random sequence

Question

There is stream (sequence) of uniform random integers $x_i$, each integer in $[0,N-1]$ range, where N is not power of 2.
I need to convert it to sequence of integers [0..255] (bytes), such that uniformity in input numbers results in uniformity in output numbers. And non-uniformity in input number results in some non-uniformity in output numbers.

I am thinking about doing $L=\sum{x_i N^{i}}$ (using multiple-precision library), then representing L in base 256 (taking bytes from L in binary). Is this good ? Is there better method ?

Answer 1

It may depend on what you mean by uniformity, but if you mean random and independent with a uniform distribution then you can probably move on to the next issue.

There is a problem that powers of $N$ are not powers of 256 (unless this is an infinite stream) so with your suggestion you cannot be sure that all your bytes are equally likely. There are ways around this involving rejection sampling: e.g. if $N=258$ you might simply ignore every time $256$ or $257$ appears.

If it is an infinite stream of numbers then $L$ will be infinite and it might be better to look at $\sum{x_i N^{-i}}$ written in base $256$ instead. [This illustrates the uniformity issue: there are apparently numbers which may be normal in one base but not another.]

Be aware that in any method, it is possible (though perhaps with probability zero) that you do not find out which way to round the calculation of some bytes. More realistically there is a positive though small probability you will have to wait a long time to find even a few bytes.

Answer 2

If you have a decent random number generator available, then just choose the least $K=2^k>N$ and do the following at each step: generate a random number from $0$ to $K-1$. If it is greater than $N-1$, accept it and write down its bits just halting the stream for this step. If not, discard it, accept one number from the stream, and write down its bits. This may slow you down twice on the intake speed but you gain a lot from getting rid of arbitrarily precision arithmetic. If there is no bias in the original sequence, the new sequence will have none either. If there was a bias in the original one, it can get diluted a bit but still will be present. Also, you can recover the original sequence from the new one (just read your numbers and drop the excessively high ones).