wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> Coin Flip Game Worth (solution?)
        
(Message started by: Nicodemus on Jul 31^st, 2002, 12:31am)

Title: Coin Flip Game Worth (solution?)
Post by Nicodemus on Jul 31^st, 2002, 12:31am

I don't know that I've found the correct answer, but I wanted to put this up and see if other people either came to the same conclusions or were working along different lines.

As the number of coin flips increases, the law of averages says we should approach a 50/50 distribution. Therefore the payout if we play infinitely long should be 50 cents.

The goal is to employ a strategy that gets us more than 50 cents on average, as I read the problem. Despite what compulsive gamblers would say, I think the best strategy is to stop as soon as you have a greater number of heads than tails; in terms of probability, playing longer is just more likely to see you converge towards 50/50.

(My solution does rely on probability, one of the reasons I suspect it's incorrect. If you keep flipping tails, you will play infinitely long or until you get bored.)

So we use our ability to choose how long we play to stop as soon as we're ahead. Graphing the possibilities as a tree (reminiscent of Pascal's triangle) shows us the first couple of rounds. Note we never stop on an even round, since we can't have better than a 50/50 history. Also note that I'm counting probabilities from the first flip; so each round splits the ones where we kept going.

first flip: 1/2 heads (pays $1), 1/2 tails (keep going)
second flip: 1/4 heads, 1/4 tails
third flip: 1/8 heads (pays $2/3), 1/8 tails (keep going)
fourth flip: 1/16 heads, 1/16 tails
fifth flip: 1/32 heads (pays $3/5), 1/32 tails (keep going)
etc...

This gives us a payoff defined by the series:
(1/2 * 1/1) + (1/8 * 2/3) + (1/32 * 3/5) + ...

I never did well on series stuff in calculus, but by calculator it's approximately 61 cents. Anyone else get that?

Title: Re: Coin Flip Game Worth (solution?)
Post by AlexH on Jul 31^st, 2002, 2:46am

You're missing some of the cases. If you're down by some number of tails, then you play a long time and get an expected payoff of at least .5. Your sum is skipping some cases where you get behind on the ratio. For example the case where both of the first two flips are tails doesn't seem to ever get into your sum as you've written it.

Given the long play time .5 payoff, we can see right away that we should be able to get at least .75 since when our first flip is heads we can get $1, and the other half of the time we can at worst drag the game out to get .5 (we can do better of course I'm just saying we can't do worse).

I think you're probably right about the "greedy" strategy of quitting as soon as you're ahead being at least pretty close to optimal. At first glance this problem looks like maybe you could do something with prefix codes, wish I had time for it today. This board is evil :P

Title: Re: Coin Flip Game Worth (solution?)
Post by Kozo Morimoto on Jul 31^st, 2002, 7:45am

I like the solution by Nicodemus. The solution is basically how you price financial options using the binomial tree, where early exercise is possible.

Title: Re: Coin Flip Game Worth (solution?)
Post by Nicodemus on Jul 31^st, 2002, 12:35pm

AlexH-

You're quite right. I completely missed those cases when computing the probabilities in the tree; I was only looking at outer branches. Nice catch!

Hmm.... Dang, this makes it much harder! :)

Title: Re: Coin Flip Game Worth (solution?)
Post by Kozo Morimoto on Jul 31^st, 2002, 8:58pm

OK, here goes.
I am looking at a binomial tree and each node has payout amount AND a probability of reaching it.

The naming convention is starting at the root of (0,0), and the next level would be (1,1) for getting a head, and (1,0) for getting a tail. So after 2 flips, the nodes would be (2,2) for 2 heads, (2,1) for 1 head/1 tail and (2,0) for 2 tails. etc etc

Probability of reaching any node (k,i) = (k!*p^k) / ((k-i)!*i!)
where p=1/2.

Now I assume that if you get a head on the first flip, you will quit and collect the $1. But if you get a tail on the first flip, you will keep playing forever as you can approach $1 as you get more and more heads. Say you have a sequence THH. Payout is $2/3. If you get H on the next flip, your payout increases to $3/4, which is better than $2/3.

So starting the binomial tree at (1,0) and translating that to (0,0),
Payout(k,i)=i/(k+1)
So,
Expected Return'=Sum(k=0->inf)[Sum(i=0->k){k!*p^k*i/(k-i)!/i!/(K+1)}]

Since this binomial tree start at (1,0) of the original tree,
Expected Return of the whole game = ($1+Expected Return')*p

I don't know what the ER' sums to and if you can specify an early exit condition, this should be able to be expanded to calculate for that. Do you get out when $2/3 or do you try for $3/4? Or get out at $4/5? And I'm not sure what the optimum exit condition is... yet.

Title: Re: Coin Flip Game Worth (solution?)
Post by Eric Yeh on Aug 1^st, 2002, 7:25am

Guys. One clue: the greedy algorithm doesn't work.

Sub problem [Coin Flip Game Worth 0.5]: Prove you do not stop after 2/3.

Happy puzzling,
Eric

Title: Re: Coin Flip Game Worth (solution?)
Post by Kozo Morimoto on Aug 1^st, 2002, 2:36pm

I think you should stop at $2/3.

You have 2 scenarios:
a) you win the next flip and your payout increases by $1/12 to $3/4
b) you lose the next flip and your payout decreases by $1/6 to $2/4

So 50/50 chance either way, your expected return for the next flip is -$1/12 so you wouldn't do it, you should walk off with the $2/3.

Title: Re: Coin Flip Game Worth (solution?)
Post by Eric Yeh on Aug 1^st, 2002, 3:06pm

Kozo,

By that proof you would definitely stop at anything above half. (Pf left as an exercise to the reader.) Do you believe that?

The problem with the argument is that you're completely ignoring the option value of continuing the game. (You mentioned financial modelling before, so I assume you're familiar with this concept). The value of continuing the game is higher when you lose 1/6 than when you earn 1/12 -- the question would be whether or not the difference is greater than the risk differential of 1/12. ;)

Best,
Eric

Title: Re: Coin Flip Game Worth (solution?)
Post by Kozo Morimoto on Aug 1^st, 2002, 6:05pm

I've done a very small Excel spreadsheet to see how n affects the expected return.

n=1, $0.50
n=2, $0.625
n=3, $0.6667
n=4, $0.6927083
n=5, $0.7083333
n=6, $0.7197917
...
n=10, $0.7436973

this is when you quit when your return is > $1/2.
I don't know what this sequence converges to (or whether if it even converges) but I thought it may be heading towards $3/4 ?

Can you clarify your view on "The value of continuing the game is higher when you lose 1/6 than when you earn 1/12 "? I don't understand.

I've looked thru the text to refresh my mind on pricing barrier options (up & out) with a cash rebate, but the examples I could find are too simplified to be applied to this riddle.

Title: Re: Coin Flip Game Worth (solution?)
Post by Eric Yeh on Aug 1^st, 2002, 8:35pm

Kozo,

I just meant that the value of the option to continue the game when you're at 1/2 (after you've "lost 1/6" in the example we were discussing) is worth more than the option to continue the game when you're at 3/4 (after you've won 1/12).

For example, suppose that at 3/4 the expected value of the finished game is .78 (I am picking something semi-random -- I am not saying it is not actually .75 as you are thinking about!). Then the value of the option when you're standing at 3/4 is .78-3/4 = .03. But the expected value starting from 2/4 may actually be .65, so that the value of the option to continue is worth .15. Then at 2/3 you would prefer the half-chance of getting to .78 rather than .65, precisely because -- relative to your previous argument regarding 1/6 being > 1/12 -- the value of the continuation option is greater by more than 1/6 - 1/12 = 1/12.

Hope that's more clear.

If I understand your spreadsheet work correctly, you now agree with me that stopping at 2/3 is not optimal, right?

Best,
Eric

Title: Re: Coin Flip Game Worth (solution?)
Post by Kozo Morimoto on Aug 1^st, 2002, 10:58pm

Yeah, I see your point, but you don't have hard figures to back up your argument. You explanation has too many "may"s.

The spreadsheet simulation was assuming that I quit as soon as my payout is greater than $1/2.

If you assume no quitting, then at any n, I assume that you would get a payout figure of $0.50.

Can anyone find a strategy that beats quitting at > $0.50?

Title: Re: Coin Flip Game Worth (solution?)
Post by tim on Aug 2^nd, 2002, 12:39am

Yes, I have a strategy that beats quitting at $0.50.

Let H be the number of heads, N be the number of flips so far, and let b = 2H - N ("bias"). Quit when b > sqrt(N / 2).

It terminates with probability 1, and exceeds the payoff of the $0.50 strategy by about $0.005. I know there exists a better strategy still, but can't seem to derive it from first principles.

