Generate a uniform random numbers in $O(1)$ Suppose you have access to a random number generator $G()$ that generates uniform random numbers in $\{0,\cdots,n-1\}$. (Here, $n$ is given and cannot be changed.)
How do we generate a uniform random number in $\{0,\cdots,m-1\}$ for $m\leq n$? We require that we can only call $G()$ $O(1)$ times in expectation.
My effort:
Suppose $n=km+r$, where $k$ and $r$ are integers. Call $G()$. If $G()\leq km$, return $G()\mod m$; otherwise, call $G()$ again.
But in expectation, this will call $G()$ $O(\frac{n}{n-r})$ times, and $r$ can be $1,\cdots,m-1$.
Since $r &lt; m \leq n$, necessarily $k \geq 1$ and so $n - r = km \geq m &gt; r$. In particular, $r &lt; n/2$ and so $n-r &gt; n/2$. In total, we conclude that $n/(n-r) &lt; 2$.