wu :: forums
« wu :: forums - Coin Flip Game Worth (solution?) »

Welcome, Guest. Please Login or Register.
Mar 28th, 2024, 6:55pm

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   hard
(Moderators: Icarus, Eigenray, SMQ, Grimbal, towr, william wu, ThudnBlunder)
   Coin Flip Game Worth (solution?)
« Previous topic | Next topic »
Pages: 1 2 3 4  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Coin Flip Game Worth (solution?)  (Read 22577 times)
Eric Yeh
Senior Riddler
****





   
Email

Gender: male
Posts: 318
Re: Coin Flip Game Worth (solution?)  
« Reply #50 on: Aug 9th, 2002, 5:27am »
Quote Quote Modify Modify

Ollie,
 
OK, now I understand what you are saying.  I definitely completely agree w what you are saying about not knowing if the "H/n > W" strategy is correct, and in fact I have not employed this kind of a strategy in my work thus far at all.
 
However, I do not agree with your proof that it is definitely not of the form f(H/n), unless I am misunderstanding it.  My original reply to your msg still holds:  The payoff structure changes after your first constant number of flips, so "starting a new game" then is just not the same thing.  You can also see it by my second example in the same thread, which forces a stop under .5 which you should never do.
 
That said, I do think it would be good to figure out whether the f(H/n) strategy works.
 
Best,
Eric
IP Logged

"It is better to have puzzled and failed than never to have puzzled at all."
AlexH
Full Member
***





   
Email

Posts: 156
Re: Coin Flip Game Worth (solution?)  
« Reply #51 on: Aug 9th, 2002, 9:52pm »
Quote Quote Modify Modify

The optimal stopping decision can't be a threshold for H/n (at least not one > .5 ) for exactly the same reason Bob wins in that Alice and Bob counter game. You fixing the threshold is just like Alice picking the coin bias. For any line sloping away from the mean like there is a finite chance that the sampling will never cross that line. In other words that strategy does not terminate with p=1 and therefore you can beat it with (for example) a strategy which does mostly the same things but accepts less once it reaches an n,H situation where non-termination becomes sufficiently likely.
« Last Edit: Aug 9th, 2002, 9:53pm by AlexH » IP Logged
Eric Yeh
Senior Riddler
****





   
Email

Gender: male
Posts: 318
Re: Coin Flip Game Worth (solution?)  
« Reply #52 on: Aug 10th, 2002, 11:14am »
Quote Quote Modify Modify

Alex,
 
That is a good point -- clearly at a sufficiently high n you stop arbitrarily close to .5, for example.  However, I realize I didn't express my question well.  I meant to ask, if you stop at H/n, do you stop at every H/m where m>n.  I assume this is true, but haven't had more than a couple of minutes to think about it.
 
Best,
Eric
IP Logged

"It is better to have puzzled and failed than never to have puzzled at all."
AlexH
Full Member
***





   
Email

Posts: 156
Re: Coin Flip Game Worth (solution?)  
« Reply #53 on: Aug 10th, 2002, 12:25pm »
Quote Quote Modify Modify

Sorry to be difficult but I'm not sure I understand the question you are asking now.  
 
Did you mean m<n instead of m>n? If so then as I understand it your question is "If the best strategy stops at some number of flips n with number of heads H, can we be sure that it stops at or before H heads on all smaller numbers of flips m<n". We could ask the same question with ratio of heads (i.e. payoff) substituted for actual number of heads. Is this what you're asking?
IP Logged
tim
Junior Member
**





   


Posts: 81
Re: Coin Flip Game Worth (solution?)  
« Reply #54 on: Aug 10th, 2002, 6:50pm »
Quote Quote Modify Modify

It is not hard to prove that if you are willing to stop at H heads after N flips, you should accept H heads for any number of flips <= N.
 
Let f(H,T) = 1 mean that you will continue flipping when you have H heads and T tails. f(H,T) = 0 means you stop. Let v(H,T) be the average payoff from continuing. For any optimal strategy, f(H,T) = 0 iff v(H,T) <= H/(H+T).
 
