wu :: forums « wu :: forums - Coin Flip Game Worth (solution?) » Welcome, Guest. Please Login or Register. Jan 21st, 2022, 11:39am RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    hard (Moderators: towr, Icarus, william wu, SMQ, Grimbal, ThudnBlunder, Eigenray)    Coin Flip Game Worth (solution?) « Previous topic | Next topic »
 Pages: 1 2 3 4 Reply Notify of replies Send Topic Print
 Author Topic: Coin Flip Game Worth (solution?)  (Read 22052 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&#8800;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

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

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?

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.

 IP Logged

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
 Pages: 1 2 3 4 Reply Notify of replies Send Topic Print

 Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium => hard   - what am i   - what happened   - microsoft   - cs   - putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »