Problem

Using a function rand7() that returns an integer from 1 to 7 (inclusive) with uniform probability, implement a function rand5() that returns an integer from 1 to 5 (inclusive)

Solution

Method 1 - Using rejection sampling

The idea is to use rand7() to generate numbers from 1 to 7, and map these numbers to values between [1, 5]. We need to ensure that the probabilities remain uniform despite the discrepancy between the range of 7 and 5, and we can use acceptance-rejection method to avoid bias.

Here is the Acceptance-rejection method:

  1. Generate a Uniform Random Number:
    • Call rand7() to get a number.
  2. Reject Unwanted Values:
    • If the number generated by rand7() is within the desired range (1 to 5), return it.
    • If the number is outside the desired range (6 or 7), reject it and retry.

Rationale Behind Rejection Sampling:

  • By rejecting the numbers 6 and 7, we ensure that each number from 1 to 5 has an equal probability of 1/5 once accepted.
  • The rejection rule removes the bias introduced by the additional numbers (6 and 7) which are not needed for rand5().

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

public class RandomGenerator {
	public static int rand7() {
		Random rand = new Random();
		return rand.nextInt(7) + 1; 
	}

	public static int rand5() {
		while (true) {
			int num = rand7();

			if (num <= 5) {
				return num;
			}
		}
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

import random


def rand7():
    return random.randint(1, 7)


def rand5():
    while True:
        num = rand7()
        if num <= 5:
            return num

Complexity

  • ⏰ Time complexity: O(1)
  • 🧺 Space complexity: O(1)