Stochastical algorithm

Question

We have a stochastic random source. This gives the bit $0$ (or $1$) with probability $1/2$. We want to generate a uniform distribution on the set S = $\{0, 1,..., n-1\}$.

Which algorithm gives with probability $1/n$ the value $i\in S$. And how many bits are needed.

Answer 1

If $n$ is a power of two, then you can simply determine the value $i$ by determine bit per bit in the binary representation. So if $n=8$ then you ask your source 3 times. Suppose you get as result $1,1,0$ then you would map this event to the event that you have selected $i\leftarrow\text{bin}(110)=6$. Clearly you need $\log n$ bits.

If $n$ is not a power of two, then things a are more tricky You can definitely can get an approximate uniform distribution, if you follow the method above. Say you sample $k$ bits, and you get the $k$-digit binary number $b$, then you can pick $$i\leftarrow \frac{b}{2^k}n.$$

The more bits you sample, the closer you approach the uniform distribution. I am sure there are more involved methods for case wehere $n\neq 2^k$