Best way to generate U(1,5) from U(1,3) I am given a uniform integer random number generator $\sim U_3(1,3)$ (inclusive). I would like to generate integers $\sim U_5(1,5)$ (inclusive) using $U_3$. What is the best way to do this?
This simplest approach I can think of is to sample twice from $U_3$ and then use rejection sampling. i.e., sampling twice from $U_3$ gives us 9 possible combinations. We can assign the first 5 combinations to 1,2,3,4,5, and reject the last 4 combinations.
This approach expects to sample from $U_3$ $\frac{9}{5} * 2 = 18/5 = 3.6$ times.
Another approach could be to sample three times from $U_3$. This gives us a sample space of $27$ possible combinations. We can make use of $25$ of these combinations and reject the last 2. This approach expects to use $U_3$ $\frac{27}{25} * 3.24$ times. But this approach would be a little more tedious to write out since we have a lot more combinations than the first, but the expected number of sampling from $U_3$ is better than the first.
Are there other, perhaps better, approaches to doing this?
 A: Your calculations are correct.  The more efficient rejection sampling scheme is to generate three $U_3$ variables, say $U_{3,0}, U_{3,1}, U_{3,2}$ and compute $$S_3 = \sum_{i=0}^2 3^i (U_{3,i} - 1).$$  If $S_3 > 25$, which happens with probability $2/27$, we generate another set (i.e., reject); otherwise, we compute $\lceil S_3/5\rceil$ and this will be distributed as $U_5$.  I don't think this is too computationally expensive to implement compared to the two-variable case.  For instance, if you generate the sample $$(3,1,2),$$ then you can compute $$(3,1,2) \cdot (9,3,1) - 13 = 19,$$ or $$(2,0,1) \cdot (9,3,1) = 19;$$ both are equivalent.  Then since $19 \le 25$, we compute $\lceil 19/5 \rceil = 4$.
A: You approach is on the rigth track.
Notice that in your second proposal you need (in average) 3.24/2 = 1.62 values of $U_3$ to generate one values of $U_5$.
This is already quite near the theorical limit, which is $\log(5)/\log(3) = 1.465$
To attain this bound (with much more complexity of coding) you could use arithmetic coding.