Certainly there exist strategies that pay more when they terminate -- the difficulty is finding a strategy that terminates 100% of the time.

Note: either of these strategies place an extremely small value on your time. In one computer test run, it took more than 14 million flips before the payoff exceeded $0.50. One sqrt(N/2) strategy run took 700 million flips :O

Title: Re: Coin Flip Game Worth (solution?)
Post by Eric Yeh on Aug 2^nd, 2002, 5:52am

Kozo,

My liberal usage of the word "may" was merely an attempt not to give away too much information. :) I do have hard figures I could use to make my last argument precise, but I don't want to deprive anyone of their personal satisfaction.

Tim,

Thanks for the back up.

Best,
Eric

Title: Re: Coin Flip Game Worth (solution?)
Post by tim on Aug 3^rd, 2002, 8:28pm

Eric: do you have a provably optimal solution?

I don't actually want to know what it is or any hints toward it, I just want to know whether there is one :/

I've found a sequence of strategies that monotonically increases in value, but the average number of flips required goes to infinity as I progress along the sequence. As a consequence, I don't just want to take the limit and call it "optimal". I'm not even sure I should consider it a solution.

If you have a solution, do you know that it definitely terminates and has a finite mean number of flips? I'm stuck :(

Title: Re: Coin Flip Game Worth (solution?)
Post by Eric Yeh on Aug 3^rd, 2002, 9:55pm

Tim,

I'm afraid I am perhaps only at a similar point of thought as you are. I can also create sequences like the one you mentioned, and I understand interesting things about the solution such as the fact that you do not stop at 2/3, but I do not have a proveably optimal solution.

It's interesting though; I never interpreted the question as requiring a finite mean for flips. Perhaps that is a reasonable interpretation of the question, but I (for example) always thought it acceptable to consider any value under .5 to be worth at least .5, by the central limit theorem. Even this simple assumption requires a potentially infinite number of flips...

Best,
Eric

Title: Re: Coin Flip Game Worth (solution?)
Post by tim on Aug 3^rd, 2002, 11:21pm

Yes, I'm also treating anything under 0.5 as being potentially at least 0.5. Although this potentially requires an infinite number of flips, the mean number is still finite. (Often large, but finite)

At the moment, I'm describing my strategies by looking at the total number of turns required before a given number of tails becomes acceptable (N_t). For example, N_0 = 1, so that you accept the first flip if it doesn't come up tails. If you accept 3/4 but not 2/3, you would be using N_1 = 4. The sequence {N_k} is strictly increasing and has a few other useful properties.

I've got a formula for evaluating the mean payoff for any sequence {N_k}, and a formula for the mean number of flips it requires. I've got some constraints on 'efficient' choices for N_k, but not enough to prove optimality. So far, every strategy I've been able to devise can have its payoff improved by increasing the mean number of flips required.

Since my last post, I've found a sequence of strategies with better payoffs. Every strategy in the sequence terminates with probability 1. The sequence even has a limit. Unfortunately, that limit has a small but non-zero chance of never terminating. :( So I'm still looking for either an optimal solution or a proof that there is none.

This problem is causing me to remember how much trouble the various types of sequence spaces inflicted in my Analysis & Topology course :-/

Title: Re: Coin Flip Game Worth (solution?)
Post by anshil on Aug 5^th, 2002, 6:24am

The game is worth: 0.69314718056

Best strategy is just to stop after you get your first head. After that calculating fair chances it can't go better. This is as best demonstrated when you flipped the first time you get a tail. Second time you get a head. So you got 0.5. Keep going or stop? If you keep going and you get a head you've 2/3 if you loose you've 1/3. So sum both possiblities and divide by 2 because there are 2 possible actions you still have 0.5. So you won't get better chances. (Of course you can get higher, but also lower, so in some chances elimate themselfs in this case exactly).

Okay now supposing we want to stop at the first head. what are our


chances first game: head 1 win,           tail 0 win                          : 0.5 worth
second game: (last game head) don't care we stay at 1  last game(tai) head 0.5 win    tail 0 win     : worth 0.625
third game: (first game head) don't care we stay at 1  last game(head) we stay at 05.   last game(tail): 0 win  : worth 0.666

and so the n'th game has following worth:
1/2 + 1/ ( 2 ^ 2 * 2) + 1 / ( 2 ^ 3 * 3) + 1 / (2 ^ 4 * 4) + ... + 1 / ( 2 ^ n * n)

numercial calculated for n = 100 equals:0.69314718056
However don't ask me how to get to this nummer in closed form. Maybe it has e in it?

Title: Re: Coin Flip Game Worth (solution?)
Post by Eric Yeh on Aug 5^th, 2002, 8:31am

Anshil,

Hmmm, you sound quite sure of yourself. If you'd like to play, I will happily pay you 70 cents for the game, giving you a nice margin! ;)

The problem with the argument of using the expected value of the next flip has to do the with value of the option to continue playing the game: see my discussion with Kozo above.

Also note that you can always get 50 cents by playing a large number of flips, as per my discussion with Tim.

Best,
Eric

Title: Re: Coin Flip Game Worth (solution?)
Post by anshil on Aug 5^th, 2002, 10:18am

The problem with the argument of using the expected value of the next flip has to do the with value of the option to continue playing the game: see my discussion with Kozo above.

What do you mean with this?

Maybe I try again to explain my strategy, I stop at the first head I get. So now let's look a game where we flipp three times.


first flip. 50% chance head - 1 win
                50% chacne tail - loss
second flip: we had 50% chance (for all games)to own already in round 1.
                    we can think of doing an imaginary second flip, just for statistics,  
                     our win stays at 1.
                     we have 25% chance (total game) to get a head this time.
                     and 25% chacne to get a tail again.
third flip: we had 50% of all games win in round 1 (1 worth)
                we had 25% of all games win in round 2 (0.5 worth)
                we have 12.5 % of games where we win 0.25 this time, and
                12.5 % of games where we loose again.

Now let's calculate total worth if we are allowed only to flip only 3 times maximum. Okay we tossed the coin 3 times, (sometime imaginary), there are 8 possiblities the game can go, now we can calculate our win for each possiblity and divide it by 8. Thats what the game is worth. (we can continue this with 4, 5 or n flips maximum).
So in this case it's ( 4 * 1 + 2 * 0.5, + 1 * 0.25 + 0 ) / 8. You can also of course calculate chances if you continue to play after one head, (if it isn't the first of course). You'll discover the net worth will stay the same. In our example we have following possiblies, the game can go

column 1 possible coins: H is Head T is Tail

okay once again for the first stop strategy, column 2, and for the continue to play strategy colum 3


H H H          1                1   (if the first one is a head we stop, 
H H T           1                1    there is no sense to continue)
H T H           1                1
H T T            1                1
T H H         0.5           0.66   in the 2nd column we stopped after the 2nd flip
T H T          0.5           0.33  - "" -
T T H          0.25         0.25
T T T           0              0
--------------------------
total worth * 8 =        5,25       5,25

See it doesn't matter if you continue or stop. Okay let's do it with 4 to make sure it isn't by randon.


H H H H        1                1 
H H H T         1                1 
H H T H         1                1 
H H T T          1                1 
H T H H         1                1
H T H T          1                1
H T T H          1                1
H T T T           1                1
T H H H          0.5            0.75   
T H H T          0.5            0.5
T H T H          0.5            0.5
T H T T           0.5            0.25
T T H H          0.33          0.5
T T H T           0.33         0.25
T T T H           0.25         0.25
T T T T            0              0
--------------------------
total worth * 16 =    10.916    11.0

Oh Oops! Seems I was wrong indeed (or calculated wrong). Okay but I will post anyway maybe it helps others, so it's possibly higher than my number from above.

Title: Re: Coin Flip Game Worth (solution?)
Post by oliver on Aug 5^th, 2002, 10:36am

Hmm, I deleted a previous, blatantly wrong message, but now I think I got it.

Say you have flipped the coin N times, with H heads, and your goal is to win p cents, with H/N<p<1.
Then you need at least to throw k heads in a row, such that k is the smallest integer with

(H+k)(N+k)>p, i.e. k>(pN-H)/(1-p)

the probability of that happening is 2^-k, but this is not relevant. It's relevant that the probability is > 0.

So what happens if it didn't work out, i.e. you got not a head for at least one flip. Doesn't matter, try the above again (with bigger N,H etc.). It means that you have an infinite number of chances to win (get a price > p) with the probability of winning always > 0.
Therefore you win with a possiblity of 1.
Since p<1 is arbitrary, it follows that the worth of the game is 1.
Note to Eric, anyhow I think I wouldn't like to play the game you offered with p=0.7, methinks I'll find better ways to do with the rest of my life :D.

