= 27d567bc2d48d9f40e9ccc20ea370b15)
Luke_A_Somers comments on [SEQ RERUN] The Rhythm of Disagreement - Less Wrong
You are viewing a comment permalink. View the original post to see all comments and the full post content.
= 783df68a0f980790206b9ea87794c5b6)
Loading…= b715d02e85f7b3b4ae65ca3d3e450868)
Subscribe to RSS Feed
Powered by Reddit
= f037147d6e6c911a85753b9abdedda8d)
You are viewing a comment permalink. View the original post to see all comments and the full post content.
Comments (9)
I still have no clue how Thrun's method could be correct in the ideal case. He's relying on having some clue as to how much money there is in the envelopes.
Here's a restatement of the problem that makes my objection clearer:
"Hi again."
"Omega, my pal! Thanks for the million dollars. That was pretty sweet."
"I've got another offer for you, my fairy AI-son. Here is a box with some amount of Gxnthrzian currency. It's yours if you do one little thing for me."
"Umm. How could I spend that?"
"They will make contact with Earth in two weeks. It'll be awesome. Anyway, so that little thing - here's a document. Sort of a Gxnthrzian IOU. Just scratch one of those two circles, and the box is yours. And don't squint - you can't actually read it with your current technology level, and of course it's in an alien language you don't know."
I take the circular sheet of plastic, but say, "Waaait. How much is the IOU for?"
"The IOU is for one third as much as money in the box. I'll handle the payment for you - no fee."
I turn the circle around and arbitrarily select one of the circles.
Omega interrupts me from scratching it. "If you pick that circle, then after the IOU is paid, you will have a grand total of one Atrazad, fifteen thousand Joks, and two Libgurs."
"Well, what if I check the other one?"
"Sore wa himitsu desu!"
Thrun's algorithm is correct. To see why, note that no matter how the envelope contents are distributed, all situations faced by the player can be grouped into pairs, where each pair consists of situations (x,2x) and (2x,x) which are equally likely. Within each pair the chance of switching from x to 2x is higher than the chance of switching from 2x to x, because f(x)>f(2x) by construction.
BTW, we have an ongoing discussion there about some math aspects of the algorithm.
In the ideal case, which I specifically addressed in the first line, epsilon is zero.
Can you describe more exactly what you mean by the ideal case?
The following is an elementary Bayesian analysis of why (a de-randomized version of) Thrun's method works. Does this not include the "ideal case" for some reason?
Let A and B be two fixed, but unknown-to-you, numbers. Let Z be a third number. (You may suppose that Z is known or unknown, random or not; it doesn't matter.) Assume that, so far as your state of knowledge is concerned,
A and B are distinct with probability 1;
A < B ≤ Z and B < A ≤ Z are equally likely; that is,
p(A < B ≤ Z) = p(B < A ≤ Z);
A < Z < B has strictly non-zero probability; that is,
p(A < Z < B) > 0.
It is then clear that
p(A ≤ Z) = p(B < A ≤ Z) + p(A < B ≤ Z) + p(A < Z < B),
because the propositions on the RHS are mutually exclusive and exhaustive special cases of the proposition on the LHS. With conditions (2) and (3) above, it then follows that
p(B < A ≤ Z) / p(A ≤ Z) < 1/2.
For, B < A ≤ Z is one of two equally probable and mutually exclusive events that, together, fail to exhaust all the ways that A ≤ Z could happen. (Condition (3) in particular makes the inequality strict.) By Bayes's formula p(P & Q) / p(Q) = p(P | Q), this then becomes
p(B < A | A ≤ Z) < 1/2.
In other words, upon learning that A ≤ Z, you ought to think that A is probably smaller than B.