TADM2E 7.19

From Algorithm Wiki
Revision as of 18:13, 11 September 2014 by Algowikiadmin (Talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

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 <code>rng04</code> (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.

<pre>

  1. !/usr/bin/env python

import sys, random

def rng04():

   return random.randint(0,4)
  1. filtered call to rng04
  2. return 0 1 2 3

def rng03():

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

def rng01():

   while True:
       i = rng04()
       if i < 4:
           return i % 2
  1. 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()

</pre>

Notice we're not <i>summing</i> 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 <i>expected</i> of calls to <code>rng04</code>. The expected number of calls to <code>rng04</code> if we are filtering calls to <code>rng04</code> is <math>1/p</math> where <math>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>p = 0.8</math> and the expected number of calls is <math>1.25</math>.

We are making two filtered calls to <code>rng04</code> in <code>rng07</code> -- since the <i>expected</i> value of a sum is just the sum of the expected values we know that each call to <code>rng07</code> has an the expected number of calls to <code>rng04</code> of <math>2.5</math>.