# Random Number Puzzle

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')