Probability puzzle

Here's a sketch of a (possibly bad) upper bound.

We will use the following strategy, parametrized by two constants X and Y. First, we will make the bet X times, guessing randomly each time. If all X coin flips were NOT the same, we stop. If they were, we keep going for Y more flips, each time guessing the same outcome that happened for the first X coin flips.

We lose $X in expectation for the first X flips, no matter what. Our expected winnings on the longer sequence of Y flips, in terms of the unknown probability p, are p^X . (4p - 3) .Y plus a similar term for (1-p). Integrated from 0 to 1, these give 2Y(4/(X+2) - 3/(X+1)), which is positive for X>2, so we just have to choose Y to make this bigger than X.

The total number of flips is X + Y, which is minimized (over the integers) when X = 3 and Y = 30, for a total of 33 coin flips. This just lets us break even, so we bump Y up to 31, for N=34 and an expected profit of ten cents.

Obviously this can be improved -- we should be using our partial information about the coin at each step, instead of making just one decision 3 coin flips in.

Please clarify your setup. I'm almost certain that you don't want to put a uniform distribution over the "heads:tails ratios" covering (0, +∞). Rather you mean a uniform distribution of the heads probability over (0, 1), right?

Assume that all heads:tails ratios are equally likely for the coin.

Presumably there is still a fixed (frequentist) probability of a flip being heads, otherwise your coin either has memory or is a subject to an unknown external interference.

You have to accurately predict at least 75% of flips to come out ahead, there is no way to do that with a fair(ish) coin, so, even if you have a perfect model of the coin you will likely lose if the coin is moderately unfair (25%-75% heads), regardless of N.

Maybe I misunderstand your setup.

...It could come up all heads, all tails, or any value in between....

What is the minimum value of N that lets you come out ahead on average?

I'm pretty sure that in the region of curiously-warped-coin-space near 'fair', you're not going to be able to come out ahead on average.

It's been nearly a couple decades since I studied any probability, but if these problems keep turning up, I might look it up and refresh my memory of it.

Nffhzvat lbh nobeg nsgre gur svefg syvc gung pbzrf hc qvssreragyl sebz gur svefg syvc rire, lbh erpbhc lbhe fhax pbfg bs $1.33 nsgre svsgrra syvcf (hayrff zl zngu vf qenfgvpnyyl naq jrveqyl jebat; vg qbrf frrz vapbafvfgrag jvgu bguref'...) Fvapr bgure oenapurf fubhyq unir cbfvgvir rkcrpgrq inyhr (v.r. avar gnvyf bar urnqf lbh fubhyq cebonoyl xrrc tbvat) vg zvtug or yrff guna gung. Vs lbh xrrc tbvat nal gvzr lbh unir cbfvgvir rkcrpgrq inyhr, lbh fubhyq rkcrpg gb erpbhc pbfgf nsgre whfg gjryir pbva syvcf.

vg nyfb qbrf abg nccrne gung gur hgvyvgl vf obhaqrq nf A->vasvavgl, ohg vg qbrf tebj cerggl fybjyl. Sbe rknzcyr, gb rkcrpg gb znxr gjragl-svir qbyynef, lbh'q unir gb unir A nyzbfg n uhaqerq.

This seems to be a good opportunity to use a trick I figured out for approximating the probability of a binary event (I'm sure I'm not the first to discover it). The trick goes as follow: start with a probability distribution P(x) = 1. For each time the even happens, multiply P(x) by x, and for each time it doesn't, multiply by 1-x. After doing this for your data, renorm it so that the area beneath the curve is 1: you can do that by dividing your function by its integral from 0 to 1. If you have a range of outcomes, you can multiply by the function representing that to get expected utility. In this case, the function representing the outcomes can be modeled by O(x) = 4x - 3. If we assume the coin is biased towards heads (if it's biased towards tails, just substitute H and T in the following reasoning), we find through some math and puzzling that the formula that determines expected value for the sequence of coins is (N-4*T-4)/N+2) where H is the number of heads and T is the number of tails, and N represents the number of tosses. The probability of reaching any state is given by 1/N. For the first two flips, your expected value is negative (-$1 and -$.033 for the first and second respectively) no matter what happens, so we can count these as sunk costs. So our expected value is as follows here:

It took me 19 flips to come up with a positive expected value, though my answer with the original question is "as many as the person offering this can be convinced to give me".

You can definitely break even with N=13, assuming the unrealistic even distribution between 0 and 1, perhaps a bit earlier with a more sophisticated strategy.

Example strategy: Choose randomly the first time, the same side in all further throws. If the other side comes up before the 6th throw stop (6th throw because that's the earliest your expected winnings for the next throw don't increase by stopping if the other side comes up). Otherwise continue to N.

The probability of the same side coming up n times is 2/(n+1), the probability of the other side coming up exactly the n+1th time 2/(n^2 +3n +2).

Expected winnings each throw: 1st: -1$, 2nd: -1/3 $, 3rd: 0$ 4th: 1/10 $, 5th: 2/15 $, 6th-Nth: 1/7 $

Spoiler Alert:

Vg qrcraqf ba lbhe cevbe sbe gur vagryyvtrapr bs lbhe sevraq. Vs ur xabjf jung ur vf qbvat, ur jvyy perngr n jnecrq pbva gung vf fgvyy 50-50 naq lbh jvyy trg lbhe pybpx pyrnarq ertneqyrff bs nyy lbhe snapl Onlrfvna whwvgfh.

N havsbez qvfgevohgvba ba (0,1) vf whfg gur jebat cevbe sbe n thl gung pbzrf hc jvgu n jnecrq pbva naq n cebcbfvgvba sbe n org ba vg. Vg'f nyjnlf orggre gb juvc bhg n yvggyr tbbq frafr orsber lbh juvc bhg lbhe snapl rdhngvbaf.

V'z n yvggyr qvfnccbvagrq gung ab bar frrzf gb unir tbggra guvf lrg. Hfr lbhe urnqf.

V'z pbafvqrevat jurgure gb fuhg zl lnc naq znxr fbzr zbarl ng gur arkg ybpny YJ zrrgvat. ... V'z gbb ynml.