# Difference between revisions of "TADM2E 7.19"

(Recovering wiki) |
(Recovering wiki) |
||

Line 1: | Line 1: | ||

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. | 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 | + | 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> | |

#!/usr/bin/env python | #!/usr/bin/env python | ||

Line 16: | Line 16: | ||

while True: | while True: | ||

i = rng04() | i = rng04() | ||

− | if i | + | if i < 4: |

return i | return i | ||

Line 25: | Line 25: | ||

while True: | while True: | ||

i = rng04() | i = rng04() | ||

− | if i | + | if i < 4: |

return i % 2 | return i % 2 | ||

Line 34: | Line 34: | ||

return i * 2 + j | return i * 2 + j | ||

− | if __name__ == | + | if __name__ == "__main__": |

for i in range(10000): | for i in range(10000): | ||

print rng07() | print rng07() | ||

sys.exit() | sys.exit() | ||

− | + | </pre> | |

− | Notice we're not | + | 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 | + | 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 | + | 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>. |

## Latest revision as of 18:22, 11 September 2014

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 $ 1/p $ where $ p $ is the probability of accepting a value. For both of the filtered calls we are throwing away one of the five values so the $ p = 0.8 $ and the expected number of calls is $ 1.25 $.

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 $ 2.5 $.