2
$\begingroup$

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$.

$\endgroup$
1
  • $\begingroup$ Welcome to COMPUTER SCIENCE @SE. Can you give an upper limit for $r$ in terms of $n$? $\endgroup$
    – greybeard
    Oct 4, 2020 at 8:08

1 Answer 1

3
$\begingroup$

Since $r < m \leq n$, necessarily $k \geq 1$ and so $n - r = km \geq m > r$. In particular, $r < n/2$ and so $n-r > n/2$. In total, we conclude that $n/(n-r) < 2$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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