# Uniform random number generation from random bits

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?

• 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? – Pseudonym Aug 14 '15 at 7:39
• 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. – Yuval Filmus Aug 14 '15 at 8:53
• @YuvalFilmus Can you please explain further? – AccurateEstimate Aug 14 '15 at 21:29
• @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. – Yuval Filmus Aug 14 '15 at 21:36

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.

$rand(n)=$

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}$

• 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). – Maarten Bodewes Mar 1 '17 at 13:02