Title: Re: Coin Flip Game Worth (solution?)
Post by Eric Yeh on Aug 5^th, 2002, 10:45am

Anshil,

How interesting, you've re-discovered the same problem that Kozo initially mentioned, but in the reverse! This is the fact that if you are below 1/2, the expected value of your next flip is strictly positive (in your last example, this occurs where .5-.33 > .33-.25). This doesn't occur in your n=3 case because there the tree is not deep enough to get beyond the symmetric cases. Amusingly, the fact that you never see the analagous case at 2/3 is actually only an outcome of your base strategy, since the strategy never allows you to get there!

But don't be fooled by that; the argument is still wrong because of the option to continue the game -- if you read my discussion with Kozo you will see what I mean.

In the other direction, you can quickly see that the concept of stopping at your first head cannot be right: Suppose your first head is at 10. You would never want to stop and collect 1/10, because in the limit you can always convert this to .5...

Best,
Eric

Title: Re: Coin Flip Game Worth (solution?)
Post by Eric Yeh on Aug 5^th, 2002, 10:53am

Oliver,

Sorry, the flaw in your argument is that not every sequence of positive numbers sums to... er... 1. (Hm, now it sounds even more obvious!) In your example, if your "first" chance of getting to p is, say 1/4, and your second "chance" is (cumulative for simplicity) 1/8, and so on, your total probability of getting to p is -- while strictly increasing in your number of flips -- still only 1/2...

BUT, if you don't believe me, I'll happily sell you the game for the great discount rate of 90 cents ;)

Best,
Eric

Title: Re: Coin Flip Game Worth (solution?)
Post by oliver on Aug 5^th, 2002, 11:14am

Indeed, eric, indeed.

That was not very clever, I really should have thought about adding the probabilities. That's why I always hated probability&statistics - sigh.

Title: Re: Coin Flip Game Worth (solution?)
Post by Eric Yeh on Aug 5^th, 2002, 11:17am

That's all right Ollie, your complex analysis is solid! :)

Title: Re: Coin Flip Game Worth (solution?)
Post by oliver on Aug 5^th, 2002, 12:05pm

Haha, two edged compliment.
Solving the riddle you refer to without knowing complex analysis would have been more praiseworthy. :P

Btw., I don't see you _solving_ any riddles? Know all the solutions? Lazy? :D

Title: Re: Coin Flip Game Worth (solution?)
Post by Eric Yeh on Aug 5^th, 2002, 12:16pm

I've posted answers to some. Many I already knew, and most of the others I did indeed solve. However, I don't post if 1) I already knew the answer, 2) they are relatively easy, or 3) there is already a good solution sitting in the forum. That covers most of the cases.

If you like, check my answer to Frost's Impatient Patients problem -- the author seems to have disappeared. I didn't think through the last few details very carefully so I might have made a mistake.

Best,
Eric

Title: Re: Coin Flip Game Worth (solution?)
Post by oliver on Aug 5^th, 2002, 12:28pm

Take a look at the Hamming Distance question. Do you know the answer also, or is it too easy?
If yes, I have another riddle I plan to post if most of the others are solved, the problem is I don't know the answer myself, and I don't know if it is easily solvable (and no, it's not Goldstein's conjecture).

cheers,
oliver

Title: Re: Coin Flip Game Worth (solution?)
Post by Kozo Morimoto on Aug 5^th, 2002, 7:17pm

I've been googling and came up with:

Y.S. Chow and H. Robbins (1965) "On Optimal stopping rules for Sn/n" Illinois J. Math. 9. 444-454

Can someone locate this so that we can conclude this thread? I'm frantically searching for this at the moment...

Title: Re: Coin Flip Game Worth (solution?)
Post by Eric Yeh on Aug 5^th, 2002, 8:27pm

Ollie,

Why don't you just post your problem? For a variety of reasons I'm not too interested in the Hamming Distance question.

Best,
Eric

Title: Re: Coin Flip Game Worth (solution?)
Post by anshil on Aug 5^th, 2002, 9:15pm

Okay I've thinked about it more, the game is _at_ _least_ worth 0.75. Since if you take probalities for 10 flips, saying you always continue if the first one isn't a head. You have a total equal number of heads and tails in all possiblities changes, so get 0.5 after that. So total worth is at least 0.75. However I guess it's actually even more. Since I think the best strategy is to stop when chances are that you loose more than you'll win.

THHH = 0.75 stop or continue?
THHHT = 0.6 (loose 0.15)
THHHH = 0.8 (win 0.05)
So you better stoped would have stopped at THHH.

TH = 0.5

Guess here you can also better just stop.

THH = 0.66 (won 0.16)
THT = 0.33 (lost 0.16)
I think it's even true if continueing:
THHH = 0.75 (won 0.25)
THHT = 0.5 ( equal)
THTT = 0.25 (lost 0.25)
THTH = 0.5 (equal)

So you stop if your total worth is at least 0.5 ? Okay but what's the total game worth then? (It's must be more than 0.75)

Title: Re: Coin Flip Game Worth (solution?)
Post by Eric Yeh on Aug 5^th, 2002, 9:42pm

Anshil,

You are correct that the value is > .75. However, your argument for stopping at 3/4 is specious! This is the same pitfall many of the people posting on this thread are falling for: you have to take into account the value of the option to continue, not just the value of the next flip.

Best,
Eric

Title: Re: Coin Flip Game Worth (solution?)
Post by anshil on Aug 5^th, 2002, 9:57pm

Okay Eric I guess you want to say the total worth is 1.0$, but I don't buy that, this way. Since you don't use any mathematics, only mind boggling. Thats what greeks already did wrong. Of course you can always continue to play until you heads exceed the number of tails by any factor. But it's more and more unlikely to get that, I think it's part of the total "worth", you can't always say, well then next ten thousend flips I will have luck and only get heads.

Okay maybe another interesting puzzle would be, what if each flip would cost 0.1$ when is best stopping condition.

Title: Re: Coin Flip Game Worth (solution?)
Post by Eric Yeh on Aug 5^th, 2002, 10:38pm

Anshil,

No; if you had actually been following this thread carefully, you would have known that I certainly do not believe it is worth 1, and in fact I can easily demonstrate that mathematically.

