can be better

For example, if 1 head and 1 tail so far, one should definitely keep tossing. if he gets head the payoff is at least 2/3, and if it is tail then he can get better than 1/3 by keep tossing, thus improving the payoff.

Let f(a,b) be the expectation of the payoff if played optimally, then we are interesting in f(0,0). We can obtain the following recursion:

f(a,b) = max(a/(a+b), (f(a+1,b)+f(a,b+1))/2);

It is not easy to solve it though, since the number of states is infinite. If we fix a finite horizon then we can compute an approximate solution. Another observation is that if one keeps tossing for a long time, with high probability he gets at least 1/2 - \epsilon. Therefore, f(a,b) >= 1/2 for all possible a and b. One good way of getting a good approximate will be setting a horizon T such that f(a,b) = max(a/(a+b), 1/2) if a+b=T, and solve the recursion.

I have no idea how the optimal solution can be computed analytically.

所有跟帖： 

• Similar to American Option -haha2000- ♂ (70 bytes) () 08/20/2009 postreply 06:07:11