# Generating uniformly distributed random numbers using a coin

You have one coin. You may flip it as many times as you want.

You want to generate a random number $r$ such that $a \leq r < b$ where $r,a,b\in \mathbb{Z}^+$.

Distribution of the numbers should be uniform.

It is easy if $b -a = 2^n$:

r = a + binary2dec(flip n times write 0 for heads and 1 for tails)


What if $b-a \neq 2^n$?

This method is useful in these kinds of situations: you want to pick some random object from a set (a random integer in the set $[a,b]$ in your case), but you don't know how to do that, but you can pick some random object from a larger set containing the first set (in your case, $[a, 2^k + a]$ for some $k$ such that $2^k + a \ge b$; this corresponds to $k$ coin flips).
In such a scenario, you just keep picking elements from the bigger set until you randomly pick an element in the smaller set. If your smaller set is big enough compared to your larger set (in your case, $[a, 2^k + a]$ contains at most twice as many integers as $[a,b]$, which is good enough), this is efficient.