3
$\begingroup$

I need to generate random number in a given interval using random bits. For example, If I want to generate a random number between 1 to 6, inclusive, I can concatenate three random bits which gives me a possible range of 000 to 111 (0 to 7), inclusive. My intuition says after concatenating 3 random bits, if the result falls between 000 and 101, inclusive, I can just return that number plus 1 (which essentially gives me a number between 1 and 6, inclusive). If I get 110 or 111 (6 or 7) after concatenating 3 random bits, I can retry again until I the number generated is in my desired range. How can I prove (or disprove) that the number I returned is indeed random?

$\endgroup$
  • 1
    $\begingroup$ Well it's obviously "random". What you're actually trying to prove is that the frequency distribution is flat (that is, there's an equal probability of getting each number between 1 and 6). Does that help? $\endgroup$ – Pseudonym Aug 14 '15 at 7:39
  • $\begingroup$ If you want many of these numbers, they should cost you only $\log_2 6$ random bits on average, rather than $3 \cdot \frac{8}{6} = 4$ with your current algorithm. $\endgroup$ – Yuval Filmus Aug 14 '15 at 8:53
  • $\begingroup$ @YuvalFilmus Can you please explain further? $\endgroup$ – AccurateEstimate Aug 14 '15 at 21:29
  • $\begingroup$ @AccurateEstimate If you're interested, you can ask a new question. It also might be the case that a similar question has been asked before on this site. $\endgroup$ – Yuval Filmus Aug 14 '15 at 21:36
3
$\begingroup$

First we need reduce our rand(from, to) function just to rand(n) = returns uniformly random number from [0, n); and later we will be able construct original function as rand(from, to) = rand(to - from) + to.

$rand(n)=$

  1. Take $k$ random bits such where $n \le 2 ^ k$ (actually we can choose any $k$ that satisfy this condition, but in practice make sense to choose minimal among all possible $k$) and interpret this sequence as binary integer $r$.
  2. If $r < n$ return $r$ else go to step 1.

Now let's calculate probability that some number $r$ will be choosen:

  1. Probability that algorithm will stop after one iteration is $\frac{n}{m}$, probability that we will reach 2nd iteration is $\frac{m-n}{m}$; more generally probability that algorithm will reach $step$ interation is $Pr(step) = (\frac{m-n}{m}) ^ {step - 1}$.

  2. Probabilities that algorithm will return some $r$ on 1st iteration:

$ Pr(0) = \frac{1}{m}\\ Pr(1) = \frac{1}{m}\\ Pr(2) = \frac{1}{m}\\ ...\\ Pr(n - 1) = \frac{1}{m}\\ $

  1. Probabilities that algorithm will return some $r$ on 2nd iteration:

$ Pr(0) = \frac{m-n}{m}*\frac{1}{m}\\ Pr(1) = \frac{m-n}{m}*\frac{1}{m}\\ Pr(2) = \frac{m-n}{m}*\frac{1}{m}\\ ...\\ Pr(n - 1) = \frac{m-n}{m}*\frac{1}{m}\\ $

  1. Probabilities that algorithm will return some $r$ on $step$ iteration:

$ Pr(0) = (\frac{m-n}{m}) ^ {step - 1}*\frac{1}{m}\\ Pr(1) = (\frac{m-n}{m}) ^ {step - 1}*\frac{1}{m}\\ Pr(2) = (\frac{m-n}{m}) ^ {step - 1}*\frac{1}{m}\\ ...\\ Pr(n - 1) = (\frac{m-n}{m}) ^ {step - 1}*\frac{1}{m}\\ $

  1. And probability that some $r$ will be choosen (after any number of interations) will be the same regardless of $r$:

$ Pr(r) = \frac{1}{m} + \frac{m-n}{m}*\frac{1}{m} + ... + (\frac{m-n}{m}) ^ s*\frac{1}{m} + ... = \frac{1}{m}\sum\limits_{s=0}^\infty(\frac{m-n}{m}) ^ s = \frac{1}{m} \frac{1}{1 - \frac{m - n}{m}} = \frac{1}{m} \frac{m}{n} = \frac{1}{n} $

$\endgroup$
  • $\begingroup$ Note that this is not necessarily the most efficient option. It makes more sense to use a somewhat larger $K$ (say 8 bits larger, one byte), then find out how many times $n$ fits in $K$ (let's call this $x$ and use $m = x * n$). If the random number $r$ is $m$ or higher, then regenerate $r$, otherwise return $r \bmod n$. Voila, less chance of having to generate $r$ again and again. You may want to optimize further for $n = 2^y$ and yes, for larger numbers there are even more efficient methods (I know I just programmed one - checking for prior art). $\endgroup$ – Maarten Bodewes Mar 1 '17 at 13:02

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.