The coin is 90% to be weighted 49% heads and 10% to be weighted 51% heads. You bet $1 on heads each flip. After x flips you either give up or commit to one million total flips (1,000,000 - x more from this point).

You must announce now, what x is, and what criteria you need to continue. For example you might say that you will go on to a million total flips if you have gotten 7100 or more heads out of your first 14000 flips.

To give you the highest total EV (including your expected loss of your preliminary flips) what is the best decision point and the minimum result at that point you need to go on.

The problem here is that as given the edges are tiny so i suspect any good run one has doesnt particularly convince you have a heads+ coin (as compared to say some (60-40 edge case that quickly reveals itself). So you likely need to go the distance in testing to have a solid probability to have the heads+ coin before you decide to continue. Similarly true for a bad run because the opportunity cost is substantial if you give up too easily.


Just to give you an idea if you used 1000 runs the probability to be ahead even with a 0.49 heads coin is still ~25%, at 10000 runs its ~2% and only at 100k runs it goes down to 10^-10 levels.

Now the idea here is to spend x runs and get a result x1, x-x1 from which to deduce the conditional probability you have a heads+ coin. Then calculate the EV as function of x after settling to a decent criterion how to do it (continue or not). Then maximize for x.

It may even prove true that one can arrive at a decision to continue locked after a particular strong run is made (for example if you tried only 500 runs and you had heads leading 270-230 the chance to do that with a 49% coin is 1.4% but with 51% its 9.7% about 7 times stronger (so for some particular starting profiles that would be telling to continue -maybe not here yet though as we start with 9 to 1 against having a heads+ coin).


At the same time lets also see what is the decision if forced to stop at x runs (no optimization yet) and you have at hand a calculation of the conditional probability to have heads+ coin P(heads+) as function of the run x1,x-x1.

If your coin was a heads+ coin your expectation after N more runs is (consider the p1,1-p1 here p1=51% coin) N*p1-N*(1-p1)=N*(2*p1-1).

If your coin was a heads- coin (because of a false positive test say) the expectation after N runs is

N*(2*p2-1).

So you need in order to want to continue to have a positive expectation to continue when the probability to have a heads+ coin is some P(heads+).

That expectation of such decision would be >0 if ;

P(heads+)*N*(2*p1-1)+(1-P(heads+))*N*(2*p2-1)>0 or p(heads+)>1/2*(1-2*p2)/(p1-p2)


So for p1=0.51 and p2=0.49 continuing has a positive expectation for the next N-x tosses only if p(heads+)>1/2

Notice however that this is in general a coincidence of the symmetry of that particular OP case ie 0.49-0.51 vs 0.51 0.49 we have here. If we had 2 possible coins one 0.49-0.51 the other 0.52-0.48 the above requirement would be significantly different p(heads+)>1/3 only.



What we need now is a calculation at any point in time the run is x1,x-x1 of the conditional probability to have a heads+ coin P(heads+|x1,x-x1 run)

that is the Bayes result;

P(heads+|x1,x-1 run)= P(x1,x-x1 run| heads+ coin to begin)*P(heads+ coin to begin)/(P(x1,x-x1 run| heads+ coin to begin)*P(heads+ coin to begin)+P(x1,x-x1 run| heads- coin to begin)*P(heads- coin to begin))

here in OP we have given as P(heads+ coin to begin)=10% and P(heads- coin to begin)=90%.


also P(x1,x-x1 run| heads+ coin to begin)=x!/x1!/(x-x1)!*p1^x1*(1-p1)^(x-x1)

P(x1,x-x1 run| heads- coin to begin) =x!/x1!/(x-x1)!*p2^x1*(1-p2)^(x-x1)

So the above conditional probability P(heads+|x1,x-x1 run) becomes;


P(heads+|x1,x-x1 run)=A*p1^x1*(1-p1)^(x-x1)/(A*p1^x1*(1-p1)^(x-x1)+B*p2^x1*(1-p2)^(x-x1)) so



P(heads+|x1,x-x1 run) = 1/(1+B/A*(p2/p1)^x1*((1-p2)/(1-p1))^(x-x1))


here A=0.1 and B=0.9 (the starting profile) and p1=0.51, p2=0.49

so the above at any point x1,x-x1 becomes;

P(heads+|x1,x-x1 run)= 1/(1+9*0.9608^x1*1.0408^(x-x1))

For example after a run of 100 that is now 55 45

P(heads+|55,45 run)=0.142 still very small to conclude we should stop and decide to go for it (need it to be over 50%).






So far it seems one can continue if you see a conditional probability to have heads+ coin over 50% at any point and then it also becomes an opportunity loss consideration for the other cases that you have bad runs or not over 50% yet, but shouldn't give up because the probability to recover and prove you had heads+ coin anyway is still nontrivial. (i also wonder if one should consider cases the result hints over 50% chance so far but waiting a bit more to be sure it wasnt a false positive saves you money eventually, so maybe this introduces another conditional probability calculation regarding false positives, especially since the continued test running is not a problem,ie if you are correct you still keep the profits from the testing phase. If that detail was to be altered though things would change. I realize that x is specified in advance, we do not have a running strategy, its a fixed preagreed x, i only argue here while searching for that x if it pays to have it big enough to remove some false positives substantially for the cases the conditional probability is already over 50% and some opportunity loss cases of less than 50% that deserve more testing ie false negatives. One could ask for example what is the probability one gets a clear indicator after x runs that minimizes these issues ie how the false positives and false negatives are phased out with increased x and incorporate that in the EV, in particular the negative aspect of continuing to go with a negative result or the similarly funny case a good results case turns negative down the road due to a sudden bad run sequence killing a good case ie a result of us continuing the testing phase and getting bad luck. I do however think that more runs suppress more the false positives than they do increase the false negatives). A numerical simulation may also provide an answer here as one can use brutal force to try almost anything for 1 mil runs using a computer running for only a day to get almost all strategies studied.


Also one recognizes that for the particular severe bias in OP towards a heads- coin at start one cannot make x too large either because this introduces a substantial cost as the majority of the cases ~90% will lead to aborting anyway with losses already.


It would see than x is less than 20000 though as 99.8% of the heads+ coins lead by then (and selected) and only 0.23% of the heads- do lead (false positives). So a crude strategy like run to 20000 and select to continue only with the P(heads+|run)>1/2 is already leading to decent profits that cant be improved by going say to 30000 because the majority close to 90% are losses anyway and the testing phase itself is a negative process in general and the improved accuracy we gain by prolonging it doesnt recover these losses when we are already confident enough at some x smaller than 20000 it seems.

A normal approximation is likely to be used also in the solutions as we need the testing phase to be in the thousands already likely, due to the substantial negative starting bias that we need to suppress to avoid the effect of false positives.

To be continued (pending any missed corrections).

To make sure that everyone gets what I am asking lets say that the player announces that after 10,000 flips he will continue if he gets 5100 heads or more.

At that point he will be down an average of $160, since there was a 90% chance the 2% edge was against him.

The chances he will continue after 10,000 is about 5.003%. Five percent comes from the fact that its even money the heady coin will give him that result and .003% from the fact that the taily coin would need a result outside four standard deviations (50, the square root of 2500) to give the false continuation signal.

If he does continue with the heady coin he will win 2% of 990,000 or $19,800 5% of the time. This gives him an EV of $990. He will lose $1980 .003% of the time so subtract a half a dollar or so.

Since it cost him $160 to get to that decision point, this strategy gives him an EV of about $830. But there are clearly better ones. For instance in the case where he stops to decide at 10,000 he does better if he makes 5050 the criteria. Now he has a 8.4% to win $1980 and a .14% chance to lose it.

Programming a computer to get the best number should be easy for you computer whizzes.

Just to be a bit more confident let me raise the x to 25000 and claim that the optimum is some number lower than that.

The objective of any lower x is to cut down on the losses that the testing introduces for ~90% of the cases anyway due to starting profile.

A significant source of problem is the fact that due to starting bias the false positives are enhanced and prove a terrible loss when continued to 1 mil. So we need to cut these down to the level that the remaining ones are not particularly potent source of loss anymore but not go as far as introduce unnecessary losses on the testing process to achieve that.


As an example if we got to 25000 and had there only 0.077% false positives its no problem anymore. By the way if at 25000 we had some result like 12600 vs 12400
then using the equation from earlier post we obtain;

p(heads+|12600 vs 12400)=99.7%
at the 12501 threshold of winning it gives;

p(heads+|12501 vs 12499)=10.7%

the 50% level is at about 12528

The chance a 0.49 coin gets to 12528/25000 and higher is only 0.02% but we have 9 times more such coins to begin with. It is also a very small chance the 0.51 does so badly hence the P(heads+|such run)> Pcritical (here 0.5) criterion.


In my opinion killing the false positives is very important and the extra cost to do that from say 10kto 25k is not that bad.

Lets say we had x at 10000 say. At this point the criterion to accept a run forward means we need at least 5028 heads. The chance a 0.49 coin will register 5028 or better is 0.54%. The chance a 0.51 coin will register worse than 5028 is 7.6%. Now those are depressing numbers actually.

Such strategy as 5028 or higher to continue would mean on avg ;

For the first 10000 loss of 160 to reach a decision point. Then at this point he continues with a population that is 0.54%*0.9+92.4%*0.1=9.73% of the original population and which is made of 5% 0.49 coins and 95% 0.51 for a net result -19800 for each 0.49 coin and +19800 for each 0.51. The total is 9.2435% 19800 and 0.4865% -19800 or 1733.8.

So the process yields 1734-160=1574.

But now imagine if he tried 15000. Then the threshold to continue becomes >=7528/15000. Now the chance a 0.51 coin will pass that test is a respectable 97.72869%. The chance a 0.49 coin will pass the test is just 0.18726%.

The test to 15000 costs 240. The other 985000 runs when will happen give for 0.51 coins a profit of 19700 and for 0.49 ones a loss of 19700. So a population of 0.9772869*0.1+0.9*0.0018726=9.9414% will continue. That is made of 98.3% 0.51 and 1.7% 0.49 coins. The net EV becomes

-240+0.09772869*19700-0.00168534*19700=1652


So it proves better to try a 15000 level.

If one tries the same with say 25000 you see a decline that proves worse than the 10000 level.

So the maximum looks to be somewhere in 10000 to 25000 range and maybe near 15000.

(if i normalize the calculation, to not be long sums of binomial terms, to be able to do fast enough i may run a brutal force search for the real maximum or someone else can do it)

16000 level gives 1649.6

15500 level gives 1651.3

14700 level gives 1652 also.

Which implies little interest in finding the exact answer as the maximum is not particularly far away from 15000 (probably between 14700 and 15300 and and its only $0.2 away from $1652 if at all.

The only thing left now is to rethink if we missed something in the approach (or if i made some symbolic error anywhere).

What i do is have a run to around 15000 and select all coins that pass the test of 7528/15000 or more because for all these the conditional probability to be 0.51 coins is over 50% justifying the risk of the remaining 985000 runs for the symmetric case of 0.51-0.49 (different condition than 0.5 though arises if it were say 0.52, 0.49). So its a balancing act between the cost of the testing duration vs the removal of false positives and the reduction of false negatives. We can have a nearly perfect screening result around 20000 and higher but the cost to get up there is reducing the overall gain.

So how far from perfection was my instantaneous guesstimate 0f 7,100 out of 14,000?

14000 seems pretty close to the maximum but the threshold needs to be at 7028.

The expected avg for 0.51 is 7140. However many of the good ones will be naturally unlucky by 1-2 sd easily and we must not give up on those and the 0.49 ones at avg 6860 need also to get real lucky to reach 7028+. The sd is around 59=(14000*0.49*0.51)^(1/2) so they need to rally near 3sd to get there. However the 0.51 need only drop 1.9sd . Now what happens at this level is that a coin that finishes at ~7028 has about 50% chance to be a 0.49 or a 0.51 but given that they started at 9 to 1 this is a great improvement for the filtering of 0.51s.

Now any time we know a coin is over 50% chance to be 0.51 we can go for the long run at this set up of 0.51 vs 0.49 (it would be at only 33.3% if it were 0.52 vs 0.49 at same 1:9 starting bias, so the 50% here is specific to the choice of edges). Of course the vast majority of coins that are 0.51 will clear it easily. For example at 7100 with expected 7140 the chance the coin is 0.51 moreover the 9 to 1 start is an impressive 99.7%. So it would be a waste to put the threshold so high. At 7050 for example its also high at 86%. We go down to 7028 to avoid giving up on all those that are like 60%, 70% etc which are still good bargains. At 7028 its ~indifferent.

The funny thing is that due to the equation this came from (unless i made an error) any large threshold at N runs for this particular start up appears to be N/2+28 for large enough N. (some cancellations happen in the conditional probability that lead to this that eliminate N).

For any result x1,x-x1 there is a probability it came if it was 0.51 and another if it was 0.49 which are functions of x1,x. We dont really care what these probabilities are ie how small or big (for each x1 they are tiny anyway even when close to the avg), we only care of the relative fraction of 0.51s in it ie the Bayes conditional probability of a run x1,x-x1 to correspond to a 0.51 coin must be over 50%.

For example if a rather unreasonably lucky run came at the first 100 like 78/100 the chance we have a 0.51 is already over 50% and we could decide for it right there. Now both 0.51 and 0.49 coins need to get real lucky to get to such levels so early but the difference suppresses enough the 0.49 that it reduces the initial 9 to 1 bias down to 1-1. For comparison a 10-0 run, however lucky, is only taking the probability to have 0.51 at 14%. It hasnt suppressed yet enough the 0.49s, that can also get lucky that early (once in 1253 runs vs once in 840).

Same is true on the other side if some bad run happens for the 0.51s, it will get there rarely eg at 7028 out of 7140 expected. But its a lot harder for 0.49 to get up there so the 9 to 1 becomes 1 to 1 at this level.

The equations and conditions for all this were given at the first post and unless i missed something they should be correct. Intuitively it also makes sense that to eliminate the 9 to 1 you need to go down ~2sd for the 0.51 and up 3sd for the 0.49 which is kind of plausible to expect as the balancing breakeven level (well for 14000). Any level higher is only going to further improve the 0.51 and suppress more the 0.49.

The optimal strategy is to flip 14,852 times, and continue if you have 7,454 or more heads. That will give you an EV of $1652.10.

If you did 14,000 and 7,100, you would only have an EV of $1260.94. The optimal threshold for 14,000 flips is 7028 which would give an EV of $1650.51, better than 99% of optimal.

The formula for the ev is

ev = (.1*ph - .9*pt)*.02*(1000000-flip) - 0.016*flip

with

ph = 1-pbinom(thresh-1,flip,.51)
pt = 1-pbinom(thresh-1,flip,.49)

where

pbinom(k,n,p) is the cumulative binomial distribution for no more than k heads out of n flips with probability p.

To get the optimal strategy, I checked every strategy where we had had more than 50% heads all the way to 50,000 flips, and then went every 1000 after that up to a million, though that was hardly necessary. The R script below performs the brute force search, or as masque calls it, "brutal force" lol. You can put in different values for the parameters at the top.

Output:

> flips[[k]]
[1] 14852
> ev.thresh[2,k]
[1] 7454
> ev.max
[1] 1652.098

I modified the script so you could put in different values for the parameters at the top, but editing time ran out before I could finish, so there were still some lines with hardcoded constants. Here's a new one.

Output:

> flips[[k]]
[1] 14852
> ev.thresh[2,k]
[1] 7454
> ev.max
[1] 1652.098

Yes i call it brutal because it is after all brutal lol, like check everything because you can, much like kill everyone because you can, instead of finding the guilty lol (drones anyone?).

That thing became obvious by various samples it was very flat around 1652 for a great number of runs from 14700 to 15300 or so and it quickly lost intrigue because all the contributing terms quickly become unimportant in terms of improvement going towards 20000 , then over 25000 they are near their limits so it felt as if it was a single local maximum kind of thing rather than some elaborate interesting pattern. The cost to run it all starts overcoming the benefits after ~15000 although most statistics improve a lot better over 20000 (so 15k is a compromise between not getting the results at clean as say >99.9% heads+ but getting them decent enough ~98% heads+ to balance the cost of going further).

(I didnt check if excel was fast enough to go with it, got lazy, maybe its the faster way to do it)

A lot of this like say the decision point is also singular to our selection of symmetric probabilities 0.51 to.49. Other cases are not as static in the transition point (i mean here its like always N/2+28).



Now how do we approach a case that we dont know the original details like the probabilities or the population mix at start becomes the next project. We now need a several stages process of testing (which sometimes wont be particularly clear if the number choices are very tough eg some terrible 0.5001 vs .0.4999. Of course for any of this to have value we need some reasonable/somewhat understood starting distributions.

This all could have applications too in some areas it seems.

With the drones, the probability that we won't find them guilty combined with the cost of putting them on trial and the cost of releasing people who are probably still guilty is outweighed by the fact that we know they are guilty and it doesn't cost much if we're wrong. Of course we do blow up some associates who are not guilty, but they aren't exactly innocent either if they are associates. They should have picked better colleagues, friends, husbands, fathers, etc.

The drones aren't brute force though, they are very surgical. Brute force would be to carpet bomb the whole place.

Yes more or less agree with the terrorists and their companies and all the losers there (by association, although some kids clearly are innocent) for the most part but its one thing to think this way and another to tell them you dont care in their face and lose respect worldwide all while it is these losers that are the barbarians, a message easily lost this way.

I think with all these drone style attacks its more like lets get done with it approach rather than some more ethical lets try to be cleaner because we can if we put little effort (kill ratio 10 to 1? could become better with some effort that will cost less in outrage) . The entire terrorism wars then drones thing for me is a loss project if you think about it. We spend so much resources playing a completely asymmetric game exactly like they want us to do.

Sometimes i have to stop and ask myself if the brutal chop head "losers" in the desert are actually brainiacs beyond field medals level.

Think about it. They spend a few millions in order for us to spend trillions over a decade and develop the type of technology (early example past decades rpg weapons ) they then will steal or tamper with to deliver worse terrorist attacks on us (can you imagine a rogue or hacked drone out in our skies?). We are playing a losing game instead of focusing on what really eliminates terrorism and what improves quality of life of all citizens. Pure insanity of priorities. Instead of spending 10 bil $ to create 2 mega towers to replace the old ones in the most provocative in their face demonstration of we prevail forever you losers, you cant touch us, here is your new targets, we go ahead and basically cripple the economy with expensive campaigns on the trillions level that do little and deliver them the technology to do worse eventually all while we continue to be hated worldwide. China Russia, terrorists all super happy about it. So who is the winner? Money culture and corruption and stupid theocracies and totalitarian systems but definitely not US or democracy or freedom or peace. At the same time the prolonged crisis keeps oil prices high and secures more profits to islamic hands (and Russian too) worldwide. The entire thing looks like the ultimate US defeat plan. And it has long ago started to pi$$ me off the way we fall for it!

Obama needs the drones to balance the rest of his foreign strategy which consists mainly of telegraphing weakness and kowtowing to dictators. While you don't like to lose the respect of your friends, you definitely don't want to lose the respect of your enemies.

You also ignore the peaceful technological benefits that come from developing drones and guidance systems capable of sending a missile thousands of miles through Abdul's front door without so much as scraping the paint on the trim. Anyone can build a bomb, but no one delivers them like we do. We do these things not because they are easy, but because they are hard.

Here are some charts for fun (turns out excel was fast to do and find the max with simple 3000 steps columns) ( i was using mathematica for most calculations and was lazy to try excel but since Bruce did the brute force thing here is a visual of it and a confirmation also of the max as 1652.098077 at 14852 and pass test at 7454 or higher)






also a wider range idea;

Care to guess the EV now (and the strategy obviously) of a free to stop at any point strategy? What needs to be the initial bias to make it a fair game?

That's like the question he asked before where you find all the stopping points working it backwards from a million.

Did we do a recursive decision coin thing before? Did we get a closed from or approximation result? I thought i remembered something vaguely from the past when i saw this thread a few days ago (something felt familiar, Déjà vu kind of thing lol). We need to do a collection of problems solved before reference thread link type of thing or something like that with threads that required some work and results that may not be widely available in books etc and are mathematically interesting puzzles or interesting techniques...

http://forumserver.twoplustwo.com/47...ht-up-1335681/


And here's the plot for the problem ITT going the other direction for EV vs. Threshold at 14000 flips so you can see how fast the EV drops off if you get the threshold wrong. Of course it will look similar at the optimal 14852 flips.

I see we didnt do any approximation work on that other thread given we have a large N case here. So lets treat it as somewhat open problem.

I think its kind of impressive that Sklansky guessed 7100,14000 and the answer was 7454,14852.

If you wanted to release yourself from the affinity/discipline to think about these problems in a more systematic/organized way with focus on delivering the proper math that takes you to the answer with conviction, and tried instead a more back of envelope economic way of thinking you could observe these things;

The sd of N trials is (N*0.49*0.51)^(1/2) ie 0.5*N^(1/2). The difference in averages of the 2 coins is 0.02*N. If you recognize that you need to have near the maximum arrived at some substantial type of conviction that you have a heads+ coins in general this implies the chance to miss a good coin needs to be comparable with the chance to accept a bad coin and that much less than 5-10% anyway. But since you start with 9 times more bad coins you are looking at some kind of 2sd by 3sd fluctuation (+3sd for the bad coins and -2sd for the good ones) or maybe 1.7 to 2.6 (say a 5% good coins miss and 0.5% *9 bad coins gained level hence why i go to a bit over 2sd/3sd type thing say with more confidence) (the cdf and 1-cdf of these need to be like 9 to 1 in ratio). So typically you are looking at a situation that the difference of the 2 averages is enough to leave room for something like 4-5sd. Why 4-5 again? well because you need to be losing say less than 5% of the good coins so near 1.5-2sd level and the bad ones that go up there need to also be 9 times smaller (since they are 9 times more numerous at start) so like 2.5-3sd type thing. This is why it feels like 4-5 sd type thing difference will do it (unlucky good ones plus lucky bad ones). (see next why you need less than 5% but not much over 1% error by estimating how much profit each 1% close to 100%clean coins gives you).

So if you set 5sd=0.02*N (the difference in EV equal to 5 sd) you obtain;

5^2*N*0.49*0.51=0.02^2*N^2 or N~15600.

It seems you dont really need to go far above 5sd difference because the gain in profit from say 1% of more positive coins gained is only order 0.01*0.1*10^6*0.02~20. Now the cost of testing is about 0.02*0.8*1000=16 per 1 k runs. So its not worth it to go even up 1-2k over the level you are like ~99% good coins. And that seems to be the ~2.3sd+3.1sd difference level ~18000. So you know the max is less than 18k for sure anyway.


So i guess without any detailed math its about 15600 say with some threshold at typically ~0.51*N-2*sd.