Suppose that you have a function that you can use to generate uniformly distributed random numbers between \(1\) and \(5\). How can you use the above function to generate uniformly distributed random numbers between \(1\) and \(7\)?

The key to solving puzzles such as the one above is to first recognize that if we can somehow generate \(7\) equally likely outcomes then we can use each one of these \(7\) outcomes to output one of the integers between \(1\) and \(7\) as shown below:

$$ \text{Outcome}\ 1 \longrightarrow 1$$

$$ \text{Outcome}\ 2 \longrightarrow 2$$

$$ \text{Outcome}\ 3 \longrightarrow 3$$

$$ \text{Outcome}\ 4 \longrightarrow 4$$

$$ \text{Outcome}\ 5 \longrightarrow 5$$

$$ \text{Outcome}\ 6 \longrightarrow 6$$

$$ \text{Outcome}\ 7 \longrightarrow 7$$

So, how can we generate \(7\) equally likely outcomes when you have a function that only outputs \(5\) equally likely outcomes. The trick is to change the space of outcomes. One way to change the outcome space is to draw two random numbers uniformly distributed between \(1\) and \(5\). The outcome space when we draw two numbers is as follows:

$$\{ (1, 1), (1, 2), (1, 3), (1, 4), (1, 5), \\ (2, 1), (2, 2), (2, 3), (2, 4), (2, 5), \\ (3, 1), (3, 2), (3, 3), (3, 4), (3, 5), \\ (4, 1), (4, 2), (4, 3), (4, 4), (4, 5), \\ (5, 1), (5, 2), (5, 3), (5, 4), (5, 5) \}$$

Of course, now we have \(25\) equally likely outcomes and not \(7\). But, what if we were to map \(7\) of the above outcomes to our desired numbers and ignore the others. In other words, our random number generator to draw random numbers between \(1\) and \(7\) does the following:

$$ (1, 1) \longrightarrow 1$$

$$ (1, 2) \longrightarrow 2$$

$$ (1, 3) \longrightarrow 3$$

$$ (1, 4) \longrightarrow 4$$

$$ (1, 5) \longrightarrow 5$$

$$ (2, 1) \longrightarrow 6$$

$$ (2, 2) \longrightarrow 7$$

If we obtain any outcome apart from the ones listed above we try again till we obtain one of the above outcomes. All the above outcomes are equally likely and there are \(7\) outcomes. Thus, one would expect the above procedure to generate uniformly distributed random numbers between \(1\) and \(7\).

We could go through the math to convince ourselves but writing a simulation is another way to validate the above intuition. The plot below shows the percentage of times each number occurs in a simulation where we use the above procedure to generate numbers between \(1\) and \(7\). Note that the chances of obtaining any of these outcomes is \(\frac{1}{7} \approx 0.143\). Thus, we have strong evidence that the procedure does generate numbers uniformly between \(1\) and \(7\). For those interested, the Python code used to generate the plot is at the end of the post.

A related problem to think about: How can we generate uniformly distributed numbers between \(1\) and \(30\) if we have access to a function that only gives us random numbers between \(1\) and \(5\)?

import random import matplotlib.pyplot as plt import seaborn as sns def draw_histogram(draws): ax = sns.barplot(x=draws, y=draws, estimator=lambda x: len(x) / len(draws) * 100) ax.set_xlabel('Number') ax.set_ylabel('Percentage') ax.set_ylim(0, 100) for p in ax.patches: ax.annotate("%.0f" % p.get_height() + '%', (p.get_x() + p.get_width() / 2., p.get_height() + 3), ha='center', va='center', fontsize=12, color='black', rotation=0, xytext=(0, 0), textcoords='offset points') def generate_rand_between_1_and_7(): draw = None while draw is None: draw_1 = random.randint(1, 5) draw_2 = random.randint(1, 5) draw_sequence = (draw_1, draw_2) if draw_sequence == (1, 1): draw = 1 elif draw_sequence == (1, 2): draw = 2 elif draw_sequence == (1, 3): draw = 3 elif draw_sequence == (1, 3): draw = 3 elif draw_sequence == (1, 4): draw = 4 elif draw_sequence == (1, 5): draw = 5 elif draw_sequence == (2, 1): draw = 6 elif draw_sequence == (2, 2): draw = 7 else: pass return draw if __name__ == '__main__': random.seed(42) no_of_draws = 10000 draws_between_1_and_7 = [] for _ in range(no_of_draws): draw = generate_rand_between_1_and_7() draws_between_1_and_7.append(draw) draw_histogram(draws_between_1_and_7) plt.savefig('histogram_of_draws.png', bbox_inches='tight')