For a project I am working on, I have access to a CSPRNG that outputs a random integer in the interval $[0, 2^n-1]$ for any integer $n$ greater than 0. I cannot use the zero values, so I have my RNG code in a while loop that runs until the random number is !==0. For small $n$ it is very likely that the while loop will run more than once, even more than twice (for $n=8$, the probability is $1/65536$). While this is not the bottleneck in my program, I want to eliminate the while loop and replace it with a linear transformation on the the generated random integer to get the integers I need in $[1, 2^n-1]$.

Is there a transformation that can be performed on the interval $[0, 2^n-1]$ to yield integers in $[1, 2^n-1]$ while retaining the uniform distribution of the random numbers?

(Would this be better posted in math.se?)

  • $\begingroup$ Are you sure that your PRNG really has an output range of $2^{n-1} + 1$ different values (e.g. that $2^{n-1}$ itself is a possible value)? This looks a bit unusual. $\endgroup$ Commented Dec 15, 2012 at 19:02
  • $\begingroup$ @PaŭloEbermann you are correct, I entered the interval incorrectly. Fixed now, thank you. $\endgroup$
    – ampersand
    Commented Dec 15, 2012 at 19:06

2 Answers 2


Assuming that $n > 1$ so as to avoid a trivial special case, there is no function $g(\cdot)$ (linear or otherwise) that will transform a discrete random variable $X$ uniformly distributed on $\{0,1, 2, \ldots, 2^{n}-1\}$ into a discrete random variable $Y$ uniformly distributed in $\{1, 2, \ldots, 2^{n}-1\}$. This is because each value of $X$ has probability $2^{-n}$ attached to it, and this gets mapped onto the $Y$ value $g(X)$. Thus, for any $m \in \{1, 2, \ldots, 2^{n}-1\}$, $P\{Y=m\}$ is necessarily an integer multiple of $2^{-n}$ including, possibly, a zero multiple. It follows that the best one could do is to get a random variable $Y$ that takes on all values in $\{1, 2, \ldots, 2^{n}-1\}$ except one with equal probability $2^{-n}$, and this exceptional value occurs with probability $2\times2^{-n}=2^{-(n-1)}$.

On the other hand, if $X$ were a continuous random variable uniformly distributed on the interval $[0,2^n-1]$, the answer would be easy: $Y = 1+\frac{2^n-2}{2^n-1}X$ is a continuous random variable uniformly distributed on the interval $[1,2^n-1]$.

  • $\begingroup$ You must exclude $n=1$, because it is possible to generate a $Y$ taking the single value $1=2^1-1$ from pretty much anything. Also in "$n\in\{1,2,\ldots,2^{n}-1\}$" the left $n$ is not meant to be the same as the right $n$. My demonstration would be that in order for a suitable mapping to exist, $2^n-1$ (cardinality of destination) must divide $2^n$ (cardinality of source), and that's impossible for $n>1$. I upvoted nevertheless. $\endgroup$
    – fgrieu
    Commented Dec 17, 2012 at 17:57
  • $\begingroup$ @fgrieu Thanks for the comment about $n > 1$, the bad choice of notation, and the upvote. I have edited my answer to incorporate your corrections. $\endgroup$ Commented Dec 17, 2012 at 19:16
  • $\begingroup$ Regarding "no function", wouldn't a function which recursively call itself anytime it would have otherwise returned 0, return the remaining values with uniform probability? For $n=8$ each nonzero value would be returned with probability $\frac18+\frac1{64}+...\frac1{8^n}$ as $n\rightarrow \infty$. That infinite sum is $\frac17$. Granted that would be more inefficient than just the while. $\endgroup$ Commented Jun 13, 2017 at 1:14

No, there is no way to do it the way you want.

Just stick with the while loop. There is nothing wrong with using a while loop. As you seem to realize, the while loop will almost never execute more than one iteration, so it will perform extremely well. You don't say why you find the straightforward solution (the while loop) problematic, so I'm sticking with my answer: just use the while loop.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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