Optimal strategy for repeated coin toss game - with possible bias

[The Investor]

TL;DR Summary

Adjust your strategy as you receive more information as to what the bias of the coin might be.

You are given the opportunity to play a game where a coin will be tossed 10,000 times consecutively.
You have a starting bankroll of $1,000,000.
The coin may be biased (you are not given any information as to what the probability or the degree of bias might be). A bet on either heads or tails is for even money.

Your goal is to formulate a staking strategy to maximize the geometric growth rate of wealth. On each coin toss you may use the information from the previous results of the tosses to adjust your stake size as a proportion of bankroll, but you must decide on a set of rules (algorithm), before the coin toss procedure starts, and may not change this for the rest of the game. Not betting at all on any particular coin toss is allowed, and if you do choose to bet, you must do so in amounts in round pennies.

 

[marcusl]

Use Bayesian inference, which allows you to compute the odds of winning (or losing) for each of heads and tails Before each bet. You might start off with assuming a 50/50 prior distribution, but this is updated at each bet to incorporate information learned to that point.

 

[The Investor]

Thanks marcusl, that would be a good starting point, but what is an appropriate updating procedure?

And how do you strike a balance between the uncertainty that an edge exists and missing opportunities to have favorable bets? So how do you strike a balance between the time spent waiting to have a high degree of certainty that the coin is biased and missing opportunities to bet in the meantime.

My procedure would be:
*You start with the assumption it's 50/50 and observe the coin tosses without placing bets.
*If the sequence so far reaches the point that the number of occurrences of heads falls in the top or bottom 0.1% of what's expected assuming a 50/50 distribution, start betting on either heads or tails, based on which has occurred most often.
*Any time the sequence so far drops outside of the 0.1% extremes of what's expected, pause betting.
*Stake size is determined by applying the Kelly Criterion *x/10 for each bet, where the expected edge is calculated just by taking the difference between the mean heads proportion and 0.5, and x is the minimum of Sqrt(number of tosses) and 50. (Kelly would be adjusted for each bet as the estimate of edge changes, which is not how it's normally used).

What would we be an 'obviously better' approach than this that is the best you can come up with?

 

[BWV]

The answer is the Kelly Criterion, where your optimal bet equals 2p-1, with p the prob of winning. So without knowledge of an edge or bias, you do not play.

https://en.wikipedia.org/wiki/Kelly_criterion

 

[marcusl]

The Kelly Criterion depends on foreknowledge of the probability of winning (i.e., the bias in the coin), which the OP explicitly says you do not have, so the only choice is to not play as BWV states. An adaptive strategy,on the other hand, should allow one to wager small amounts to gather information about bias and then to begin winning. If the coin is unbiased, then one will not recoup the investment made to discover the bias (or lack of bias) on the coin.

 

[BWV]

right, so just bet zero for the first couple of thousand flips to get an idea if bias exists, if it does then use Kelly

 

[PeroK]

The Kelly Criterion depends on foreknowledge of the probability of winning (i.e., the bias in the coin), which the OP explicitly says you do not have, so the only choice with is to not play as BWV states. An adaptive strategy,on the other hand, should allow one to wager small amounts to gather information about bias and then to begin winning. If the coin is unbiased, then one will not recoup the investment made to discover the bias (or lack of bias) on the coin.

If the coin is close to 50%, then the game is going to be very difficult. If we assume, therefore, that the coin is biased significantly away from 50% then it would not take long to establish this and the Kelly criterion should kick in. We could debate the correct introductory strategy, but no strategy is sound until you have some idea of the bias.

 

[marcusl]

PeroK---agreed.
BWV--It is not clear from the OP if you are allowed to bet 0 and watch the outcome. If yes, then your approach is optimal.

 

[Stephen Tashi]

Optimal strategy for repeated coin toss game - with possible bias
Summary:: Adjust your strategy as you receive more information
as to what the bias of the coin might be.

You haven't defined a mathematical problem that has an optimal solution. (In fact, you haven't defined what function is to be optimized.)

My procedure would be:

