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