Now, a simple induction argument shows that for any optimal strategy, f(H,T+1) = 0 implies f(H+1,T) = 0 (in particular, there cannot be a smallest T for which f(H,T+1) = 0 and f(H+1,T) = 1).  We already know that the optimal strategy has f(H,T) = 1 for all H <= T, so we need consider only H > T.
 
Now suppose that f(H,T+1) = 0. Then f(H+1,T) = 0, and hence
v(H,T) = 0.5 H / (H+T+1) + 0.5(H+1) / (H+T+1)
 = (H+0.5) / (H+T+1)
 = (2H+1) / 2(H+T+1)
 = (2H+1)(H+T) / 2(H+T+1)(H+T)
 = (2H^2+H+2HT+T) / 2(H+T+1)(H+T)
 < (2H^2+H+2HT+H) / 2(H+T+1)(H+T)  since H > T,
 = 2H(H+T+1) / 2(H+T+1)(H+T)
 = H / (H+T).
Any optimal strategy has f(H,T) = 0 when v(H,T) <= H/(H+T), so f(H,T) = 0.
 
Thus if you accept H heads in N flips for some N, you should accept H heads in N-1 flips. Continuing by induction, you should accept H heads in any number of flips M where M <= N.
 
In general, f(H,T) = 0 implies f(h,t) = 0 for all h >= H and t <= T.
 
I'm still trying to find stronger relations.
IP Logged
Eric Yeh
Senior Riddler
****





   
Email

Gender: male
Posts: 318
Re: Coin Flip Game Worth (solution?)  
« Reply #55 on: Aug 10th, 2002, 7:41pm »
Quote Quote Modify Modify

Alex, Tim,
 
Sorry guys, that one was a victim of typing too fast.  Tongue  I agree that what I wrote makes no sense without Alex's change, and also that it is then pretty clear as Tim suggested.
 
What I meant to write was this:  if you stop at H/n = x, do you also stop at every H'/m = x where m>n?  I.e. if you stop at 4/5 do you also stop at 8/10, 44/55 etc.  I think it should be fairly straightforward since the "stopping value" has to go to .5 as n -> infinity, but I haven't really worked out any of the details yet.  I guess maybe more interesting would be to show that the stopping value is monotonically decreasing, which seems the intuitive thing.
 
Best,
Eric
« Last Edit: Aug 10th, 2002, 7:43pm by Eric Yeh » 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 #56 on: Aug 10th, 2002, 10:45pm »
Quote Quote Modify Modify

No, the stopping value does not monotonically decrease. That's what's making it so hard Undecided
 
If it did, then anywhere after a value of 2/3, f(H,T) = 0 would imply f(H+1,T+1) = 0. I've already tested that class of strategies; the best one has a value of about $0.7904.
 
So far, I've got a strategy asymptotically based on H > T+sqrt(T) that manages to get $0.79292+.
 
It seems that my suspicion that the value of the game might be sqrt(pi/5) didn't work. Sad
IP Logged
Eric Yeh
Senior Riddler
****





   
Email

Gender: male
Posts: 318
Re: Coin Flip Game Worth (solution?)  
« Reply #57 on: Aug 10th, 2002, 11:01pm »
Quote Quote Modify Modify

Tim,
 
How did you test that entire class of strategies conclusively?  There are arbitrarily many monotonically decreasing fns...  I don't believe there's a clear way to see the optimal strategy in that subset.
 
Plus, why after 2/3?  No matter what, f(H,T) = 0 would imply f(H+1,T+1) = 0.  Plus, you would never get there anyway.  Plus, you don't stop at 2/3!  Hm, I'm afraid I don't understand much of your post at all!  Apologies if I am just missing the key; it's a bit late.
 
I haven't worked seriously on this problem since long before giving it to Will, but from what I remember of my work from before, I think got some strategies that pay around 81 cents.  I could be misremembering it though.
 