The procedures people select are a matter of taste. That said, it may be interesting to hear about them.

 

[The Investor]

Hi all, just to address some of the replies so far:
BMV, The Kelly Criterion is just a piece of the answer. I also alluded to it in repy #3, describing what my strategy would be.

PeroK: That's right, but what I'm after is a more precise formulation of how you would choose to play this game. For example, can you come up with something that is obviously better than what I described in post #3. Just a side note that Kelly is supposed to be applied when you know what your edge is, and that edge is fixed over a series of consective bets. I think if you bet full Kelly, you would be over staking.

In reply to Marcusl, betting 0 at any point is allowed. I did say that
"Not betting at all on any particular coin toss is allowed, and if you do choose to bet, you must do so in amounts in round pennies." ;)

Stephen Tashi, yes that's right, there is not enough information for an optimal mathematical solution. You have to maximize the geometric growth rate of bankroll, but there is some guesswork that goes into how to achieve this, and I'd be interested to see how people would approach this. While it may not have an optimal solution, I think you can reason through why some solutions are obviously better than others. It's more of a practical problem than a purely mathematical one.

 

[Stephen Tashi]

Stephen Tashi, yes that's right, there is not enough information for an optimal mathematical solution. You have to maximize the geometric growth rate of bankroll,

If this was a deterministic problem then "maximize the geometric rate of the bankroll" might be a coherent statement. However, since you say the problem involves probability, that phrase doesn't apply.

 

[BWV]

Don’t see why there would not be a solution to optimize the expected value, the trade off being the robustness of the bias estimate, which increases the longer you bet $0 and increase the sample size of the ‘training set’ vs how many flips you Kelly bet. If allowed, one could bet $0 until some significance level was reached on the bias estimate - longer for smaller bias and shorter for larger- then switch to Kelly

 

[Stephen Tashi]

Don’t see why there would not be a solution to optimize the expected value,

The expected value of what?

The expected net gain at the end of the trials? Optimizing that does not necessarily optimize considerations of risk. For example a strategy with the high expected gain might also have a higher probability of going bankrupt than a strategy with a lower expected gain.

The bias of the coin is not given in the problem, so how can a strategy be optimal, in the sense of being optimal for all possible biases? Stating a strategy as a function of the bias of the coin is not a solution since the bias is unknown. A Bayesian approach that uses a prior probability distribution for the bias can state a well defined mathematical problem.

 

[BWV]

Maximizing the expectation of ending wealth is a well defined problem, as is estimating the bias of the coin. With any bias, Kelly betting maximizes the expected (log) value of ending wealth. No Bayes involved either- merely a frequent its estimation of bias from an initial sample of n flips for $0 bet. The only non-obvious part is how many flips in the sample- in this case flip vs Kelly bet flips, which is a function of what significance level you want to reach in the bias estimate before you begin betting real money

 

[Stephen Tashi]

Maximizing the expectation of ending wealth is a well defined problem, as is estimating the bias of the coin.

Maximizing the expectation of ending wealth without knowing the bias the coin is like finding the length of the third side of triangle given only the lengths of two others. It is a well defined goal, but not a well defined mathematical problem.

Estimating the bias of the coin is a special case of estimating the a parameter of a probability distribution. Parameter estimation is a well known topic in statistics, but it is not a single well defined mathematical problem. In particular there are many different ways in which an estimator can be "good", so there are many different ways in which an estimator can be "optimal" (eg. unbiased, minimum variance, maximum liklihood, best least squares etc.)

Since this is in the math forum, we should get the math right. I don't object to people giving answers along the lines of "if it were me, what I would do is ...". However, claims about mathematical topics like optimality should be mathematically correct.

 

[pbuk]

Hmmm, initially I was not sure you were right @Stephen Tashi but then I re-read the question.

When I first read

Maximizing the expectation of ending wealth without knowing the bias the coin is like finding the length of the third side of triangle given only the lengths of two others.

I read this as: "maximizing the expectation of ending wealth without knowing the value of the bias [of] the coin is like finding the length of the third side of triangle given only the lengths of two others", and I thought "but surely we simply need to integrate the expected value of each strategy given bias β over the pdf ϕ(β)".

