Author |
Topic: Coin Flip Game Worth (solution?) (Read 22591 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 <stdio.h>
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 <stdio.h>
#include <stdlib.h>
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 |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print