is it possible to implement random(0,1,..,m) with finite calls to random(0,1)?

Question

that is, is there a function $f$ that $Y=f(m,X_1,X_2,...,X_{n(m)})$ where $X_i\sim B(1,\frac{1}{2})$ and $Y\sim U\{0,m\}$?

e.g. when $m=2^k-1$,$n(m)=k$ and $Y=f(2^k-1,X_1,...,X_k)=\Sigma_{i=1}^k{X_i*2^{i-1}}$

Answer 1

It is clearly possible if $m+1 = 2^k$ for some $k \in \mathbb{N}$, by tossing $k$ fair coins. It is impossible for all other $m$ if you require a deterministic procedure that always halts, simply because the number of possibilities for $n$ fair coin tosses is $2^n$ which is only divisible by powers of $2$.

If you want determinism but do not mind approximation then clearly we can just use a large number of coin tosses and divide the possibilities as evenly as possible into $m+1$ groups.

If you want an exactly uniform random selection between $c$ choices, then choose $d \in \mathbb{N}$ such that $2^d \ge c$. Toss $d$ coins and return the choice if the outcome is one of the first $c$ possibilities, where the order is predetermined (perhaps using binary representation). If not, simply repeat the procedure. The probability that you will never get one of the first $c$ possibilities in every round of $d$ tosses will go to $0$ as the number of repeats goes to $\infty$, so this procedure will almost surely halt.