TADM2E 7.19 - Revision history

Matt: Undo revision 1024 by FuckMatt (talk)

2020-07-29T20:17:01Z

Undo revision 1024 by FuckMatt (talk)

Matt: Undo revision 1038 by Matt (talk)

2020-07-29T20:16:49Z

Undo revision 1038 by Matt (talk)

Matt: Removed spam.

2020-07-29T20:16:25Z

Removed spam.

FuckMatt: Replaced content with "Username:FuckMatt Password:N"

2020-07-29T14:21:24Z

Replaced content with "Username:FuckMatt Password:N"

Matt: Matt moved page TADM2E 7.20 to TADM2E 7.19 over redirect: revert

2020-07-24T15:22:49Z

Matt moved page TADM2E 7.20 to TADM2E 7.19 over redirect: revert

Penis: Penis moved page TADM2E 7.19 to TADM2E 7.20

2020-07-16T23:27:35Z

Penis moved page TADM2E 7.19 to TADM2E 7.20

Algowikiadmin: Recovering wiki

2014-09-11T18:22:44Z

Recovering wiki

Algowikiadmin: Recovering wiki

2014-09-11T18:13:26Z

Recovering wiki

New page

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>
#!/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()
</pre>

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

← Older revision	Revision as of 20:16, 29 July 2020
Line 1:	Line 1:
−	+	Username:FuckMatt
	+	Password:N

← Older revision		Revision as of 20:16, 29 July 2020
Line 1:		Line 1:
−	~~Username:FuckMatt~~	+
−	~~Password:N~~

← Older revision		Revision as of 14:21, 29 July 2020
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.~~	+	Username:FuckMatt
−		+	Password:N
−	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~~
−
−	~~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()~~
−	~~</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>.

← Older revision		Revision as of 20:17, 29 July 2020
Line 1:		Line 1:
−	~~Username~~:~~FuckMatt~~	+	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.
−	~~Password~~:N	+
		+	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
		+
		+	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()
		+	</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>.

← Older revision	Revision as of 15:22, 24 July 2020
(No difference)

← Older revision	Revision as of 23:27, 16 July 2020
(No difference)

@@ 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.
-Conceptually we create a simple tree branching four ways on the first draw from &lt;code&gt;rng04&lt;/code&gt; (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.
+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.
-&lt;pre&gt;
+<pre>
 #!/usr/bin/env python
@@ Line 16: / Line 16: @@
      while True:
          i = rng04()
-         if i &lt; 4:
+         if i < 4:
              return i
@@ Line 25: / Line 25: @@
      while True:
          i = rng04()
-         if i &lt; 4:
+         if i < 4:
              return i % 2
@@ Line 34: / Line 34: @@
      return i * 2 + j
-if __name__ == &quot;__main__&quot;:
+if __name__ == "__main__":
      for i in range(10000):
          print rng07()
      sys.exit()
-&lt;/pre&gt;
+</pre>
-Notice we're not &lt;i&gt;summing&lt;/i&gt; 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.)
+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 &lt;i&gt;expected&lt;/i&gt; of calls to &lt;code&gt;rng04&lt;/code&gt;. The expected number of calls to &lt;code&gt;rng04&lt;/code&gt; if we are filtering calls to &lt;code&gt;rng04&lt;/code&gt; is &lt;math&gt;1/p&lt;/math&gt; where &lt;math&gt;p&lt;/math&gt; is the probability of accepting a value. For both of the filtered calls we are throwing away one of the five values so the &lt;math&gt;p = 0.8&lt;/math&gt; and the expected number of calls is &lt;math&gt;1.25&lt;/math&gt;.
+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 &lt;code&gt;rng04&lt;/code&gt; in &lt;code&gt;rng07&lt;/code&gt; -- since the &lt;i&gt;expected&lt;/i&gt; value of a sum is just the sum of the expected values we know that each call to &lt;code&gt;rng07&lt;/code&gt; has an the expected number of calls to &lt;code&gt;rng04&lt;/code&gt; of &lt;math&gt;2.5&lt;/math&gt;.
+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>.