Author |
Topic: Coin Flip Game Worth (solution?) (Read 22594 times) |
|
AlexH
Full Member
Posts: 156
|
 |
Re: Coin Flip Game Worth (solution?)
« Reply #75 on: Aug 18th, 2002, 9:34pm » |
 Quote  Modify
|
I forgot to mention that shortly after this post it occured to me that we could get it down to n1.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  . I still think that there ought to be some sneaky way to do better.
|
|
 IP Logged |
|
|
|
jdaw1
Newbie
Posts: 3
|
|
Re: Coin Flip Game Worth (solution?)
« Reply #76 on: Oct 16th, 2005, 4:20pm » |
Quote Modify
|
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, suggesting that it might be a once-off not-very-useful transcendental number.
|
|
IP Logged |
|
|
|
jdaw1
Newbie
Posts: 3
|
|
Re: Coin Flip Game Worth (solution?)
« Reply #77 on: Nov 9th, 2005, 8:42am » |
Quote Modify
|
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. Comments welcomed, ideally by email.
|
| « Last Edit: Nov 9th, 2005, 9:01am by jdaw1 » |
IP Logged |
|
|
|
James Fingas
Uberpuzzler
Gender: 
Posts: 949
|
|
Re: Coin Flip Game Worth (solution?)
« Reply #78 on: Jul 24th, 2006, 10:11am » |
Quote Modify
|
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.
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
BNC
Uberpuzzler
Gender:
Posts: 1732
|
|
Re: Coin Flip Game Worth (solution?)
« Reply #79 on: Jul 24th, 2006, 10:55am » |
Quote Modify
|
James: It's been ages!  
|
|
IP Logged |
How about supercalifragilisticexpialidociouspuzzler [Towr, 2007]
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Coin Flip Game Worth (solution?)
« Reply #80 on: Jul 24th, 2006, 3:22pm » |
Quote Modify
|
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]
|
| « Last Edit: Jul 24th, 2006, 3:27pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Coin Flip Game Worth (solution?)
« Reply #81 on: Jul 24th, 2006, 5:06pm » |
Quote Modify
|
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! )
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.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Eric Yeh
Senior Riddler
Gender:
Posts: 318
|
|
Re: Coin Flip Game Worth (solution?)
« Reply #82 on: Jul 24th, 2006, 7:43pm » |
Quote Modify
|
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>
|
|
IP Logged |
"It is better to have puzzled and failed than never to have puzzled at all."
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: Coin Flip Game Worth (solution?)
« Reply #83 on: Jul 25th, 2006, 6:02am » |
Quote Modify
|
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...
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
jdaw1
Newbie
Posts: 3
|
 |
Re: Coin Flip Game Worth (solution?)
« Reply #84 on: Jul 25th, 2006, 6:33am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
malchar
Junior Member
Gender:
Posts: 54
|
|
Re: Coin Flip Game Worth (solution?)
« Reply #85 on: Jun 27th, 2008, 12:04pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print