As far as your mathematics/"mind-boggling" comment (I'm not sure what that even means as a noun), I suppose I should be offended? I'm not sure of your intention, but either way you can rest assured that just because I don't reveal all my work in these posts doesn't mean I don't still have real "mathematics" to back it up. I am certainly greatly insulted if that shamble of a proof you outlined for P=$1 is supposed to pass for anything that could even remotely pass through my mind. >:(

Your suggestion of a $.1 flip charge, while possibly workable as an extremely simplified version of the problem for rookies, demonstrates a fundamental misunderstanding of the crux of this riddle. It trivializes the problem by forcing the game to a finite set of states, whose value it would take me under five minutes to compute (and the methodology five seconds after reading). So unless you have at least solved your own problem before I have, I suggest you not fling insults so errantly.

If you like, I would be happy not to correct any of your errors in the future.

Eric

Title: Re: Coin Flip Game Worth (solution?)
Post by anshil on Aug 5^th, 2002, 11:27pm

Oh man, don't feel insulted so easily, get a thicker skin. (or grow up, I see that as a pretty childish reaction).

So yes, sorry, I didn't mean it that way.

Well here are these thing discussed:
http://www.math.ucla.edu/~tom/Stopping/sr1.pdf

And well the additional cost per toss is also a problem discussed, so if you're so a smart *** tell the forumular for a optimal stop condition for a cost of x.

Title: Re: Coin Flip Game Worth (solution?)
Post by Eric Yeh on Aug 6^th, 2002, 7:41am

Anshil,

Well, I may have said something similar to you on your previous post. But you're right that this petty bickering doesn't become us, so I will also apologize for my outburst and move on.

Regarding the solution to your problem: It really is quite simple computationally, but you will note I never claimed to have a closed-form formula. Certainly for the case of c=$.1 one can do it by hand, and it would only take maybe ten minutes to write a general program to solve the more computationally intensive cases with small values of c.

Note that it differs greatly from the problem mentioned in the paper (nice find on that, by the way) in the respect that in their problem there is an arbitrary distribution on the value of the house (I assume you were referring to Example 1). I don't have time to think very far into that problem right now, but the unboundedness makes it at least nontrivial. Because our problem is bounded by [0,1], a cost of $.1 a flip ensures that you never play more than 10 rounds, which makes it quite simple indeed.

Alternatively, we might be able to extend your extension into a more difficult problem by ensuring that the cost-to-play never exceeds 1, or at least along certain lines. An example of the former (simpler) case, we could say that the nth flip costs $.1*.5ⁿ or some such, and I would no longer know the solution. On the otherhand, I am not sure that that adds any intellectual value to the original problem, which is perhaps already optimally complex.

Eric

Title: Re: Coin Flip Game Worth (solution?)
Post by anshil on Aug 6^th, 2002, 9:00am

I think a possible way is to find a closed formular for a cost of x per flip. (0.1 as an example). If this is possible than the original problem should also be no problem then, just let lim x-> 0 so then you've that, and just hope we won't get 0/0 or such.

Title: Re: Coin Flip Game Worth (solution?)
Post by Kozo Morimoto on Aug 6^th, 2002, 4:51pm

"Note that it differs greatly from the problem mentioned in the paper (nice find on that, by the way) in the respect that in their problem there is an arbitrary distribution on the value of the house (I assume you were referring to Example 1). "

I think we are all talking about the problem on page 5 of that paper subtitled "Maximizing the average".

I also found this paper, but it only describes the problem but no solution, but points out that Chow & Robbins (1965) have attempted/solved and talks about greater than $0.79.. payoff. Can someone locate THAT original paper?

Title: Re: Coin Flip Game Worth (solution?)
Post by Paul Hsieh on Aug 7^th, 2002, 8:01am

Hmm! Well, I can get > $0.7831 ...

Basically I just flip, and stop as soon as the number of heads exceeds the number of tails. If after a million flips the number of heads is always less than the number of tails, then I just flip an additional billion times and just take whatever I get.

I worked this out for up to 11 flips, but cannot figure out how to compute it in closed form. The sequence is something like:

1/2 + 1/8*2/3 + 2/32*3/5 + 6/128*4/7 + 16/512*5/9 + 46/2048*6/11 + ...

(I cut it off after 11 terms, and thus could add an additional 434/2048*1/2) But I cannot find the pattern is so few terms.

Title: Re: Coin Flip Game Worth (solution?)
Post by Paul Hsieh on Aug 7^th, 2002, 5:08pm

Here's a program from generating the result according to my strategy:

Code:

#include <stdio.h>

double val (int h, int t, double l) {

if ((int)(h + t) == 31) return 0.5 / l;

if (h > t) {
return ((double)h) / (((double)(h + t)) * l);
}

return val (h + 1, t, l + l) + val (h, t + 1, l + l);
}

main () {
double d;

d = val (0, 0, 1);
printf ("Sum = %g\n", d);
}

After much transformation I have substantially improved the performance in the following:

Code:

#include <stdio.h>
#include <stdlib.h>

struct tag_s {
double c;
int l;
double a[1];
};

static struct tag_s * newTable (int l) {
int i;
struct tag_s * tab;

tab = malloc ((l + 1) * sizeof (double) + sizeof (struct tag_s));
tab->l = l;
for (i=0; i <= l; i++) {
tab->a[i] = 0;
}
tab->c = 0;
return tab;
}

static double * accessTab (struct tag_s * tab, int h, int t) {
return &tab->a[h];
}

static struct tag_s * nextTab (struct tag_s * tab) {
struct tag_s * nt;
int l;
int h, t;
double c = 0;
double d = 0;

l = tab->l;
nt = newTable (l + 1);

if (l == 0) d = 1.0; else {
d = 2;
for (h = 1; h < l; h++) d += d;
}

d += d;
d *= (double)(l + 1);

for (h=0; h <= l; h++) {
double v;
t = l - h;
v = *accessTab (tab, h, t);

if (h + 1 > t) {
c += ((double)(h + 1) * v);
} else {
*accessTab (nt, h + 1, t) += v;
}
*accessTab (nt, h, t + 1) += v;
}

nt->c = c / d;
return nt;
}

static struct tag_s * endTab (struct tag_s * tab) {
struct tag_s * nt;
int h, t, l;
double c = 0;
double d = 0;

l = tab->l;
nt = newTable (l + 1);

if (l == 0) d = 1.0; else {
d = 2;
for (h = 1; h < l; h++) d += d;
}

d += d;

for (h=0; h <= l; h++) {
double v;
t = l - h;
v = *accessTab (tab, h, t);
c += v;
}

c = c / d;

nt->c = c;
return nt;
}

main () {
static struct tag_s * tab;
static struct tag_s * ot;
int i;
double d;

d = 0;
tab = newTable (0);
*accessTab (tab, 0, 0) = 1;
for (i=0; i < 1013; i++) {
ot = tab;
tab = nextTab (tab);
free (ot);
d += tab->c;
}
tab = endTab (tab);
d += tab->c;

printf ("Tot = %.11g\n", d);
}

So the best I can do is: 0.78539404679 ...

Title: Re: Coin Flip Game Worth (solution?)
Post by tim on Aug 7^th, 2002, 7:06pm

Paul: I don't have a closed formula for the value of the the >50% strategy either. I do have a closed formula for the nth term in the series, though. To get n+1 heads out of 2n+1 flips, you must get n heads out of 2n flips without ever exceeding equal numbers of heads and tails, and then get a head.

The number of ways to get n heads out of 2n flips without the number of heads ever exceeding the number of tails is given by Catalan numbers, catalan(n) = (2n)! / n!^2.(n+1). So the total value of the >50% strategy is

Sum[n=0 to infinity, (2n)! / n!^2.(2n+1).2^(2n+1) ]

I can get above $0.79 through a heuristic annealing process running on my computer, but can't find an optimal strategy by a deductive process. I can't find a useful pattern in the best heuristic strategies, either.

What's more, I haven't been able to track down that 1965 paper. :(

Title: Re: Coin Flip Game Worth (solution?)
Post by tim on Aug 7^th, 2002, 7:59pm

The value of the >$0.50 strategy is actually $0.7853981633980431...

I have been doing quite a bit of work on the >$0.50 strategy, even though I know that it is suboptimal. For example, the probability of exceeding N flips tends toward sqrt(2/(pi*N)), and the residual value of the remainder tends toward 1/(3*N*sqrt(2*pi*N).

I am hoping that studying a simpler strategy can help me to understand how to construct a better one.

My best heuristic strategies are suspiciously close to sqrt(pi/5) in value. Maybe that's some sort of clue... :-/

Title: Re: Coin Flip Game Worth (solution?)
Post by Paul Hsieh on Aug 7^th, 2002, 11:36pm

Interesting! :o My intuition definately failed me here. A simple modification of my calculations verifies exactly what you just said.

Rather than using the rule that we stop if #Head > #Tail, I changed this rule to (#Head > 5/4*#Tail) and this increased the value to 0.788257... (from my previously computed value of 0.785394... .) This 5/4ths ratio appears to be some kind of local limit. That's interesting.

This "5/4" ratio can be treated on a per sub-problem (# heads so far, # tails so far) basis, rather than a global constant, which is where I would view the remaining opportunity for further improvements. Hmmm ... this might turn into some kind of strange optimization problem ...

Title: Re: Coin Flip Game Worth (solution?)
Post by tim on Aug 8^th, 2002, 1:15am

You definitely have to treat the "5/4 ratio" as a local parameter to be changed with N. Any constant ratio greater than 1 will give a non-zero probability that the game lasts forever. :(

It is a very difficult problem in optimisation. I have managed to prove that the value of the game is less than 5/6 ($0.833), but that's about as far as I've managed to get on the analytical front. A most vexing problem! :P

Title: Re: Coin Flip Game Worth (solution?)
Post by oliver on Aug 8^th, 2002, 2:39am

Hm, perhaps time to join the forces.

First, has anybody the complete solution for this riddle already?

Is anybody at the point where the problem is merely analytical, i.e. you have any formula, probably an infinite sum about one or two indizes with one unknown variable representing the worth of the game, reducing the riddle to the problem of solving an equation or maximizing a formula?

I ask the above because I'm quite sure one can write such down such a formula, but I assume it will look very ugly.

Title: Re: Coin Flip Game Worth (solution?)
Post by tim on Aug 8^th, 2002, 3:39am

I've got an two-index infinite series formula representing the value of the game, in an infinite number of unknowns, to be maximized subject to a different infinite sequence in the same unknowns having zero limit. From a theoretical mathematics sense, you could look at this as merely "maximizing a formula".

However, there is always the tantalizing prospect that the true solution has a form that is blindingly obvious in hindsight, without regard to any messy formulas. I'd like to find such a solution.

Failing that, I'd like to at least prove that the game has a best strategy that achieves the value of the game. I'm not certain that it does; in fact I suspect the opposite.

Failing that, I'd like to be able to prove rigorously that there is no best strategy.

Either way, I'd like to derive a formula for the least upper bound of the value of the game, independent of strategies.

Failing that, I'd like to at least derive a better upper bound for the value of the game than the one I've got.

So far, I've got a very loose upper bound for the value of the game, a whole bunch of very good but known suboptimal strategies found only by computer search, and sequences that don't converge. Ick. :P

Title: Re: Coin Flip Game Worth (solution?)
Post by oliver on Aug 8^th, 2002, 5:02am

I'm short on time, so please excuse if the following has any glaring error, I'm just writing down something that came to my mind when reading your post Tim. Btw. thanks for the concise explanation of your proceedings and plans.

Quote:

Failing that, I'd like to at least prove that the game has a best strategy that achieves the value of the game. I'm not certain that it does; in fact I suspect the opposite.

May I reformulate that?

Can the best strategy be to aim for realizing the worth of the game (W) in any case, that is, continue as long as one hasn't got H/T >= W?

If that were the case, we would have proved that the worth of the game is invariant of adding a constant C to T when calculating the earned value, because if we assume we had thrown T₀ times without getting a head, the remainder of the game would be equivalent to a freshly started game with a prize of H/(T+T₀).
Doesn't sound very convincing, does it?

Title: Re: Coin Flip Game Worth (solution?)
Post by Eric Yeh on Aug 8^th, 2002, 5:36am

Ollie,

I've also briefly thought about this "W" question you mentioned -- if I had some more time to think about the problem I think that's a question I would try to figure out soon. However, your invariant argument isn't quite right because the payoffs are changing depending on your value of T₀, in a non-proportional way. Another way to see the problem is that you could force a stop at a value under .5 by taking C = 2H-T+1 (for example).

Tim,

Is it hard to show your 5/6 boundary? That sounds quite useful. I suppose it's not extendable?

Best,
Eric

Title: Re: Coin Flip Game Worth (solution?)
Post by oliver on Aug 8^th, 2002, 6:47am

Eric, maybe I misunderstand you and/or worded myself not very well.

I wanted to argue that the strategy cannot be independend on T, esp. cannot only be dependend on the value of the fraction H/T.

Title: Re: Coin Flip Game Worth (solution?)
Post by Eric Yeh on Aug 8^th, 2002, 4:19pm

My apologies if I misunderstood. Unfortunately, I have to admit I still don't understand! I think it's because you use both "dependent" and "independent".

I agree with you that it would be interesting to see if the "instantaneous" (next flip) strategy is independent of T, but only relies on H/T. Or are you saying you've disproved this possibility?

Best,
Eric

Title: Re: Coin Flip Game Worth (solution?)
Post by oliver on Aug 9^th, 2002, 3:05am

Eric,

what I meant to say is the following:

In order to get a strategy, many people seemed to have the idea that "continue if H/N > W" is the way to go (N is the number of the flips we did).

Formally, our strategy could expressed as a function f(b) B_n -> {0,1}, where B_n is the set of bitstring of length n, representing the coin flips we had already done ("TTHTHTHH" ...), so that if f(b) == 1 we continue, otherwise not.
Due to indepence of the events, it's clear that f(b) can be written as f(H,n). What I wanted to give a plausability argument for was that f cannot be written as f(H/n).

Title: Re: Coin Flip Game Worth (solution?)
Post by Eric Yeh on Aug 9^th, 2002, 5:27am

Ollie,

OK, now I understand what you are saying. I definitely completely agree w what you are saying about not knowing if the "H/n > W" strategy is correct, and in fact I have not employed this kind of a strategy in my work thus far at all.

However, I do not agree with your proof that it is definitely not of the form f(H/n), unless I am misunderstanding it. My original reply to your msg still holds: The payoff structure changes after your first constant number of flips, so "starting a new game" then is just not the same thing. You can also see it by my second example in the same thread, which forces a stop under .5 which you should never do.

That said, I do think it would be good to figure out whether the f(H/n) strategy works.

Best,
Eric

Title: Re: Coin Flip Game Worth (solution?)
Post by AlexH on Aug 9^th, 2002, 9:52pm

The optimal stopping decision can't be a threshold for H/n (at least not one > .5 ) for exactly the same reason Bob wins in that Alice and Bob counter game. You fixing the threshold is just like Alice picking the coin bias. For any line sloping away from the mean like there is a finite chance that the sampling will never cross that line. In other words that strategy does not terminate with p=1 and therefore you can beat it with (for example) a strategy which does mostly the same things but accepts less once it reaches an n,H situation where non-termination becomes sufficiently likely.

Title: Re: Coin Flip Game Worth (solution?)
Post by Eric Yeh on Aug 10^th, 2002, 11:14am

Alex,

That is a good point -- clearly at a sufficiently high n you stop arbitrarily close to .5, for example. However, I realize I didn't express my question well. I meant to ask, if you stop at H/n, do you stop at every H/m where m>n. I assume this is true, but haven't had more than a couple of minutes to think about it.

Best,
Eric

Title: Re: Coin Flip Game Worth (solution?)
Post by AlexH on Aug 10^th, 2002, 12:25pm

Sorry to be difficult but I'm not sure I understand the question you are asking now.

Did you mean m<n instead of m>n? If so then as I understand it your question is "If the best strategy stops at some number of flips n with number of heads H, can we be sure that it stops at or before H heads on all smaller numbers of flips m<n". We could ask the same question with ratio of heads (i.e. payoff) substituted for actual number of heads. Is this what you're asking?

Title: Re: Coin Flip Game Worth (solution?)
Post by tim on Aug 10^th, 2002, 6:50pm

It is not hard to prove that if you are willing to stop at H heads after N flips, you should accept H heads for any number of flips <= N.

Let f(H,T) = 1 mean that you will continue flipping when you have H heads and T tails. f(H,T) = 0 means you stop. Let v(H,T) be the average payoff from continuing. For any optimal strategy, f(H,T) = 0 iff v(H,T) <= H/(H+T).

Now, a simple induction argument shows that for any optimal strategy, f(H,T+1) = 0 implies f(H+1,T) = 0 (in particular, there cannot be a smallest T for which f(H,T+1) = 0 and f(H+1,T) = 1). We already know that the optimal strategy has f(H,T) = 1 for all H <= T, so we need consider only H > T.

Now suppose that f(H,T+1) = 0. Then f(H+1,T) = 0, and hence
v(H,T) = 0.5 H / (H+T+1) + 0.5(H+1) / (H+T+1)
= (H+0.5) / (H+T+1)
= (2H+1) / 2(H+T+1)
= (2H+1)(H+T) / 2(H+T+1)(H+T)
= (2H^2+H+2HT+T) / 2(H+T+1)(H+T)
< (2H^2+H+2HT+H) / 2(H+T+1)(H+T) since H > T,
= 2H(H+T+1) / 2(H+T+1)(H+T)
= H / (H+T).
Any optimal strategy has f(H,T) = 0 when v(H,T) <= H/(H+T), so f(H,T) = 0.

Thus if you accept H heads in N flips for some N, you should accept H heads in N-1 flips. Continuing by induction, you should accept H heads in any number of flips M where M <= N.

In general, f(H,T) = 0 implies f(h,t) = 0 for all h >= H and t <= T.

I'm still trying to find stronger relations.

Title: Re: Coin Flip Game Worth (solution?)
Post by Eric Yeh on Aug 10^th, 2002, 7:41pm

Alex, Tim,

Sorry guys, that one was a victim of typing too fast. :P I agree that what I wrote makes no sense without Alex's change, and also that it is then pretty clear as Tim suggested.

What I meant to write was this: if you stop at H/n = x, do you also stop at every H'/m = x where m>n? I.e. if you stop at 4/5 do you also stop at 8/10, 44/55 etc. I think it should be fairly straightforward since the "stopping value" has to go to .5 as n -> infinity, but I haven't really worked out any of the details yet. I guess maybe more interesting would be to show that the stopping value is monotonically decreasing, which seems the intuitive thing.

Best,
Eric

Title: Re: Coin Flip Game Worth (solution?)
Post by tim on Aug 10^th, 2002, 10:45pm

No, the stopping value does not monotonically decrease. That's what's making it so hard :-/

If it did, then anywhere after a value of 2/3, f(H,T) = 0 would imply f(H+1,T+1) = 0. I've already tested that class of strategies; the best one has a value of about $0.7904.

So far, I've got a strategy asymptotically based on H > T+sqrt(T) that manages to get $0.79292+.

It seems that my suspicion that the value of the game might be sqrt(pi/5) didn't work. :(

Title: Re: Coin Flip Game Worth (solution?)
Post by Eric Yeh on Aug 10^th, 2002, 11:01pm

Tim,

How did you test that entire class of strategies conclusively? There are arbitrarily many monotonically decreasing fns... I don't believe there's a clear way to see the optimal strategy in that subset.

Plus, why after 2/3? No matter what, f(H,T) = 0 would imply f(H+1,T+1) = 0. Plus, you would never get there anyway. Plus, you don't stop at 2/3! Hm, I'm afraid I don't understand much of your post at all! Apologies if I am just missing the key; it's a bit late.

I haven't worked seriously on this problem since long before giving it to Will, but from what I remember of my work from before, I think got some strategies that pay around 81 cents. I could be misremembering it though.

Best,
Eric

Title: Re: Coin Flip Game Worth (solution?)
Post by tim on Aug 11^th, 2002, 3:49am

Eric: Not quoted in order

Quote:

No matter what, f(H,T) = 0 would imply f(H+1,T+1) = 0

We know that f(1,0)=0: you definitely stop when your first flip is a head!
If f(H,T)=0 generally implied f(H+1,T+1)=0, then f(2,1)=0. That is, we should stop at 2 heads and 1 tail, which we know isn't a good idea.

Quote:

Plus, you don't stop at 2/3

Not at 2 heads out of 3 flips, no. But if your sequence of stopping values is monotonically decreasing toward 1/2, then at some stage it must below 2/3. Thus there will be a pair (H,T) such that f(H,T)=0 with value H/(H+T) < 2/3. That is, H < 2T.

Quote:

Plus, you would never get there anyway.

Consider what happens if you are currently at (H-1,T+1). If you get a head, you move to (H,T+1). That isn't a stopping point; it has too many tails. You flip again, getting another head. You've reached (H+1,T+1). Is that a stopping point or not?

Suppose it is not. Then you could flip again to get (H+2,T+1), with a value of:
(H+2) / (H+T+3)
= (H+2)(H+T) / (H+T+3)(H+T)
= (H^2+2H+HT+2T) / (H+T+3)(H+T)
> (H^2+HT+3H) / (H+T+3)(H+T) since H < 2T
= H(H+T+3) / (H+T+3)(H+T)
= H/(H+T).
In other words, the value of (H+2,T+1) is greater than that of (H,T), violating monotonicity.
Hence under the monotonicity assumption, our supposition must be incorrect, and (H+1,T+1) is a stopping point whenever (H,T) is, for H<2T.

Now, we already know that we cannot continue H >= 2T indefinitely, or we get a nonzero chance of never stopping. Hence there is a smallest T such that f(H,T)=0 for H < 2T.

Quote:

How did you test that entire class of strategies conclusively?

For any such T, the strategy is completely determined by a finite number of stopping points before settling into one extra head for each tail in the rest. For any given T value, a catalan sequence can be constructed to evaluate the expected payoff of the infinite portion of the sequence. It turns out that for T>8, the expected payoff decreases rapidly. A simple exhaustive search then suffices for finding all stopping points (h,t) for t<=8. The best one has value bounded above by $0.791, and actually evaluates to $0.79044.

Quote:

I think got some strategies that pay around 81 cents. I could be misremembering it though.

I hope not! I'd love to see some better strategies. I'm starting to get stuck in a rut here :(

Title: Re: Coin Flip Game Worth (solution?)
Post by Eric Yeh on Aug 11^th, 2002, 10:09am

Tim,

Spent so much time responding to you in "The Gods of Gibberland" that I don't have time to write much here. :)

Woops, I think most of our misunderstandings have just been syntactic miscommunications (prob my fault (tho I'm too lazy to reread everything to see); sorry).

First, I thought f(H,T) was f(Heads,Total), but I see now you mean T=Tails. The reason for this was probably:

Second, when I write 2/3 in the context of this problem I actually mean literally two heads, three tails, not any value 2/3. Otherwise I write 4/6 etc. This is why I also thought your "f(x,y)" was my "x/y".

Apologies for the confusion. Many of the things I disagreed with last post I agree are fairly obvious after the clear-up; the couple of things that are not I will think about later. (One thing was the finite values in your conclusive test -- is that also bc of the syntax or am I just missing the reasoning? It seems to me that there should be arbitrarily many as a function of T=Total.)

Ok, gotta jet.

Best,
Eric

Title: Re: Coin Flip Game Worth (solution?)
Post by oliver on Aug 12^th, 2002, 12:36am

Hi Guys, still at work.

I'm short on time ATM, but I saw one thing:

Quote:

In other words that strategy does not terminate with p=1 and therefore you can beat it with (for example) a strategy which does mostly the same things but accepts less once it reaches an n,H situation where non-termination becomes sufficiently likely.

AlexH, IMO that is a tough one. It's certainly not written in the riddle that a strategy has to terminate.
Maybe the payoff converges against a value > 0. (HTHTHTHTHTHT... as an example). Now we have the possiblity to define the "payoff" just as the value of this limit.
Moreso, it feels like if you want the strategy to terminate in any case, you have to "artificially" impose something that this happens. Take the above sequence with H and T always alternating, when do we stop?
To sum up, I think there is the uncertainty of how to define the value of non-terminiating flip sequences, either as the limit, or as zero. This decision will certainly impact the value of the game.

Title: Re: Coin Flip Game Worth (solution?)
Post by AlexH on Aug 12^th, 2002, 1:27am

A strategy can terminate wtih probability 1 and still have lots of sequences (such as THTHTHTHTHTHTHTH....) that never terminate. The problem with having some fixed ratio of H/T required would not be that some sequences never terminate, but that a non-zero measure of sequences would. Since you take your money only after the game concludes its outside the scope of the question to define some non-zero payoff for non-terminating sequences. This shouldn't really be a barrier to any of the kinds of strtategies I can think of.

Title: Re: Coin Flip Game Worth (solution?)
Post by Paul Hsieh on Aug 12^th, 2002, 3:56pm

If you don't have any termination condition, then you can simply follow the rule:

Wait until #H > 0.99999 * #T.

This is a legitimate strategy, but its probability of termination is actually quite low. In my thinking I have basically said, that I have a strategy for up to the first n flips, S_n, and that for any sequence that has not terminated as desired after n flips, simply perform K*n additional flips (where K is very large, like a million) and just take the the result you get. This will result in an expected outcome of (0.5 - epsilon) for any arbitrarilty small epsilon.

These (0.5-epsilon)'s have impact on the computed output and, of course, cannot be ignored in order to ensure that you have a well defined terminating algorithm.

So, by simply letting K and n go off to infinity in a well defined way, you can converge on an outcome, which each instance having a finite predetermined termination upper bound. The final result computed, say V, will then technically be an upper bound for the real realizable outcome. I.e., its really (V-epsilon) for any chosen epsilon > 0.

Hmmm ... it has suddenly occurred to me, that in fact you can perform a slight optimization. Since I have seen that in fact that the rule should be (stop flipping if #H > A * #T), for A ~= 5/4, in fact if after n flips we find that #H > #T >= #H / A, then we should terminate without any additional flips. This would probably represent a very small improvement.

Title: Re: Coin Flip Game Worth (solution?)
Post by AlexH on Aug 12^th, 2002, 7:11pm

At any point you can switch to the strategy "stop once payoff is > .5" and you will terminate with probability 1, so the "continuation value" of any position is >= .5 without worrying about payoff of non-terminating sequences. I think its fine to have an optimal algorithm which has no upper bound on sequence lengths as long as chance of termination goes to 1 as t-> infinity.

I've been spending too much time on 100 prisoners.

Title: Re: Coin Flip Game Worth (solution?)
Post by tim on Aug 12^th, 2002, 10:36pm

Let H(T) be the least number of heads you need before you will accept T tails. For example, we know that H(0)=1 since you should always stop at 1 head if you haven't got any tails yet.

All of my highest-value strategies so far have been of the form

H(T) = T+1 + floor(sqrt(T) + r(T)), where
r(T1) >= r(T0) for T1 > T0, and
0 <= r(T) < 1 for all T.

All such strategies terminate with probability 1. One such strategy achieves an average payoff of a bit more than $0.79292.

Can anyone find a strategy with better average payoff that does not fit this model, or prove that the optimal strategy must be of this form? I've had no luck yet with either side of the question.

Title: Re: Coin Flip Game Worth (solution?)
Post by Kozo Morimoto on Aug 13^th, 2002, 9:37pm

I posted this riddle to another, more technical forum and this is the result:
http://www.wilmott.com/310/today_detail.cfm?articleID=137

So according to this, 0.79295 seems to be answer as a limit of number of flips approach infinity.

However, at infinity, its a whole different ball game and there is a huge thread on the nature of infinity how this affects the answer to this riddle.

Title: Re: Coin Flip Game Worth (solution?)
Post by tim on Aug 14^th, 2002, 3:41am

Kozo: Good lord, what a monster thread! I read 7 pages of discussion, and there were still some participants unconvinced that the value of the game was less than 1!

I noticed that some of them are as interested in finding the Chow&Robbins paper as I am :)

Title: Re: Coin Flip Game Worth (solution?)
Post by AlexH on Aug 14^th, 2002, 4:25am

A 100,000 flip optimal strategy with a fallback to quit when x>=.5 wins yields .79294.

Edited :

Assuming my program is correct, we do see higher thresholds than the 1+T+sqrt(T) formula. For example, the 10^5 flips scheme above has stopping criterion H-T =50 at T = 1686 where the formula says we should require at most H-T> 43 at that point. The approximation of the optimal scheme by this bounded flip method is pessimistic in the sense that it will stop too early because it underestimates the continuation value. This means the stopping criteria given by the approximation are lower bounds on the true optimal criteria.

Title: Re: Coin Flip Game Worth (solution?)
Post by Eric Yeh on Aug 14^th, 2002, 6:09am

I agree with Alex -- I dug out my old results and show the same value @ 100,000.

Title: Re: Coin Flip Game Worth (solution?)
Post by AlexH on Aug 14^th, 2002, 3:01pm

Interestingly even the early thresholds keep rising as you up n. On a 2E6 flip game I get payoff .792952, but the interesting thing is that the stopping criteria rise even early on when you lengthen the game. The first criteria which changed was surplus of 15. You don't require a surplus of 15 heads until 122 tails in the 1E5 flips, while you require it at 121 tails with 2E6 flips. This continues so, for example the 50 surplus I mentioned above happens at 1646 tails instead of 1686 as in 1E5 flips. Maybe I can run a big number overnight later and test say 5E7. I can't think of any way to beat n^1.5 run time though so I can only push it so far.

Title: Re: Coin Flip Game Worth (solution?)
Post by Eric Yeh on Aug 14^th, 2002, 3:04pm

n^1.5 is already impressive -- how do you get it below quadratic?

Title: Re: Coin Flip Game Worth (solution?)
Post by AlexH on Aug 14^th, 2002, 4:56pm

I'll post the code once I get the chance to do some last tweaks. Kind of busy today though so probably not tonight.

Here is the crux of how we trim our problem so that we can do n^1.5. We're working backwards from the boundary at n flips, computing the i-1 flip data from the ith flip data. We only wind up doing computations for an O(sqrt(n)) neighborhood of the 50/50 line. On the high side, once we detect the surplus needed for stopping for this # of flips we don't have to compute all higher surpluses' values; we can just compute them when needed since we know that they will be the stopping payoff at those points. On the low side we rely on the fact that we're using bounded precision arithmetic. Look at the question "for a certain combination of (surplus,flips) where surplus is negative, whats the chance we break .5 payoff before we hit n flips". For large n we have a normal distribution, with deviation sqrt(n)/2. We use that to bound how far below 50/50 we have to compute. Below that bound we just use .5 for the values. We can pick a constant multiple of deviations thats big enough to force the error generated by this to be below the precision of a double and we still win big in terms of run time for large n. There are few more details/tweaks but those are the big points.

Title: Re: Coin Flip Game Worth (solution?)
Post by AlexH on Aug 14^th, 2002, 5:04pm

I'll post the code once I get the chance to do some last tweaks. Kind of busy today though so probably not tonight.

Here is the crux of how we trim our problem so that we can do n^1.5. We're working backwards from the boundary at n flips, computing the i-1 flip data from the ith flip data. We only wind up doing computations for an O(sqrt(n)) neighborhood of the 50/50 line. On the high side, once we detect the surplus needed for stopping for this # of flips we don't have to compute all higher surpluses' values; we can just compute them when needed since we know that they will be the stopping payoff at those points. On the low side we rely on the fact that we're using bounded precision arithmetic. Look at the question "for a certain combination of (surplus,flips) where surplus is negative, whats the chance we break .5 payoff before we hit our limit n flips". For large n we have a normal distribution, with deviation sqrt(n)/2. We use that to bound how far below 50/50 we have to compute. Below that bound we just use .5 for the values. We can pick a constant multiple of deviations thats big enough to force the error generated by this to be below the precision of a double and we still win big in terms of run time for large n. There are few more details/tweaks but those are the big points.

Title: Re: Coin Flip Game Worth (solution?)
Post by tim on Aug 14^th, 2002, 8:15pm

Thanks, I'm glad someone managed to do better, even if it did disconfirm my hypothesis.

Yes, your evaluation method looks similar to mine. I only took it out to about 10000 flips though, since I needed to do rapid evaluations for a search.

I did suspect that continuing further would affect earlier results. What a horrid problem :-/

Title: Re: Coin Flip Game Worth (solution?)
Post by AlexH on Aug 14^th, 2002, 10:26pm

Its not the prettiest code I've ever written, but hopefully its understandable.

On my pokey celeron at home it takes about 45 seconds on a 1E6 problem. Memory may be as much of a problem as time as we grow n since I didn't mess about with trying to code it for sqrt(n) memory. It could be rewritten to do so if I get the time/inclination, but at the moment its linear memory in n. This means a 1E7 problem takes 80MB (and a ballpark of 30 minutes). The 1E7 problem paid off 0.792953042848

Also, while I did optimize the algorithm reasonably, there is more that could be done at a low-level coding standpoint. It feels like maybe there should be some way to beat the system and cut down to less than n^1.5 but I don't see it atm. The code is C++ though its 98 percent plain C.

#include <stdio.h> #include <iostream.h> #include <math.h> #define DEVIATIONS 6.0 // gives error threshold 1E-9 (at mean line error << 1E-18) // cutoffs[i] is lowest # of heads for which we require surplus >= i to stop int *cutoffs; // we could get down to O(sqrt(flips)) memory but we'll have to be very // careful with the indicies. Currently its O(n) space and O(n^1.5) time double computeFlipValue(int flips,int numberCutoffs){ int curFlips,curHeads; double stopValue, contValue; double *values; int lowBound, lastUpperBound, deviationBound, surplus; values = new double[flips+1]; int flipsOverTwo = flips >> 1; // k * deviation + extra buffer so that we compute all for small problems deviationBound = ceil(sqrt((double) flips) * .5 * DEVIATIONS) + 100; //Set boundary conditions lastUpperBound = (flips >> 1) + 1; for(curHeads=0;curHeads<lastUpperBound;curHeads++){ values[curHeads] = .5; } values[lastUpperBound] = (double) lastUpperBound / (double) flips; // all boundary values higher than lastUpperBound get computed in loops as needed // Compute curFlips flips data from curFlips+1 flips data for (curFlips=flips-1;curFlips>=0;curFlips--){ curHeads = (curFlips-flipsOverTwo > 0) ? curFlips-flipsOverTwo : 0; // skip triangle of all .5 //error in cutoffs region < 1E-18 with coeff 6.0 lowBound = (curFlips >> 1) - deviationBound; curHeads = (lowBound > curHeads) ? lowBound : curHeads; // stopping point can't drop more than 1 head per flip, so don't need to check // Most of the running time is spent here. Should optimize. for(;curHeads < lastUpperBound-1 ;curHeads++){ values[curHeads] = .5 * (values[curHeads] + values[curHeads+1]); } // ASSERT: curHeads == lastUpperBound - 1 for(;curHeads<curFlips;curHeads++){ stopValue = (double) curHeads/(double) curFlips; contValue = .5 * (values[curHeads] + values[curHeads+1]); if (stopValue > contValue) { // true ==> found cutoff surplus = (curHeads << 1) - curFlips; if(surplus < numberCutoffs) // array bounds check should never fail cutoffs[surplus] = curHeads; // last overwrite will be on lowest curFlips for given surplus values[curHeads] = stopValue; lastUpperBound = curHeads; break; } values[curHeads] = contValue; /* We need to set up the correct values[curHeads+2] from the curFlips+1 round so that our next iteration computes contValue properly. We can compute it directly because we know it is past the cutoff from that round. */ values[curHeads+2] = (double) (curHeads+2) / (double) (curFlips+1); } if (curHeads == curFlips){ // true means we never hit a stop point if (curFlips > 0){ values[curHeads] = 1.0; lastUpperBound = curHeads; cutoffs[curHeads] = curHeads; // curHeads is the surplus since curHeads==curFlips } else{ // curFlips=curHeads=0 values[0] = .5 * (values[0] + values[1]); } } } contValue = values[0]; //delete values; return contValue; } void displayCutoffs(int flips,int numberCutoffs){ int i; printf("Surplus\t Heads\n"); for(i=1;i<numberCutoffs;i++){ if (cutoffs[i] == -1){ printf("Largest cutoff was %d\n",i-1); break; } printf("%d \t %d\n", i, cutoffs[i]); } } int main(){ char line[80]; int flips = 1.0E6; int numberCutoffs; double gameValue; int i; cin >> flips; numberCutoffs = (int) (ceil(sqrt(0.5 * flips))+1); cutoffs = new int[numberCutoffs]; for(i=0;i<numberCutoffs;i++){ cutoffs[i] = -1; } gameValue=computeFlipValue(flips,numberCutoffs); displayCutoffs(flips >> 1,numberCutoffs); printf("Value at %d flips = %14.12f\n",flips,gameValue); // cin >> line; return (int) (gameValue * 1.0E8); }

Title: Re: Coin Flip Game Worth (solution?)
Post by AlexH on Aug 18^th, 2002, 9:34pm

I forgot to mention that shortly after this post it occured to me that we could get it down to n^1.25 by pulling another fixed precision trick and calculating columns of cells from other columns around n^.5 away. Actually implementing this would be a serious pain though so I'm not going to :P. I still think that there ought to be some sneaky way to do better.

Title: Re: Coin Flip Game Worth (solution?)
Post by jdaw1 on Oct 16^th, 2005, 4:20pm

There is indeed an easy way to do better.

Imagine starting with a spreadsheet, with a large square of cells. Interior cells contain the Maximum of:
-- stop now;
-- average of cells to right (one more tail) and down (one more head).
The right hand wall, where t>h, contains 0.5, that being the gazillion-flip score. (It is trivial to prove that the probability of reaching h=t starting anywhere is 1, though the expected time to reaching it is infinite if t≠h.)
The top wall is an alway-flip formula, because h=0 (so we wouldn't want to stop) and that avoids the h=t=0 nastiness.

Scores depend on the size of the square, on n. My code, also in C-like C++ with an algorithm using time n^2 and memory n, was compiled using XCode and run on an old Apple Mac. (Please check my numbers on a different processor, different code, different compiler, etc.)

Code:

0.7770833333333333481 3
0.7858662629327854976 9
0.7896264796342247205 27
0.7914761539909933585 81
0.7922934641039933723 243
0.7926572763570003399 729
0.7928209434352511131 2187
0.7928941655924004461 6561
0.7929269252779566068 19683
0.7929416026039753929 59049
0.7929481759328098622 177147
0.7929511190864083625 531441

and

Code:

0.7708333333333332593 2
0.7799479166666667407 4
0.7852476574125744069 8
0.7881908989715458169 16
0.7900232244244766999 32
0.7911968421606350166 64
0.7918975370793603918 128
0.7923182242915052242 256
0.7925704383240074202 512
0.7927224938475999627 1024
0.7928144143569131330 2048
0.7928697526753007985 4096
0.7929030566167816207 8192
0.7929231096159555792 16384
0.7929351959569922448 32768
0.7929424763794645781 65536
0.7929468624282201006 131072
0.7929495040795999650 262144

(Full C double precision, printed as %0.19lf, is shown but not believed.)

These scores increase, and the amount of each increase is very nearly z times the previous improvement, where z=0.448 in the powers of 3, and 0.602 in the powers of 2. So this behaving like EV+const*z^m, where m is the row number (the log of n). Hence the EV is an easily-estimable value, that being 0.7929535..., with the next digit probably being 0 or 1.

In other words, the low-n computations give a result that behaves well as a function of n, and that can be used to estimate the high-n value.

Alas, this number does not appear in the Inverse Symbolic Calculator (http://oldweb.cecm.sfu.ca/projects/ISC/), suggesting that it might be a once-off not-very-useful transcendental number.

Title: Re: Coin Flip Game Worth (solution?)
Post by jdaw1 on Nov 9^th, 2005, 8:42am

The value of this game is approximately 0.792953506407..., with the next digit possibly being 7. A justification of this claim, with full working and C code, is at www.jdawiseman.com/papers/easymath/coin-stopping.html (http://www.jdawiseman.com/papers/easymath/coin-stopping.html). Comments welcomed, ideally by email (http://www.jdawiseman.com/author.html).

Title: Re: Coin Flip Game Worth (solution?)
Post by James Fingas on Jul 24^th, 2006, 10:11am

Although it looks like my primitive spreadsheet can't get a more accurate answer than your fancy programs (I have the optimal payout between 0.7922 and 0.7937), I would like to contribute a proof that there is actually a maximum payout that must be less than 1.

First, I define P as the payout given a number of heads H and a total number of flips F (P=H/F).

Now I define a game where we keep flipping until we get a payout P. We already know that for P<=0.5, this game always terminates. For P>0.5, there is a finite possibility that the game will never terminate.

Now I define Q(P) as the probability that given the payout P, my modified game will terminate. The Q(P) function is monotonically decreasing, but it's something of a beast because for P>0.5 it's everywhere discontinuous. I have attached a graph showing my simulated results.

Now suppose (playing the original game again) we knew exactly when every sequence of flips would reach its maximum point. This would allow the ideal strategy. But how many sequences reach a maximum payout of P? The answer is in the size of the jump in Q(P). In a regular function, this would be the derivative, Q'(P).

Therefore, given the function Q(P), the value of the game using the optimal strategy is bounded by the integral of PQ'(P). Based on my simulations of Q(P), I have calculated this integral to be roughly 0.8157. The game cannot be worth more than this.

Now for some other observations:
1) The behaviour of Q(P) should make it clear why this problem has no closed-form solution.

2) This method also shows that it is unlikely that there is a way to turn this discrete problem into a continuous one for the sake of easier math. The solution depends strongly on us being forced to choose specific cutoff points.

NOTE: Although I have glossed over taking the derivative of an everywhere-distcontinuous function ;), the math still works--I used finite differences and summations in place of the derivative and integral.

Title: Re: Coin Flip Game Worth (solution?)
Post by BNC on Jul 24^th, 2006, 10:55am

James: It's been ages! ;D :D

Title: Re: Coin Flip Game Worth (solution?)
Post by towr on Jul 24^th, 2006, 3:22pm

Wow.. after two and a half year, he's back.. So what ever happened?

[edit]Also, there's no attachment. The attachment directory is probably still/again full[/edit]

Title: Re: Coin Flip Game Worth (solution?)
Post by Icarus on Jul 24^th, 2006, 5:06pm

Yes, we're all glad to hear from you again! (If you look in the "general" forum, you'll see that we were bemoaning the loss of you and several other former regulars just last week! :P)

Q(P) sounds like an interesting function. I've made one attempt at it, but flubbed up (my result was 0 everywhere). jdaw1 is probably correct as to the value (I've not reviewed his code or the supporting arguments), but this looks like it should be a very nice argument, from the portion you gave.

Title: Re: Coin Flip Game Worth (solution?)
Post by Eric Yeh on Jul 24^th, 2006, 7:43pm

omg i cant believe you guys are still at this!! hahaha. moreover, i cant believe i still get emailed when ppl post on this thread! HAHA!

all those years ago i had a follow-up to 'gods of gibberland' that i intended to post as soon as i figured out the solution myself. unfortunately, it was too hard and i never did!! haha. guess i shoulda gotten help from all of you smart guys out there when i had the chance!! :) <sigh>

Title: Re: Coin Flip Game Worth (solution?)
Post by James Fingas on Jul 25^th, 2006, 6:02am

I guess I owe you guys and explanation. This forum is awesome, and I really enjoy sinking my teeth into a good puzzle, but it kills my productivity at work :(, so I kicked the habit.

But just the other day, I tried to come up with a way to solve this particular problem, and I didn't, but I came up with this maximum value, so figured I might as well post it.

Once an addict, always an addict...

Title: Re: Coin Flip Game Worth (solution?)
Post by jdaw1 on Jul 25^th, 2006, 6:33am

James: hello from a stranger. Indeed, from a stranger who doesn't properly understand what you've done, and would like to do so. Please post much more about your algorithm for an upper bound.

Thank you.

Title: Re: Coin Flip Game Worth (solution?)
Post by malchar on Jun 27^th, 2008, 12:04pm

I hate to rehash another old thread, but there's something alluring about the small number of "unsolved" puzzles on the riddles site. Given the apparent elegance of this problem, I was surprised by the conclusion of the author of the paper that was linked somewhere on this thread. That is, that this problem appears to have no known connection to any other region of mathematics. That is to say that the calculated values don't appear to approach any elegant number.
Anyway, I have little programming knowledge and prefer to read and theorize about problems rather than actually calculate things. However, I am kind of curious about your calculations that the game's value has a maximum around $0.81 because I generally liked to believe that the value of the game should be just under if not equal to $1. Then again, I admit that I have a dubious understanding of infinity in the context of this problem.
I thought it would be interesting to think about actually running this game and am kind of surprised that I have never heard of it being done. A casino could run the game at the elegant rate of $.80 and the players would obviously be limited to small numbers of flips based on the amount of real time it would take.
An unusual question I have is why is it so much easier to locate a minimum bound and slowly push upwards? The problem with settling on a minimum bound (for a casino, for example) would be that the house could lose money if the true value is above the bound. I guess I just have a lot of trouble conceptualizing that a maximum bound even exists at all, probably because I don't understand the math.