Best,
Eric
« Last Edit: Aug 10th, 2002, 11:03pm by Eric Yeh » 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 #58 on: Aug 11th, 2002, 3:49am »
Quote Quote Modify Modify

Eric: Not quoted in order
Quote:
No matter what, f(H,T) = 0 would imply f(H+1,T+1) = 0

We know that f(1,0)=0: you definitely stop when your first flip is a head!
If f(H,T)=0 generally implied f(H+1,T+1)=0, then f(2,1)=0. That is, we should stop at 2 heads and 1 tail, which we know isn't a good idea.
 
Quote:
Plus, you don't stop at 2/3

Not at 2 heads out of 3 flips, no. But if your sequence of stopping values is monotonically decreasing toward 1/2, then at some stage it must below 2/3. Thus there will be a pair (H,T) such that f(H,T)=0 with value H/(H+T) < 2/3. That is, H < 2T.
 
Quote:
Plus, you would never get there anyway.

Consider what happens if you are currently at (H-1,T+1). If you get a head, you move to (H,T+1). That isn't a stopping point; it has too many tails. You flip again, getting another head. You've reached (H+1,T+1). Is that a stopping point or not?
 
Suppose it is not. Then you could flip again to get (H+2,T+1), with a value of:
  (H+2) / (H+T+3)
= (H+2)(H+T) / (H+T+3)(H+T)
= (H^2+2H+HT+2T) / (H+T+3)(H+T)
> (H^2+HT+3H) / (H+T+3)(H+T)  since H < 2T
= H(H+T+3) / (H+T+3)(H+T)
= H/(H+T).
In other words, the value of (H+2,T+1) is greater than that of (H,T), violating monotonicity.
Hence under the monotonicity assumption, our supposition must be incorrect, and (H+1,T+1) is a stopping point whenever (H,T) is, for H<2T.
 
Now, we already know that we cannot continue H >= 2T indefinitely, or we get a nonzero chance of never stopping. Hence there is a smallest T such that f(H,T)=0 for H < 2T.
 
Quote:
How did you test that entire class of strategies conclusively?

For any such T, the strategy is completely determined by a finite number of stopping points before settling into one extra head for each tail in the rest. For any given T value, a catalan sequence can be constructed to evaluate the expected payoff of the infinite portion of the sequence. It turns out that for T>8, the expected payoff decreases rapidly. A simple exhaustive search then suffices for finding all stopping points (h,t) for t<=8. The best one has value bounded above by $0.791, and actually evaluates to $0.79044.
 
Quote:
I think got some strategies that pay around 81 cents.  I could be misremembering it though.

I hope not! I'd love to see some better strategies. I'm starting to get stuck in a rut here Sad
IP Logged
Eric Yeh
Senior Riddler
****





   
Email

Gender: male
Posts: 318
Re: Coin Flip Game Worth (solution?)  
« Reply #59 on: Aug 11th, 2002, 10:09am »
Quote Quote Modify Modify

Tim,
 
Spent so much time responding to you in "The Gods of Gibberland" that I don't have time to write much here.  Smiley
 
