I need to generate random number in a given interval using random bits. For example, If I want to generate a random number between 1 to 6, inclusive, I can concatenate three random bits which gives me a possible range of 000 to 111 (0 to 7), inclusive. My intuition says after concatenating 3 random bits, if the result falls between 000 and 101, inclusive, I can just return that number plus 1 (which essentially gives me a number between 1 and 6, inclusive). If I get 110 or 111 (6 or 7) after concatenating 3 random bits, I can retry again until I the number generated is in my desired range. How can I prove (or disprove) that the number I returned is indeed random?

  • 1
    $\begingroup$ Well it's obviously "random". What you're actually trying to prove is that the frequency distribution is flat (that is, there's an equal probability of getting each number between 1 and 6). Does that help? $\endgroup$
    – Pseudonym
    Aug 14, 2015 at 7:39
  • $\begingroup$ If you want many of these numbers, they should cost you only $\log_2 6$ random bits on average, rather than $3 \cdot \frac{8}{6} = 4$ with your current algorithm. $\endgroup$ Aug 14, 2015 at 8:53
  • $\begingroup$ @YuvalFilmus Can you please explain further? $\endgroup$ Aug 14, 2015 at 21:29
  • $\begingroup$ @AccurateEstimate If you're interested, you can ask a new question. It also might be the case that a similar question has been asked before on this site. $\endgroup$ Aug 14, 2015 at 21:36

1 Answer 1


First we need reduce our rand(from, to) function just to rand(n) = returns uniformly random number from [0, n); and later we will be able construct original function as rand(from, to) = rand(to - from) + to.


  1. Take $k$ random bits such where $n \le 2 ^ k$ (actually we can choose any $k$ that satisfy this condition, but in practice make sense to choose minimal among all possible $k$) and interpret this sequence as binary integer $r$.
  2. If $r < n$ return $r$ else go to step 1.

Now let's calculate probability that some number $r$ will be choosen:

  1. Probability that algorithm will stop after one iteration is $\frac{n}{m}$, probability that we will reach 2nd iteration is $\frac{m-n}{m}$; more generally probability that algorithm will reach $step$ interation is $Pr(step) = (\frac{m-n}{m}) ^ {step - 1}$.

  2. Probabilities that algorithm will return some $r$ on 1st iteration:

$ Pr(0) = \frac{1}{m}\\ Pr(1) = \frac{1}{m}\\ Pr(2) = \frac{1}{m}\\ ...\\ Pr(n - 1) = \frac{1}{m}\\ $

  1. Probabilities that algorithm will return some $r$ on 2nd iteration:

$ Pr(0) = \frac{m-n}{m}*\frac{1}{m}\\ Pr(1) = \frac{m-n}{m}*\frac{1}{m}\\ Pr(2) = \frac{m-n}{m}*\frac{1}{m}\\ ...\\ Pr(n - 1) = \frac{m-n}{m}*\frac{1}{m}\\ $

  1. Probabilities that algorithm will return some $r$ on $step$ iteration:

$ Pr(0) = (\frac{m-n}{m}) ^ {step - 1}*\frac{1}{m}\\ Pr(1) = (\frac{m-n}{m}) ^ {step - 1}*\frac{1}{m}\\ Pr(2) = (\frac{m-n}{m}) ^ {step - 1}*\frac{1}{m}\\ ...\\ Pr(n - 1) = (\frac{m-n}{m}) ^ {step - 1}*\frac{1}{m}\\ $

  1. And probability that some $r$ will be choosen (after any number of interations) will be the same regardless of $r$:

$ Pr(r) = \frac{1}{m} + \frac{m-n}{m}*\frac{1}{m} + ... + (\frac{m-n}{m}) ^ s*\frac{1}{m} + ... = \frac{1}{m}\sum\limits_{s=0}^\infty(\frac{m-n}{m}) ^ s = \frac{1}{m} \frac{1}{1 - \frac{m - n}{m}} = \frac{1}{m} \frac{m}{n} = \frac{1}{n} $

  • 1
    $\begingroup$ Note that this is not necessarily the most efficient option. It makes more sense to use a somewhat larger $K$ (say 8 bits larger, one byte), then find out how many times $n$ fits in $K$ (let's call this $x$ and use $m = x * n$). If the random number $r$ is $m$ or higher, then regenerate $r$, otherwise return $r \bmod n$. Voila, less chance of having to generate $r$ again and again. You may want to optimize further for $n = 2^y$ and yes, for larger numbers there are even more efficient methods (I know I just programmed one - checking for prior art). $\endgroup$ Mar 1, 2017 at 13:02

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.