Author |
Topic: Coin Flip Game Worth (solution?) (Read 22639 times) |
|
Nicodemus
Guest
|
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 31st, 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 31st, 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 31st, 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 31st, 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) / ((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.
|
|
IP Logged |
|
|
|
Eric Yeh
Senior Riddler
Gender: 
Posts: 318
|
|
Re: Coin Flip Game Worth (solution?)
« Reply #5 on: Aug 1st, 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 1st, 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 1st, 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 1st, 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 1st, 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 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
|
|
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 1st, 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 2nd, 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 2nd, 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 3rd, 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 3rd, 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 3rd, 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 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 
|
|
IP Logged |
|
|
|
anshil
Newbie
Posts: 41
|
|
Re: Coin Flip Game Worth (solution?)
« Reply #16 on: Aug 5th, 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 5th, 2002, 6:24am by anshil » |
IP Logged |
|
|
|
Eric Yeh
Senior Riddler
Gender:
Posts: 318
|
|
Re: Coin Flip Game Worth (solution?)
« Reply #17 on: Aug 5th, 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 5th, 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 5th, 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>(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  .
|
|
IP Logged |
|
|
|
Eric Yeh
Senior Riddler
Gender:
Posts: 318
|
|
Re: Coin Flip Game Worth (solution?)
« Reply #20 on: Aug 5th, 2002, 10:45am » |
Quote Modify
|
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
|
|
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 5th, 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 5th, 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 5th, 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 5th, 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 5th, 2002, 12:09pm by oliver » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print