Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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.

share|improve this question
    
Closely related question, maybe even a duplicate? –  Raphael Nov 6 '12 at 11:18
add comment

1 Answer

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$

share|improve this answer
    
Rejection sampling? –  Raphael Nov 6 '12 at 11:17
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.