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