wu :: forums « wu :: forums - Coin Flip Game Worth (solution?) » Welcome, Guest. Please Login or Register. Jan 22nd, 2022, 1:41pm RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    hard (Moderators: Grimbal, Icarus, Eigenray, SMQ, towr, ThudnBlunder, william wu)    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 22058 times)
Eric Yeh
Senior Riddler

Gender:
Posts: 318
 Re: Coin Flip Game Worth (solution?)   « Reply #25 on: Aug 5th, 2002, 12:16pm » Quote Modify

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
 « Last Edit: Aug 5th, 2002, 12:17pm by Eric Yeh » 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 #26 on: Aug 5th, 2002, 12:28pm » Quote Modify

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
 « Last Edit: Aug 5th, 2002, 12:29pm by oliver » IP Logged
Kozo Morimoto
Guest

 Re: Coin Flip Game Worth (solution?)   « Reply #27 on: Aug 5th, 2002, 7:17pm » Quote Modify Remove

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...
 IP Logged
Eric Yeh
Senior Riddler

Gender:
Posts: 318
 Re: Coin Flip Game Worth (solution?)   « Reply #28 on: Aug 5th, 2002, 8:27pm » Quote Modify

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
 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 #29 on: Aug 5th, 2002, 9:15pm » Quote Modify

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)
 IP Logged
Eric Yeh
Senior Riddler

Gender:
Posts: 318
 Re: Coin Flip Game Worth (solution?)   « Reply #30 on: Aug 5th, 2002, 9:42pm » Quote Modify

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
 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 #31 on: Aug 5th, 2002, 9:57pm » Quote Modify

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.
 IP Logged
Eric Yeh
Senior Riddler

Gender:
Posts: 318
 Re: Coin Flip Game Worth (solution?)   « Reply #32 on: Aug 5th, 2002, 10:38pm » Quote Modify

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
 « Last Edit: Aug 5th, 2002, 10:39pm by Eric Yeh » 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 #33 on: Aug 5th, 2002, 11:27pm » Quote Modify

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.
 « Last Edit: Aug 6th, 2002, 12:18am by anshil » IP Logged
Eric Yeh
Senior Riddler

Gender:
Posts: 318
 Re: Coin Flip Game Worth (solution?)   « Reply #34 on: Aug 6th, 2002, 7:41am » Quote Modify

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*.5n 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
 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 #35 on: Aug 6th, 2002, 9:00am » Quote Modify

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.
 IP Logged
Kozo Morimoto
Guest

 Re: Coin Flip Game Worth (solution?)   « Reply #36 on: Aug 6th, 2002, 4:51pm » Quote Modify Remove

"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?
 IP Logged
Paul Hsieh
Guest

 Re: Coin Flip Game Worth (solution?)   « Reply #37 on: Aug 7th, 2002, 8:01am » Quote Modify Remove

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.
 IP Logged
Paul Hsieh
Guest

 Re: Coin Flip Game Worth (solution?)   « Reply #38 on: Aug 7th, 2002, 5:08pm » Quote Modify Remove

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

Code:
 #include   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 #include   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 ...
 IP Logged
tim
Junior Member

Posts: 81
 Re: Coin Flip Game Worth (solution?)   « Reply #39 on: Aug 7th, 2002, 7:06pm » Quote Modify

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.
 IP Logged
tim
Junior Member

Posts: 81
 Re: Coin Flip Game Worth (solution?)   « Reply #40 on: Aug 7th, 2002, 7:59pm » Quote Modify

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...
 IP Logged
Paul Hsieh
Guest

 Re: Coin Flip Game Worth (solution?)   « Reply #41 on: Aug 7th, 2002, 11:36pm » Quote Modify Remove

Interesting!    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 ...
 IP Logged
tim
Junior Member

Posts: 81
 Re: Coin Flip Game Worth (solution?)   « Reply #42 on: Aug 8th, 2002, 1:15am » Quote Modify

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!
 IP Logged
oliver
Newbie

Posts: 25
 Re: Coin Flip Game Worth (solution?)   « Reply #43 on: Aug 8th, 2002, 2:39am » Quote Modify

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.
 IP Logged
tim
Junior Member

Posts: 81
 Re: Coin Flip Game Worth (solution?)   « Reply #44 on: Aug 8th, 2002, 3:39am » Quote Modify

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.
 IP Logged
oliver
Newbie

Posts: 25
 Re: Coin Flip Game Worth (solution?)   « Reply #45 on: Aug 8th, 2002, 5:02am » Quote Modify

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 T0 times without getting a head, the remainder of the game would be equivalent to a freshly started game with a prize of H/(T+T0).
Doesn't sound very convincing, does it?

 IP Logged
Eric Yeh
Senior Riddler

Gender:
Posts: 318
 Re: Coin Flip Game Worth (solution?)   « Reply #46 on: Aug 8th, 2002, 5:36am » Quote Modify

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 T0, 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
 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 #47 on: Aug 8th, 2002, 6:47am » Quote Modify

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.

 IP Logged
Eric Yeh
Senior Riddler

Gender:
Posts: 318
 Re: Coin Flip Game Worth (solution?)   « Reply #48 on: Aug 8th, 2002, 4:19pm » Quote Modify

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
 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 #49 on: Aug 9th, 2002, 3:05am » Quote Modify

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) Bn -> {0,1}, where Bn 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).

 « Last Edit: Aug 9th, 2002, 4:29am by oliver » 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 »