Woops, I think most of our misunderstandings have just been syntactic miscommunications (prob my fault (tho I'm too lazy to reread everything to see); sorry).
 
First, I thought f(H,T) was f(Heads,Total), but I see now you mean T=Tails.  The reason for this was probably:
 
Second, when I write 2/3 in the context of this problem I actually mean literally two heads, three tails, not any value 2/3.  Otherwise I write 4/6 etc.  This is why I also thought your "f(x,y)" was my  "x/y".
 
Apologies for the confusion.  Many of the things I disagreed with last post I agree are fairly obvious after the clear-up; the couple of things that are not I will think about later.  (One thing was the finite values in your conclusive test -- is that also bc of the syntax or am I just missing the reasoning?  It seems to me that there should be arbitrarily many as a function of T=Total.)
 
Ok, gotta jet.
 
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 #60 on: Aug 12th, 2002, 12:36am »
Quote Quote Modify Modify

Hi Guys, still at work.
 
I'm short on time ATM, but I saw one thing:
Quote:
In other words that strategy does not terminate with p=1 and therefore you can beat it with (for example) a strategy which does mostly the same things but accepts less once it reaches an n,H situation where non-termination becomes sufficiently likely.  

 
AlexH, IMO that is a tough one. It's certainly not written in the riddle that a strategy has to terminate.
Maybe the payoff converges against a value > 0. (HTHTHTHTHTHT... as an example). Now we have the possiblity to define the "payoff" just as the value of this limit.
Moreso, it feels like if you want the strategy to terminate in any case, you have to "artificially" impose something that this happens. Take the above sequence with H and T always alternating, when do we stop?
To sum up, I think there is the uncertainty of how to define the value of non-terminiating flip sequences, either as the limit, or as zero. This decision will certainly impact the value of the game.
IP Logged
AlexH
Full Member
***





   
Email

Posts: 156
Re: Coin Flip Game Worth (solution?)  
« Reply #61 on: Aug 12th, 2002, 1:27am »
Quote Quote Modify Modify

A strategy can terminate wtih probability 1 and still have lots of sequences (such as THTHTHTHTHTHTHTH....) that never terminate. The problem with having some fixed ratio of H/T required would not be that some sequences never terminate, but that a non-zero measure of sequences would. Since you take your money only after the game concludes its outside the scope of the question to define some non-zero payoff for non-terminating sequences. This shouldn't really be a barrier to any of the kinds of strtategies I can think of.
IP Logged
Paul Hsieh
Guest

Email

Re: Coin Flip Game Worth (solution?)  
« Reply #62 on: Aug 12th, 2002, 3:56pm »
Quote Quote Modify Modify Remove Remove

If you don't have any termination condition, then you can simply follow the rule:
 
    Wait until #H > 0.99999 * #T.
 
This is a legitimate strategy, but its probability of termination is actually quite low.  In my thinking I have basically said, that I have a strategy for up to the first n flips, Sn, and that for any sequence that has not terminated as desired after n flips, simply perform K*n additional flips (where K is very large, like a million) and just take the the result you get.  This will result in an expected outcome of (0.5 - epsilon) for any arbitrarilty small epsilon.
 
These (0.5-epsilon)'s have impact on the computed output and, of course, cannot be ignored in order to ensure that you have a well defined terminating algorithm.
 
So, by simply letting K and n go off to infinity in a well defined way, you can converge on an outcome, which each instance having a finite predetermined termination upper bound.  The final result computed, say V, will then technically be an upper bound for the real realizable outcome.  I.e., its really (V-epsilon) for any chosen epsilon > 0.
 
Hmmm ... it has suddenly occurred to me, that in fact you can perform a slight optimization.  Since I have seen that in fact that the rule should be (stop flipping if #H > A * #T), for A ~= 5/4, in fact if after n flips we find that #H > #T >= #H / A, then we should terminate without any additional flips.  This would probably represent a very small improvement.
IP Logged
AlexH
Full Member
***





   
Email

Posts: 156
Re: Coin Flip Game Worth (solution?)  
« Reply #63 on: Aug 12th, 2002, 7:11pm »
Quote Quote Modify Modify

At any point you can switch to the strategy "stop once payoff is > .5" and you will terminate with probability 1, so the "continuation value" of any position is >= .5 without worrying about payoff of non-terminating sequences. I think its fine to have an optimal algorithm which has no upper bound on sequence lengths as long as chance of termination goes to 1 as t-> infinity.  
 
I've been spending too much time on 100 prisoners.
IP Logged
tim
Junior Member
**





   


Posts: 81
Re: Coin Flip Game Worth (solution?)  
« Reply #64 on: Aug 12th, 2002, 10:36pm »
Quote Quote Modify Modify

Let H(T) be the least number of heads you need before you will accept T tails. For example, we know that H(0)=1 since you should always stop at 1 head if you haven't got any tails yet.
 
All of my highest-value strategies so far have been of the form
 
H(T) = T+1 + floor(sqrt(T) + r(T)), where
r(T1) >= r(T0)  for T1 > T0, and
0 <= r(T) < 1  for all T.
 
All such strategies terminate with probability 1. One such strategy achieves an average payoff of a bit more than $0.79292.
 
Can anyone find a strategy with better average payoff that does not fit this model, or prove that the optimal strategy must be of this form? I've had no luck yet with either side of the question.
IP Logged
Kozo Morimoto
Guest

Email

Re: Coin Flip Game Worth (solution?)  
« Reply #65 on: Aug 13th, 2002, 9:37pm »
Quote Quote Modify Modify Remove Remove

I posted this riddle to another, more technical forum and this is the result:
http://www.wilmott.com/310/today_detail.cfm?articleID=137
 
So according to this, 0.79295 seems to be answer as a limit of number of flips approach infinity.
 
However, at infinity, its a whole different ball game and there is a huge thread on the nature of infinity how this affects the answer to this riddle.
IP Logged
tim
Junior Member
**





   


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

Kozo: Good lord, what a monster thread! I read 7 pages of discussion, and there were still some participants unconvinced that the value of the game was less than 1!
 
I noticed that some of them are as interested in finding the Chow&Robbins paper as I am Smiley
IP Logged
AlexH
Full Member
***





   
Email

Posts: 156
Re: Coin Flip Game Worth (solution?)  
« Reply #67 on: Aug 14th, 2002, 4:25am »
Quote Quote Modify Modify

A 100,000 flip optimal strategy with a fallback to quit when x>=.5 wins yields .79294.  
 
Edited :  
 
Assuming my program is correct, we do see higher thresholds than the 1+T+sqrt(T) formula. For example, the 10^5 flips scheme above has stopping criterion H-T =50 at T = 1686 where the formula says we should require at most H-T> 43 at that point. The approximation of the optimal scheme by this bounded flip method is pessimistic in the sense that it will stop too early because it underestimates the continuation value.  This means the stopping criteria given by the approximation are lower bounds on the true optimal criteria.
« Last Edit: Aug 14th, 2002, 5:23am by AlexH » IP Logged
Eric Yeh
Senior Riddler
****





   
Email

Gender: male
Posts: 318
Re: Coin Flip Game Worth (solution?)  
« Reply #68 on: Aug 14th, 2002, 6:09am »
Quote Quote Modify Modify

I agree with Alex -- I dug out my old results and show the same value @ 100,000.
IP Logged

"It is better to have puzzled and failed than never to have puzzled at all."
AlexH
Full Member
***





   
Email

Posts: 156
Re: Coin Flip Game Worth (solution?)  
« Reply #69 on: Aug 14th, 2002, 3:01pm »
Quote Quote Modify Modify

Interestingly even the early thresholds keep rising as you up n. On a 2E6 flip game I get payoff .792952, but the interesting thing is that the stopping criteria rise even early on when you lengthen the game. The first criteria which changed was surplus of 15. You don't require a surplus of 15 heads until 122 tails in the 1E5 flips, while you require it at 121 tails with 2E6 flips. This continues so, for example the 50 surplus I mentioned above happens at 1646 tails instead of 1686 as in 1E5 flips. Maybe I can run a big number overnight later and test say 5E7. I can't think of any way to beat n^1.5 run time though so I can only push it so far.
IP Logged
Eric Yeh
Senior Riddler
****





   
Email

Gender: male
Posts: 318
Re: Coin Flip Game Worth (solution?)  
« Reply #70 on: Aug 14th, 2002, 3:04pm »
Quote Quote Modify Modify

n^1.5 is already impressive -- how do you get it below quadratic?
IP Logged

"It is better to have puzzled and failed than never to have puzzled at all."
AlexH
Full Member
***





   
Email

Posts: 156
Re: Coin Flip Game Worth (solution?)  
« Reply #71 on: Aug 14th, 2002, 4:56pm »
Quote Quote Modify Modify

I'll post the code once I get the chance to do some last tweaks. Kind of busy today though so probably not tonight.  
 
Here is the crux of how we trim our problem so that we can do n^1.5. We're working backwards from the boundary at n flips, computing the i-1 flip data from the ith flip data. We only wind up doing computations for an O(sqrt(n)) neighborhood of the 50/50 line. On the high side, once we detect the surplus needed for stopping for this # of flips we don't have to compute all higher surpluses' values; we can just compute them when needed since we know that they will be the stopping payoff at those points. On the low side we rely on the fact that we're using bounded precision arithmetic. Look at the question "for a certain combination of (surplus,flips) where surplus is negative, whats the chance we break .5 payoff before we hit n flips". For large n we have a normal distribution, with deviation sqrt(n)/2. We use that to bound how far below 50/50 we have to compute. Below that bound we just use .5 for the values. We can pick a constant multiple of deviations thats big enough to force the error generated by this to be below the precision of a double and we still win big in terms of run time for large n. There are few more details/tweaks but those are the big points.  
IP Logged
AlexH
Full Member
***





   
Email

Posts: 156
Re: Coin Flip Game Worth (solution?)  
« Reply #72 on: Aug 14th, 2002, 5:04pm »
Quote Quote Modify Modify

I'll post the code once I get the chance to do some last tweaks. Kind of busy today though so probably not tonight.  
 
Here is the crux of how we trim our problem so that we can do n^1.5. We're working backwards from the boundary at n flips, computing the i-1 flip data from the ith flip data. We only wind up doing computations for an O(sqrt(n)) neighborhood of the 50/50 line. On the high side, once we detect the surplus needed for stopping for this # of flips we don't have to compute all higher surpluses' values; we can just compute them when needed since we know that they will be the stopping payoff at those points. On the low side we rely on the fact that we're using bounded precision arithmetic. Look at the question "for a certain combination of (surplus,flips) where surplus is negative, whats the chance we break .5 payoff before we hit our limit n flips". For large n we have a normal distribution, with deviation sqrt(n)/2. We use that to bound how far below 50/50 we have to compute. Below that bound we just use .5 for the values. We can pick a constant multiple of deviations thats big enough to force the error generated by this to be below the precision of a double and we still win big in terms of run time for large n. There are few more details/tweaks but those are the big points.  
 
IP Logged
tim
Junior Member
**





   


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

Thanks, I'm glad someone managed to do better, even if it did disconfirm my hypothesis.
 
Yes, your evaluation method looks similar to mine. I only took it out to about 10000 flips though, since I needed to do rapid evaluations for a search.
 
I did suspect that continuing further would affect earlier results. What a horrid problem Undecided
IP Logged
AlexH
Full Member
***





   
Email

Posts: 156
Re: Coin Flip Game Worth (solution?)  
« Reply #74 on: Aug 14th, 2002, 10:26pm »
Quote Quote Modify Modify

Its not the prettiest code I've ever written, but hopefully its understandable.
 
On my pokey celeron at home it takes about 45 seconds on a 1E6 problem. Memory may be as much of a problem as time as we grow n since I didn't mess about with trying to code it for sqrt(n) memory. It could be rewritten to do so if I get the time/inclination, but at the moment its linear memory in n. This means a 1E7 problem takes 80MB (and a ballpark of 30 minutes). The 1E7 problem paid off 0.792953042848
 
Also, while I did optimize the algorithm reasonably, there is more that could be done at a low-level coding standpoint. It feels like maybe there should be some way to beat the system and cut down to less than n^1.5 but I don't see it atm. The code is C++ though its 98 percent plain C.
 

#include <stdio.h>
#include <iostream.h>
#include <math.h>
 
#define DEVIATIONS 6.0 // gives error threshold 1E-9 (at mean line error << 1E-18)
 
// cutoffs[i] is lowest # of heads for which we require surplus >= i to stop
int *cutoffs;
 
// we could get down to O(sqrt(flips)) memory but we'll have to be very  
// careful with the indicies. Currently its O(n) space and O(n^1.5) time
double computeFlipValue(int flips,int numberCutoffs){
 int curFlips,curHeads;
 double stopValue, contValue;
 double *values;
 int lowBound, lastUpperBound, deviationBound, surplus;
 
 values = new double[flips+1];  
 
 int flipsOverTwo = flips >> 1;
 
 // k * deviation + extra buffer so that we compute all for small problems
 deviationBound = ceil(sqrt((double) flips) * .5 * DEVIATIONS) + 100;  
 
 
 //Set boundary conditions  
 lastUpperBound = (flips >> 1) + 1;  
 for(curHeads=0;curHeads<lastUpperBound;curHeads++){
  values[curHeads] = .5;
 }
 values[lastUpperBound] = (double) lastUpperBound / (double) flips;
 // all boundary values higher than lastUpperBound get computed in loops as needed
 
 // Compute curFlips flips data from curFlips+1 flips data
 
 for (curFlips=flips-1;curFlips>=0;curFlips--){
  curHeads = (curFlips-flipsOverTwo > 0) ? curFlips-flipsOverTwo : 0; // skip triangle of all .5
 
  //error in cutoffs region < 1E-18 with coeff 6.0
  lowBound = (curFlips >> 1) - deviationBound;
  curHeads = (lowBound > curHeads) ? lowBound : curHeads;
   
  // stopping point can't drop more than 1 head per flip, so don't need to check
  // Most of the running time is spent here. Should optimize.
  for(;curHeads < lastUpperBound-1 ;curHeads++){  
   values[curHeads] =  .5 * (values[curHeads] + values[curHeads+1]);  
  }
   
  // ASSERT: curHeads == lastUpperBound - 1
  for(;curHeads<curFlips;curHeads++){
   stopValue = (double) curHeads/(double) curFlips;
   contValue = .5 * (values[curHeads] + values[curHeads+1]);
   if (stopValue > contValue) {   // true ==> found cutoff
    surplus = (curHeads << 1) - curFlips;    
    if(surplus < numberCutoffs)   // array bounds check should never fail
     cutoffs[surplus] = curHeads; // last overwrite will be on lowest curFlips for given surplus
    values[curHeads] = stopValue;
    lastUpperBound = curHeads;
    break;
   }
   values[curHeads] = contValue;
/*
   We need to set up the correct values[curHeads+2] from the curFlips+1 round  
   so that our next iteration computes contValue properly. We can compute it  
   directly because we know it is past the cutoff from that round.
*/
   values[curHeads+2] = (double) (curHeads+2) / (double) (curFlips+1);
  }
  if (curHeads == curFlips){    // true means we never hit a stop point
   if (curFlips > 0){  
    values[curHeads] = 1.0;
    lastUpperBound = curHeads;
    cutoffs[curHeads] = curHeads;  // curHeads is the surplus since curHeads==curFlips
   }
   else{    // curFlips=curHeads=0  
    values[0] = .5 * (values[0] + values[1]);
   }
  }
 }
 contValue = values[0];
 //delete values;
 return contValue;
}
 
 
void displayCutoffs(int flips,int numberCutoffs){
 
 int i;
 printf("Surplus\t Heads\n");
 
 for(i=1;i<numberCutoffs;i++){
  if (cutoffs[i] == -1){
   printf("Largest cutoff was %d\n",i-1);
   break;
  }
  printf("%d \t %d\n", i, cutoffs[i]);
 }
}
 
int main(){
 char line[80];
 int flips = 1.0E6;
 int numberCutoffs;
 double gameValue;
 int i;
 
 cin >> flips;
 
 numberCutoffs = (int) (ceil(sqrt(0.5 * flips))+1);
 cutoffs = new int[numberCutoffs];    
 for(i=0;i<numberCutoffs;i++){
  cutoffs[i] = -1;
 }
 gameValue=computeFlipValue(flips,numberCutoffs);
 displayCutoffs(flips >> 1,numberCutoffs);
 printf("Value at %d flips = %14.12f\n",flips,gameValue);
// cin >> line;
 return (int) (gameValue * 1.0E8);
}
IP Logged
Pages: 1 2 3 4  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board