1
$\begingroup$

Given a pseudo random number generator rand5() that generates a random integer in the set [0,1,2,3,4], how would someone use this to generate a function rand7() that outputs [0,1,2,3,4,5,6] with equal probability.

I was thinking of approaching it this way: reduce the problem to generate number from 0 to 6 using a coin.

We can represent [0,1,2,3,4,5,6] using bit-wise from 000 to 111.
Selecting each bit from LSB to MSB can be done using tossing a coin.
However, if we continue in this fashion from LSB to MSB then we
can get all bits as 111 which is decimal 7. So, in the case of MSB
if we get 1 then discarding it and starting again should give
the result? Right?

Reducing the problem from rand5() to coin can be done in this way: if the number is 0,2 then we can consider it as head and getting 1,3 can be considered as tail.

Is my solution right?

$\endgroup$
  • 1
    $\begingroup$ What do you think? If you feel your idea works, make an argument that proves it. $\endgroup$ – quicksort Feb 1 '17 at 4:40
  • $\begingroup$ @quicksort: each bit has probability of 1/2 being set or unset. So, each number in the range [0,1,2,3,4,5,6] has probability of 1/8 being selected. $\endgroup$ – noman pouigt Feb 1 '17 at 5:34
  • $\begingroup$ So you are using 3 x rand5 calls and with probability 1/5 reject and get new 3 x rand5 calls? $\endgroup$ – Evil Feb 1 '17 at 6:56
  • $\begingroup$ @Evil In order to convert from rand5 to a coin the probability works like this: 1/5 is the probability of getting each number and if the undesired number comes we start again. I think it is called rejection sampling where the probability is not even considered when a undesired result comes as if that event has not even happened. $\endgroup$ – noman pouigt Feb 1 '17 at 7:23
  • $\begingroup$ Ok. I know about the rejection sampling, the odd thing is giving probability 1/8 if by rejection you do not count it (so for 7 numbers it is 1/7). I have asked about discarding - do you discard all three samples or only last one? are you happy with that much samples used or this is not a concern? $\endgroup$ – Evil Feb 1 '17 at 8:57
0
$\begingroup$

(For some reason, this old question came up first)
rand5()+rand5()*5 would give numbers 0-24, each with a probability of 1/25. You could use the first 21 of these to return 0-6 with equal probabililty.
Likewise, rand2()+rand2()*2+rand2*4) gives numbers 0-7, each with a probability of 1/8. You could use the first 7 of these to return 0-6 with equal probability.
In pseudocode:

function rand7a() {
  do { rand7 = rand5() + rand5()*5 } while (rand7 >= 21);
  return rand7 mod 7; 
}
function rand7b() {
  do { rand7 = rand2() + rand2()*2 + rand2()*4 } while ( rand7 == 7);
  return rand7;
}

EDIT: Elaboration:
1st approach:
rand2() in binary is 000 or 001 with 50-50 probability.
rand2()*2 is 000 or 010 with 50-50 probability.
rand2()*4 is 000 or 100 with 50-50 probability.
So the sum is binary xxx where each x has a 50-50 probability of 0 or 1; so each 000 to 111 has a probablilty of 1/8.

2nd approach: going through each of the 8 possibilities of the 3 rand2()s:
0+0+0 or 1+0+0 or 0+2+0 or 1+2+0 or 0+0+4 or 1+0+4 or 0+2+4 or 1+2+4
all of these with equal probablilty 1/8.

$\endgroup$
  • $\begingroup$ Rand2 + rand2*2 +rand2*4 how does this give a number in the range 0 to 7 with equal probability? Can you elaborate? $\endgroup$ – noman pouigt Jun 10 '18 at 20:00
  • $\begingroup$ @nomanpouigt Think of the number written in binary. A number in the range 0-7 has three bits and the answer chooses each bit independently, uniformly at random. $\endgroup$ – David Richerby Jun 10 '18 at 20:28
  • $\begingroup$ @noman pouigt I EDIT'ed in an elaboration. Thanks. $\endgroup$ – dcromley Jun 10 '18 at 20:35
1
$\begingroup$

It can work, but there is no need for an intermediate step: just convert from base 5 to base 7, picking the least significant base-7 digit. The algorithm is as follows:

  1. Use rand(5) to generate a and b; let n = 5 * a + b.
  2. If n >= 21, discard n and go back to step 1, else go to step 3.
  3. Return n mod 7.
$\endgroup$
  • $\begingroup$ Slightly more efficient: If n ≥ 21, subtract 21 to get another 0 ≤ a < 4, get 0 ≤ b < 5, transform into a number n from 0 to 19. If less than 14 then return n modulo 7, otherwise subtract 14 to get another 0 ≤ a < 6 and so on and so on. $\endgroup$ – gnasher729 Jun 11 '18 at 22:10
  • $\begingroup$ @gnasher729: Indeed. It's the equivalent of long division, base 5. Although I think that the added complexity, and added operations, can take more time than getting, once in a while, a new rand(). $\endgroup$ – jose_castro_arnaud Jun 13 '18 at 18:27

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.