Author 
Topic: Coin Flip Game Worth (solution?) (Read 22006 times) 

Nicodemus
Guest


Coin Flip Game Worth (solution?)
« on: Jul 31^{st}, 2002, 12:31am » 
Quote Modify
Remove

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?


IP Logged 



AlexH
Full Member
Posts: 156


Re: Coin Flip Game Worth (solution?)
« Reply #1 on: Jul 31^{st}, 2002, 2:46am » 
Quote Modify

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


IP Logged 



Kozo Morimoto
Guest


Re: Coin Flip Game Worth (solution?)
« Reply #2 on: Jul 31^{st}, 2002, 7:45am » 
Quote Modify
Remove

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


IP Logged 



Nicodemus
Guest


Re: Coin Flip Game Worth (solution?)
« Reply #3 on: Jul 31^{st}, 2002, 12:35pm » 
Quote Modify
Remove

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!


IP Logged 



Kozo Morimoto
Guest


Re: Coin Flip Game Worth (solution?)
« Reply #4 on: Jul 31^{st}, 2002, 8:58pm » 
Quote Modify
Remove

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) / ((ki)!*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/(ki)!/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.


IP Logged 



Eric Yeh
Senior Riddler
Gender:
Posts: 318


Re: Coin Flip Game Worth (solution?)
« Reply #5 on: Aug 1^{st}, 2002, 7:25am » 
Quote Modify

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


IP Logged 
"It is better to have puzzled and failed than never to have puzzled at all."



Kozo Morimoto
Guest


Re: Coin Flip Game Worth (solution?)
« Reply #6 on: Aug 1^{st}, 2002, 2:36pm » 
Quote Modify
Remove

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.


IP Logged 



Eric Yeh
Senior Riddler
Gender:
Posts: 318


Re: Coin Flip Game Worth (solution?)
« Reply #7 on: Aug 1^{st}, 2002, 3:06pm » 
Quote Modify

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


IP Logged 
"It is better to have puzzled and failed than never to have puzzled at all."



Kozo Morimoto
Guest


Re: Coin Flip Game Worth (solution?)
« Reply #8 on: Aug 1^{st}, 2002, 6:05pm » 
Quote Modify
Remove

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.


IP Logged 



Eric Yeh
Senior Riddler
Gender:
Posts: 318


Re: Coin Flip Game Worth (solution?)
« Reply #9 on: Aug 1^{st}, 2002, 8:35pm » 
Quote Modify

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 semirandom  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 .783/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 halfchance 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


IP Logged 
"It is better to have puzzled and failed than never to have puzzled at all."



Kozo Morimoto
Guest


Re: Coin Flip Game Worth (solution?)
« Reply #10 on: Aug 1^{st}, 2002, 10:58pm » 
Quote Modify
Remove

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?


IP Logged 



tim
Junior Member
Posts: 81


Re: Coin Flip Game Worth (solution?)
« Reply #11 on: Aug 2^{nd}, 2002, 12:39am » 
Quote Modify

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


IP Logged 



Eric Yeh
Senior Riddler
Gender:
Posts: 318


Re: Coin Flip Game Worth (solution?)
« Reply #12 on: Aug 2^{nd}, 2002, 5:52am » 
Quote Modify

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


IP Logged 
"It is better to have puzzled and failed than never to have puzzled at all."



tim
Junior Member
Posts: 81


Re: Coin Flip Game Worth (solution?)
« Reply #13 on: Aug 3^{rd}, 2002, 8:28pm » 
Quote Modify

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


IP Logged 



Eric Yeh
Senior Riddler
Gender:
Posts: 318


Re: Coin Flip Game Worth (solution?)
« Reply #14 on: Aug 3^{rd}, 2002, 9:55pm » 
Quote Modify

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


IP Logged 
"It is better to have puzzled and failed than never to have puzzled at all."



tim
Junior Member
Posts: 81


Re: Coin Flip Game Worth (solution?)
« Reply #15 on: Aug 3^{rd}, 2002, 11:21pm » 
Quote Modify

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


IP Logged 



anshil
Newbie
Posts: 41


Re: Coin Flip Game Worth (solution?)
« Reply #16 on: Aug 5^{th}, 2002, 6:24am » 
Quote Modify

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?

« Last Edit: Aug 5^{th}, 2002, 6:24am by anshil » 
IP Logged 



Eric Yeh
Senior Riddler
Gender:
Posts: 318


Re: Coin Flip Game Worth (solution?)
« Reply #17 on: Aug 5^{th}, 2002, 8:31am » 
Quote Modify

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


IP Logged 
"It is better to have puzzled and failed than never to have puzzled at all."



anshil
Newbie
Posts: 41


Re: Coin Flip Game Worth (solution?)
« Reply #18 on: Aug 5^{th}, 2002, 10:18am » 
Quote Modify

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.


IP Logged 



oliver
Newbie
Posts: 25


Re: Coin Flip Game Worth (solution?)
« Reply #19 on: Aug 5^{th}, 2002, 10:36am » 
Quote Modify

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>(pNH)/(1p) 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 .


IP Logged 



Eric Yeh
Senior Riddler
Gender:
Posts: 318


Re: Coin Flip Game Worth (solution?)
« Reply #20 on: Aug 5^{th}, 2002, 10:45am » 
Quote Modify

Anshil, How interesting, you've rediscovered 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


IP Logged 
"It is better to have puzzled and failed than never to have puzzled at all."



Eric Yeh
Senior Riddler
Gender:
Posts: 318


Re: Coin Flip Game Worth (solution?)
« Reply #21 on: Aug 5^{th}, 2002, 10:53am » 
Quote Modify

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


IP Logged 
"It is better to have puzzled and failed than never to have puzzled at all."



oliver
Newbie
Posts: 25


Re: Coin Flip Game Worth (solution?)
« Reply #22 on: Aug 5^{th}, 2002, 11:14am » 
Quote Modify

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.


IP Logged 



Eric Yeh
Senior Riddler
Gender:
Posts: 318


Re: Coin Flip Game Worth (solution?)
« Reply #23 on: Aug 5^{th}, 2002, 11:17am » 
Quote Modify

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


IP Logged 
"It is better to have puzzled and failed than never to have puzzled at all."



oliver
Newbie
Posts: 25


Re: Coin Flip Game Worth (solution?)
« Reply #24 on: Aug 5^{th}, 2002, 12:05pm » 
Quote Modify

Haha, two edged compliment. Solving the riddle you refer to without knowing complex analysis would have been more praiseworthy. Btw., I don't see you _solving_ any riddles? Know all the solutions? Lazy?

« Last Edit: Aug 5^{th}, 2002, 12:09pm by oliver » 
IP Logged 



