# How to generate a random integer in interval $[1, 2^n-1]$ from random integer in interval $[0, 2^n-1]$?

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?)

• 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. – Paŭlo Ebermann Dec 15 '12 at 19:02
• @PaŭloEbermann you are correct, I entered the interval incorrectly. Fixed now, thank you. – ampersand Dec 15 '12 at 19:06

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]$.
• 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. – fgrieu Dec 17 '12 at 17:57
• @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. – Dilip Sarwate Dec 17 '12 at 19:16
• 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. – user2460798 Jun 13 '17 at 1:14