1
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ Rejection sampling? $\endgroup$ – Raphael Nov 6 '12 at 11:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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