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

 

 

 

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.