It seems that Eliezer’s point is not best expressed in terms of differentials. The benifet of the algorithm depends on the difference in the monotonic function between the values of each the envelopes. There is only a finite amount of difference available to distribute over the domain, of infinite measure, of the function, and for any epsilon greater than 0, for all but a finite measure of the domain, the difference in the function between possible pairs of values for the envelopes will be less than epsilon. So if you really have no information constraining the distribution of values for the envelopes to use to allocate the difference in function effectively, the expected benifet of the algorithm is 0.
Edit: Actually, that argument doesn’t hold on its own, because the value of switching to the bigger envelope isn’t constant, it depends on the size of the envelope. However, in the problem as stated, I don’t think the value of switching grows fast enough. I need to think about it more.
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.
It seems that Eliezer’s point is not best expressed in terms of differentials. The benifet of the algorithm depends on the difference in the monotonic function between the values of each the envelopes. There is only a finite amount of difference available to distribute over the domain, of infinite measure, of the function, and for any epsilon greater than 0, for all but a finite measure of the domain, the difference in the function between possible pairs of values for the envelopes will be less than epsilon. So if you really have no information constraining the distribution of values for the envelopes to use to allocate the difference in function effectively, the expected benifet of the algorithm is 0.
Edit: Actually, that argument doesn’t hold on its own, because the value of switching to the bigger envelope isn’t constant, it depends on the size of the envelope. However, in the problem as stated, I don’t think the value of switching grows fast enough. I need to think about it more.
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. ;)