I just came across a strange effect. Assume the following game: Take a dice and throw it. Now make a choice, if you want to keep that number, or try another throw for a higher number. If you get the same number or less, you loose everything. You can repeat that, if you like. What is the expected win, what is the optimal strategy?

It is easy to judge the result, if you start with the 6 and work backwards. Of course, the 6 is worth 6 and a keeper. If you get a 5, you can try to get a 6, but this will only succeed in 1/6 of all cases, yielding an expected value of 1. You do not want to do this. You better keep the 5. Likewise, with a 4 you get only (5+6)/6 on average, if you continue. So you keep the 4. Continuing from 3 gives (4+5+6)/6=2.5 on average, so it is a keeper too. The 2 is not a keeper, since another throw promises (3+4+5+6)/6=3, which is more than 2.

The 1 is most interesting. Of course, you will not keep it, and cash a win of 1. Continuing the game yields an average of (3+3+4+5+6)/6=3.5! (Note that the 2 is worth 3.) Surprisingly, the expected value is higher when we get a 1 as first throw than the amout, we get starting with a 2.

The average win is (3.5+3+3+4+5+6)/6=49/12, a little better than 4. The optimal strategy is to continue with a 1 or a 2.

The following Euler-Programm is a simulation of this effect.

>n=100000;
>a=floor(random(1,100000)*6)+1;
>{x,y}=histo(a-0.5,6,1); plot2d(x,y,bar=1);
>b=floor(random(1,100000)*6)+1;
>a1=(a<3)*b+(a>=3)*a;
>a1=(a>=3 || a1>a)*a1;
>{x,y}=histo(a1-0.5,6,1); plot2d(x,y,bar=1);
>b=floor(random(1,100000)*6)+1;
>a2=(a1<3 && a1>0)*b+(a1>=3)*a1;
>a2=(a1>=3 || a2>a1)*a2;
>{x,y}=histo(a2-0.5,6,1); plot2d(x,y,bar=1);
>mean(a2)
                4.08222
>49/12
         4.083333333333
>i=nonzeros(a==2); mean(a2[i])
         3.002320461712
>i=nonzeros(a==1); mean(a2[i])
         3.492461705464

Of course this kind of game can be applied to „Who wants to be a Millionaire?“.  Assume, you assess your chances of answering the question from a certain level on by a fraction q (maybe decreasing with the level). E.g., q=1/2 would be an interesting value. The win is doubled in each step, and you can fall back to a specific amount of money. What is your average expected win, and what is the best strategy?