Assume the envelope contents are distributed arbitrarily on [A,+infinity) where A is some large number. Let f(x)=1/x (the values for x<1 don’t matter). Then the expected benefit of Thrun’s algorithm is always 1⁄4, even though the difference in f(x) between the values of any two envelopes is less than 1/A. To convince yourself of that, work out the proof yourself or run a computational experiment:
from random import random
n = 100000
thrun = 0
chance = 0
for i in range(n):
smaller = 2+3*random() # replace this line with anything
selected,other = smaller,2*smaller
if random() > 0.5:
selected,other = other,selected
chance += (selected if (random() > 0.5) else other)
thrun += (selected if (random() > 1/selected) else other)
print (thrun-chance)/n
You’re not missing anything, but the variance is quite high, you’ll need many more samples. Or you could try writing a program that converges faster, I’m a total newbie at these things.
I tried to prove it, and I am getting an expected benifet of 1⁄4, and I am worried that I am making a mistake related to reording the terms of a non absolutely converging series.
If you are right, you could do better with f(x) = 2/x, and the values for x < 2 don’t matter.
Assume the envelope contents are distributed arbitrarily on [A,+infinity) where A is some large number. Let f(x)=1/x (the values for x<1 don’t matter). Then the expected benefit of Thrun’s algorithm is always 1⁄4, even though the difference in f(x) between the values of any two envelopes is less than 1/A. To convince yourself of that, work out the proof yourself or run a computational experiment:
Replacing “3” with “10000″ gets me varying results, mostly negative at a glance. What am I missing?
You’re not missing anything, but the variance is quite high, you’ll need many more samples. Or you could try writing a program that converges faster, I’m a total newbie at these things.
I tried to prove it, and I am getting an expected benifet of 1⁄4, and I am worried that I am making a mistake related to reording the terms of a non absolutely converging series.
If you are right, you could do better with f(x) = 2/x, and the values for x < 2 don’t matter.
Sorry, I mistyped the comment, fixed it immediately but I guess you saw the old version. It’s 1⁄4 of course.
I’m not sure what remains of Eliezer’s original point now...
Ah, that old confounder in the rhythm of disagreement: a smart person who appears to disagree with you might not have said what they meant to say. ;)