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?

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)=$

• 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$.

• If $r

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

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

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

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

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

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

StackExchange Computer Science Q#45250, answer score: 3