9.33

We avoid sums and products and throw away parts of the sample space we don't need. At the same time, we want to be efficient in our use of the space.

Conceptually we create a simple tree branching four ways on the first draw from rng04 (throwing away one value) and then drawing two possible values (say low or high) from the second draw (throwing away one value). Each end point is equally likely and draws are independent so this would provide a uniform sample.

#!/usr/bin/env python

import sys, random

def rng04():
    return random.randint(0,4)

# filtered call to rng04
# return 0 1 2 3
def rng03():
    while True:
        i = rng04()
        if i < 4:
            return i

# filtered call to rng04
# return 0 1
# use rng04 instead of rng03 to make analysis easier
def rng01():
    while True:
        i = rng04()
        if i < 4:
            return i % 2

# generate uniform numbers in 0 1 2 3 4 5 6 7
def rng07():
    i = rng03()
    j = rng01()
    return i * 2 + j

if __name__ == "__main__":
    for i in range(10000):
        print rng07()
    sys.exit()

Notice we're not summing we are indexing uniformly on the filtered values. Summing can skew the distribution away from uniform when it generates more than one way to create a specific value or a differing number than for all other values (e.g. rolling two six sided dice, etc.)

Second part of question asks for expected of calls to rng04. The expected number of calls to rng04 if we are filtering calls to rng04 is [math]\displaystyle{ 1/p }[/math] where [math]\displaystyle{ p }[/math] is the probability of accepting a value. For both of the filtered calls we are throwing away one of the five values so the [math]\displaystyle{ p = 0.8 }[/math] and the expected number of calls is [math]\displaystyle{ 1.25 }[/math].

We are making two filtered calls to rng04 in rng07 -- since the expected value of a sum is just the sum of the expected values we know that each call to rng07 has an the expected number of calls to rng04 of [math]\displaystyle{ 2.5 }[/math].

Back to Chapter 9