But then I re-read the OP

...you are not given any information as to what the probability or the degree of bias might be

and I realize that you meant "maximizing the expectation of ending wealth without knowing the distribution of the bias [of] the coin is like finding the length of the third side of triangle" - and of course this is right. To extend the analogy further, if we knew the pdf of the angle between the known sides we could calculate the expected value of the third side, but if the probelm explicitly states that this pdf is unknown then it is not sufficiently defined to yield a solution.

Perhaps "The Investor" has realized this and moved on to another sure-fire way to maximise profit

 

[Stephen Tashi]

The problem can be made well defined in various ways. For example, the Game Theory approach would be to phrase it as a "min-ah-max" problem. We think of a game where player 1 picks a strategy. Player 2 is informed of the strategy and then he picks the bias of the coin. Player 1's objective is to maximize his expected gain. Player 2's objective is to minimize Player 1's gain.

When Player 1 picks a strategy, he evaluates its expected gain on the assumption that the bias of the coin will be chosen to minimize the expected gain of that strategy.

The Game Theory approach is more pessimistic (for Player 1) than a typical Bayesian approach. The Bayesian approach doesn't assume an intelligent opponent working against Player 1.

The set of "all possible strategies" may be too diverse to work with. It would be similar to saying the distribution of a random variable is known to be in the family of "all possible probability distributions" - which isn't much help when it comes to estimating the parameters of its distribution.

We could consider particular families of strategies. For example there is a family of strategies can be defined by:
Don't bet for the first N turns. Estimate p(heads) by the fraction of heads that occurs on the first N turns. On turn N+1 and after use the Kelly betting procedure for selecting how much of our bankroll to bet, updating the estimate of p(heads) after each turn.

For a given (true) value of p = p(heads), what is the expected gain of that strategy for a given N? We might have use Monte-Carlo to estimate it. If we can find the expected gain G as a function G(p,N) then the Game Theory approach asks us to find the N that produces $Max_N(Min_p G(p,N))$. (The function $Min_p G(p,N)$ is a function of N alone. )

 

[Stephen Tashi]

Reflecting on the Game Theory approach, player 2 could select the coin to be fair. This would limit player 1's expected gain to zero.

You can't win money betting on the outcome of a fair coin. (What's the general proof of that? - a symmetry argument? ).

An interesting question is whether a possible strategy has a coin that makes its expected gain negative. The trivial strategy "never bet" can't have negative gain regardless of the coin. Are there others?

 

[BWV]

How could there be a negative expectation when the bettor can call the side?

I played around with Kelly betting on this in Matlab, curious about the skew you get with larger bets - i.e. if you ignore Kelly and bet, say 10% of your bankroll on a 1% edge, you will almost certainly go bankrupt even though the overall expectation is large

From a 1000 sample MC, with $1M bankroll, 10,000 flips (ignoring the sampling issues above), 1% edge (51% chance of heads)
Kelly betting 2% of your bankroll:
- never go bankrupt (I define bankrupt as bankroll <$1, can't go to zero as bets are a % of bankroll)
-mean ending wealth ~ $50 million
-median ending wealth - $7.1 million
% of simulations where bankroll ended <$1M - 15.3%.betting 10% of your bankroll:

Mean ending wealth: $24.7M
Median ending Wealth: $0
prob bankruptcy: 99%

The game of as described in the OP of course would never exist

 

[Stephen Tashi]

How could there be a negative expectation when the bettor can call the side?

This depends on his strategy for calling the side, doesn't it? In the scenario for the OP, the bettor doesn't know the odds since he doesn't know the probability of the coin landing heads. He can't implement Kelly betting without knowing the probabilities.

 

[zinq]

"Your goal is to formulate a staking strategy to maximize the geometric growth rate of wealth."

What is left unstated here is this: What is the criterion by which the maximum is determined?

Is it expectation, i.e., the average value gained under all equally likely outcomes of the coin?

Without a stated criterion, it is impossible to answer the question.