heehaww,

Does my solution offer the most EV possible? I can not do the EV calc. I think it does, however.

If your goal is highest EV, then the highest EV strat was already provided by a few ppl ITT including myself and stinkypete: all-in on whichever side leads on the scoreboard. Other strats were only mentioned because one might prefer to maximize median wealth (or something else) instead of avg wealth. Juk found the strategy which maximizes median wealth and geometric mean growth.

A nice thing about EV is that it's linear, so we can know without calculations that the maxEV strat as a whole is found by maximizing EV on each individual flip. On any individual flip where there's an edge to be had, the max EV is given by shoving all-in.

I don't think your dual universe proposal is different from using a single universe. After the first flip, the posterior distribution will have already chosen one of your universes. Juk's solution appears correct (though I didn't check it). It's the same concept as the Bayes calculation I did in my toy example from a few posts back, except it's on a continuous range so integration is required.

Thank you. I think I will continue with this puzzle, but make it 20k liferoll and use Kelly.

I have only skimmed the thread.

Is it the consensus that if you want to maximize EV, no matter what the prior, due to the fact that EV is a "linear" operator, you bet max on each flip on the side that is more likely (per your current posterior probability)?

That does not seem obvious to me. Isn't there some value in having a bankroll "late" in the game after you are more confident in the coin's bias?

Painting an extreme case in order to make the point, suppose that you believe that the coin is either 90% heads or 90% tails (with equal prior probability). In such a game wouldn't I want to bet very small early on and very big later on? You want to ensure that your bankroll does not go to zero (or small) because you will be able to literally print money later on.

The concept of "value of information" seems (potentially) important here.

Of course, I could very well be wrong!

I did a bit more reading up on this and it turns out you can actually calculate it without any integration (ie: just use the "linearity of expectation" property):
(I thought the formula looked suspiciously similar to the mean of the beta distribution the other day!)

BUT: you do still have to integrate it if you want to model uncertainty in your payouts (see: "Optimal betting under parameter uncertainty: improving the Kelly criterion").

Juk

Yes, but the bet way to be able to bet very large in the later rounds is to have a huge bankroll and the best way to get a huge bankroll is to double up a bunch of times. I think you'll reduce your chances of making it to the end, but the times you DO make it to the end the payoff from being able to bet the max will make up for it. Keep in mind that your total potential loss is $20.

The 90/10 coin is the perfect example of why we should bet big asap.

We know there's a 90% chance that the result of the first flip is a 90% favorite on remaining flips.

If we go all in after the first flip we're risking 20 to win $10240 with a 34.9% chance of scooping.

If we wait another flip we're risking 20 to win $5120 with a 34.9% chance of scooping (if the first two flips are the same) and an 18% chance that we're back to knowing nothing about our coin (first two flips are different) with only 8 flips left. So if we play optimally from there we flip one more time and bet all in on the last 7 flips, and we have a 18%*43%=7.7% chance of getting $2560.

34.9% chance at $10240 (EV $3574) is clearly much, much better than a 34.9% chance at $5120 plus a 7.7% chance at $2560 (EV $1984).

(I did the calculations quickly, it's possible i made a mistake somewhere... but if they're wrong the correct numbers still show a similar result)

It seems you may be assuming (hand-waving) your conclusion. We are trying to find the optimal amount to bet in each possible node on the decision tree.

Could you post your current updated posterior probabilities along the various paths through the tree? Don't your EV's depend upon them?

I'd like to see someone actually demonstrate this before I 100% believe it.

Read with interest the entire thread. Didn't partecipate to the discussion due to lack of time. However, I hopefully find some time to address some of the considerations ITT.

- "We don't know the prior. It's nothing": this is wrong. The prior distribution is meant precisely to quantify your knowledge (or abscence of) regarding something. It's subjective, since differente subjects may have different information and/or different views about something. But it has to be expressed since, in many instances, your strategy depends on it. Some particular cases aside (and this problem might be one of them), you cannot find a solution for whatever prior you assume.

- We want to find an optimal strategy, not just one that is +EV. Here basically any possible strategy (aside the most idiotic ones) is +EV: we are given 20$ and the chance to bet even money on events with p>50%. How cannot be +EV. Nonetheless, we need to develop a strategy that is optimal in any decision point. While "betting all-in on the result of the first toss" might be +EV to begin with, if the priors are what described in post #69, betting tail if you had a tail is a moronic strategy.

- So we need to build the prior. I agree that an uniform prior doesn't make full use of the information received, and it's likely suboptimal. A uniform prior says that we believe P(H=.50000001) and P(H=0.75) the same. In the former case, however, the guy had to spend maybe billions of tosses before determining such a small bias. If he knows that there is a bias, it's likely that the bias is big.

A non controversial assumption about the prior is that it has to be symmetric: P(H) must be equal to P(1-H). We don't have a reason to believe that the bias is more likely to be on heads, rather than on the tails (or the other way around). A "Jeffrey prior" is much better than an uniform one in this instance.

Also, consider that if the bias is very small, there is not much to discuss about: we are compounding ~0 EV bets and any strategy will have a tiny, marginal EV.

- So, how to formally solve the problem? It's not that hard, at least conceptually. We can make use of beta distribution properties and a simple dynamic programming algorithm that consists in taking the decisions backward. We assume a beta prior on P(H) with parameters (alpha, alpha). alpha = 1 is for the uniform case and = 1/2 for Jeffrey's; however one can use here any alpha>0. Giving both beta parameters the same value makes the prior symmetric. A 0 < alpha < 1 gives more weight to the extreme values of P(H) (the opposite is true for alpha>1, which gives you a bell-shape prior centered at 0.5).

If we assume such a prior, it's easy to show that if we see N_H tails in N tosses, the probability of getting Heads the next toss is (N_H + alpha)/(N + 2*alpha).

Now, say we are before the last decision. We are arrived there with a b_10 bankroll. We might face 10 possible decision point, depending on the number of heads seen so far. For each decision point we know the probability of getting heads. It's easy to show that in any case it's either strictly less or strictly more than 1/2. At that point, the optimal strategy is trivially to bet the entire b_10 on whatever happened most of the times. We can calculate the normalized value (expected bankroll units) of that bet for each decision point and it's:

V(10, W) = 2*(W + alpha)/(9 + 2*alpha)

with W ranging from 5 to 9, being the number of times of the most occurred event. So we have found the value for each decision point before the last toss and we can make use of it for the following.

Now, a step back before the ninth toss. We might face 9 possible decision points. We are there with a b_9 bankroll. We know how likely is to have either heads or tails depending on the eight previous results. Say f is the fraction of b_9 we want to bet. We of course bet on the most frequent value (we might choose whatever if the results are 4-4 so far).

V(9, W, f) = [(1+f) * (W + alpha)/(8 + 2*alpha) * V(10, W+1) + (1-f) * (8 - W + alpha)/(8 + 2*alpha) * V(10, max(W,5))]

Aside from mistakes I might have made in writing, the concept of the formula above is simple. We add the immediate value of the bet we are facing and multiply it for the value we land to after the result. We know the value for each point at step 10 and we use it to calculate the value for each point at step 9. We should optimize the value above for f and find the optimal value V(9, W). Next, we can forget the values at step 10 and use step 9 result to get step 8 optimal strategy and so on.

I'd be very surprised if the optimal strategy won't prescribe f=1 for each decision point.

Here's a simple (toy) 2-step problem that may be illuminating.

Suppose your prior is "balanced" so that you think that Heads and Tails are equally likely in the first flip (or give heads a smidgen of extra probability so that we can say that you bet Heads on the first flip). Suppose that if first flip comes Heads then second flip comes Heads with probability P (P>0.5), and that if the first flip comes Tails then second flip comes Tails with probability Q (Q>0.5).

Your initial bankroll is Y and you can bet any amount of your current bankroll in each of the two stages.

I wrote out the simple decision tree and the max-EV solution is straightforward (and is probably obvious).

If P>Q, then bet Y on the first flip and bet your entire bankroll on the 2nd flip in the favorable direction.

If Q>P, then bet 0 on the first flip and bet your entire bankroll on the 2nd flip in the favorable direction.

I think this "bang-bang" solution is inherent to the "linearity" of EV as many people have previously posted.

As posterior probabilities propagate in a fairly "smooth" manner (nick gives a well-known example of such a family above), I think the "bang-bang" solution virtually always requires you to bet your current entire bankroll on the favorable direction at each stage.

Excellent thread stinky!

Bump: would any non-parametric methods be applicable to this problem?

Lots of thinking too hard and unnecessarily trying to apply advanced statistics to a simple problem in this thread.

You might like non-parametric stats, stinkypete:

Suppose the goal was to get one dollar ahead.

This is pretty complicated and I don't think I can solve it without a computer.

I think the starting point is that we always want to have exactly 10.5 on the final 10th roll no matter what if we haven't already reached $21. So we can work backwards from there.



10th roll:
Bankroll $10.5 Bet $10.5 [50%]

9th roll:
Bankroll $15.75 Bet $5.25 [75%] -> this is simple
Bankroll $10.5 Stand Pat [50%] -> we bet $0 here to gain information
Bankroll $5.25 Bet $5.25 [25%] -> we need to double up twice

Here it gets more interesting:
8th roll:
Bankroll $18.375 Bet $2.625 [87.5%] -> WIN or $15.75
Bankroll $13.125 Bet $2.625 [62.5%] -> $15.75 or $10.5
or
Bankroll $13.125 Bet $7.875 [62.5%] -> WIN or $5.25 (I don't think this is ever correct)
Bankroll $10.5 Bet $5.25 [50%]-> $15.75 or $5.25

I'm not sure of all the possible states here without a more complete solution. Other possibilities on 8th roll:

Bankroll $7.875 Bet $2.625 [37.5%] -> $10.5 or $5.25 or All in -> $15.75 or BUSTO [37.5%]
Bankroll $5.25 [25%] Stand pat.
Bankroll $2.625 [12.5%] All in.


Obviously it blows up from here when we get to the 7th step and I'd need to use a computer to solve this. If I'm feeling ambitious I might work on it this weekend.

Martingale whenever there's a side to bet on?

l think its bet 1 2 4 8 5 10 1 2 4 8 starting from first flip.

Actually I think we can dominate your strategy by betting $8.6875 on your 6th flip. If we get it wrong we still win at least 1/16 and if we get it right we get to wait out the 7th flip for information and win at least 7/8.

With an unbiased coin this is the same as your solution (46.875% to win having reached flip 6) but with bias we do better.

So with the same logic the $5 bet on flip 5 is almost certainly incorrect too.

I didn't think it fully through. But have I changed your mind about needing a computer?

I'm not saying it's unsolvable, but it seems like it's complicated enough that I wouldn't ever do the work necessary to convince myself the solution is correct without a computer.

Unless there's a more elegant way to think about the problem that I don't see.

Ah, now you have given me incentive. Meanwhile do you agree that it is almost inconceivable that you would ever pass on betting if you haven't reached your goal?

there's clear game states where you would pass on betting but it might be the case that you should never reach those spots if your strategy is good. So no I wouldn't say it's almost inconceivable

Off the top of my head I think a pencil and paper can calculate the best strategy if the coin is known to be even money to be fair, 25% to be fully tails, and 25% to be fully heads. Then use logic to show that if any percentage head weighting is equally likely as the tail weighting, you can not improve upon that strategy. Or do that in the opposite order in case my second idea is wrong.

(The above is discussing my getting one dollar ahead question.)

I wonder if that's oversimplifying things. I believe that makes 1 2 4 8 5 10 1 2 4 8 correct. You either win within 2 flips or you know from that point that the coin is fair. So if you solve for a fair coin you have this solution too.