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