4
$\begingroup$

If we have a loaded coin that plays out 75% heads, 25% tails, what would be the best way to bet on the outcome of each of $n$ trials? How could we maximize our probability of winning?

Is it possible to generalize for a coin that's loaded $n:(100-n)$?

$\endgroup$
9
$\begingroup$

In what follows, I will assume you mean someone gives you 1:1 odds on the loaded coin.

You are looking for the Kelly criterion, which states:

$$ f^* = \frac{ b p - q }{ b } $$

where (just copying from wikipedia) $f^*$ is the fraction of your bank roll, $b$ is the fraction payout (in your case presumably $b=1$, i.e. a dollar investment gives you a dollar return if heads is thrown) and $q = 1-p$.

For your example, the fraction the Kelly criterion says to invest is $f^* = .75 - .25 = 0.5$. i.e. The Kelly criterion tells you to invest half of your savings each time you play.

As intuition, you want to make sure you don't invest all your money on a loaded coin as just one bad throw will deplete your savings. Understanding what function to maximize for is what the Kelly criterion is instructive for.

The Kelly criterion requires that you maximize your winnings based on:

$$ p\ \text{ln}(1 + b x) + (1-p)\ \text{ln}(1 - x) $$

Maximizing for $x$ yields the equation for $f^*$ above.

Unfortunately I am a little unclear as to why this particular equation is being maximized as opposed to some other equation. I have heard an information theoretic argument for why this is so (notice that the equation above looks very much like an entropy equation) but, sadly, still remain puzzled.

EDIT:

Well, I feel pretty dumb. As whuber points out in the comments, the Kelly criterion is quite easy to derive. If we assume a you want to invest a constant proportion of your savings at each trial, call it $r$, then your winnings after $n$ trials, $W_n$, for an initial savings of $W_0$, will be:

$$ W_n = (1 + b r)^{p n} (1 - r)^{(1-p) n} W_0 $$

Taking logarithms, noticing that this equation, as a function of $r$, has one maximum, then setting the derivative equal to 0 and solving gives the Kelly criterion formula for $r = f^*$ as above.

$\endgroup$
8
  • $\begingroup$ I'm not certain what 50:50 odds really means. Does the Kelly criterion require the bets to be dependent on the outcome of the previous bet? $\endgroup$
    – AK.
    Dec 2 '10 at 6:11
  • $\begingroup$ The Kelly criterion tells you how much to bet in order to maximize winnings without dipping to the negatives, depending on 1) payout 2) odds 3) current bankroll. In this case 50:50 payout meant that you're being paid as if the coin were fair, and you can take advantage of that. $\endgroup$
    – sesqu
    Dec 2 '10 at 10:20
  • $\begingroup$ Yes, sorry, I meant 1:1 odds, not 50:50 odds...I've changed the answer to reflect this $\endgroup$
    – user2168
    Dec 2 '10 at 14:21
  • 3
    $\begingroup$ The Kelly criterion is not about Gambler's Ruin. Simply observe that after many (N) plays, you expect to win about pN of them, multiplying your wealth by (1 + bx)^(pN), and lose about (1-p)N of them, multiplying your wealth by (1 - x)^((1-p)N). To maximize this w.r.t. x, take logs. Factoring out N yields the Kelly criterion. In short, if you follow a system of investing a fixed proportion (x) of your wealth each time, and arbitrarily small bets can be made, and you can play for an indefinite time, then the Kelly Criterion gives the optimal proportion to choose. $\endgroup$
    – whuber
    Dec 2 '10 at 14:31
  • 3
    $\begingroup$ @user2168 A subtlety is that your winnings are unlikely to be exactly this formula. You really have to take the expectation. But, as the Central Limit Theorem shows, when N is sufficiently large, the number of wins is highly likely to be within O(Sqrt(N)) of pN. This chance of a relatively small deviation from the expected number of wins does not alter the optimal fraction. $\endgroup$
    – whuber
    Dec 2 '10 at 15:36
7
$\begingroup$

The accepted answer, to use the Kelly criterion, is at best incomplete, if not misleading. It is not what professionals do in practice. It's great to bring up the Kelly criterion, but I think it doesn't actually answer the question.

The "best way" to gamble with an advantage depends on your goals. The Kelly criterion ($f^* = (bp-q)/b = 1/2$ here) is optimal if your goal is to maximize the expected logarithm of your bankroll. It also maximizes the median bankroll among proportional betting systems in an asymptotic sense which fails for finite $n$.

The Kelly criterion is not normally used by professionals who have an advantage, such as professional poker players or hedge fund managers. There are many reasons for this. The main reason is that people are usually more risk-averse than is described by a logarithmic utility function. People often use a fractional Kelly system, which recommends betting a fixed fraction of the amount recommended by the Kelly criterion. Some hedge funds use a fraction of $1/6$. Many professional gamblers view $1/4$ as conservative, and $1/2$ as aggressive. Warren Buffett (known for being aggressive) is said to use a Kelly fraction closer to $0.7$. All of these are significantly more conservative than the Kelly criterion itself, which corresponds to a Kelly fraction of $1$. One consequence of using a Kelly fraction $k$ in a continuous version is that the probability that your bankroll ever falls to $\alpha$ times the original bankroll is $\alpha^{\frac{2}{k} - 1}$. For example, this is $\alpha$ for the Kelly criterion itself, and $\alpha^3$ for a Kelly fraction of $1/2$.

Be careful that the money in your pocket is not usually your bankroll. Fractional Kelly systems assume that losing your bankroll is an infinitely bad disaster. Losing the money in your pocket is probably just an inconvenience. So, you often want to bet a larger fraction of the money in your pocket than your preferred Kelly fraction might suggest. See the bankroll management chapter of my book, The Math of Hold'em.


Back to the second question: "How could we maximize our chance of winning?" It depends what you mean by winning, but it is hard to find a definition so that the Kelly criterion is the answer. Let's suppose $n=10$, and of course that you only bet on heads.

If by winning, you mean you would like to come out ahead, the Kelly criterion comes out ahead if you win at least $7$ times out of $10$. Winning only $6$ times multiplies your bankroll by $3^6/2^{10} = 0.71$. Winning $7$ times multiplies it by $3^7/2^{10} = 2.14$. The chance that the favorable coin will have at least $7$ heads out of $10$ is $77.6\%$.

If you bet up to about $38.9\%$ of your bankroll at each step, then you will come out ahead if there are at least $6$ heads out of $10$, which happens $92.2\%$ of the time. By the way, anything close to the Kelly fraction achieves an expected growth rate which is almost as large. Betting $35\%$ of your bankroll at each step has a greater chance to finish ahead than the Kelly criterion while only giving up about $10\%$ of the growth rate.

You can't come out ahead after $5$ heads and $5$ tails if you are betting the same fraction of your bankroll each time since $(1-x)(1+x) = 1-x^2 \lt 1$. However, if you start by making a small bet, and increase the size of your bets when you lose by just enough to come out ahead, and bet nothing after winning, then you have constructed a reverse lottery ticket. You can have a $99.9999\%$ chance to win at least once and gain $\$0.01$, and about a $1/$million chance that you lose all $10$ times and are out $\$10.23$.

How should you gamble if you would like to maximize your chance to win $\$100$ within $10$ tosses, and you don't have $\$102,300$ in your pocket to cover the reverse lottery ticket? The classic monograph How to gamble if you must: Inequalities for stochastic processes and many more recent works cover the case where you have to bet on the losing side. (Bold play is optimal but it is not uniquely optimal.) However, one speaker at a conference on financial mathematics claimed that how to bet on the winning side is an open problem.

$\endgroup$
7
  • 2
    $\begingroup$ Great answer. I tend to view fractional Kelly staking as being motivated by uncertainty in the edge rather than being because the Kelly criteria is the solution to the wrong problem. I've has reasonable results by tying the fraction to the edge uncertainty, although the work I've done on that is all paper trading for now which is never a true test. $\endgroup$ Jul 17 '12 at 23:42
  • $\begingroup$ I agree that one motivation for betting less than the Kelly criterion is uncertainty about the edge. It is hard to model that mathematically because even a Kelly fraction of 1/100 won't save you if your true edge is negative. You need to be prepared to deviate from a fixed proportional betting system if there is a chance your true edge is negative. However, I really think people (and many institutions) are more risk-averse. Consider having a $33\%$ chance that your bankroll will be cut by a factor of $3$ (Kelly) versus having $75\%$ of the growth, but only a $4\%$ chance ($1/2$ Kelly). $\endgroup$ Jul 18 '12 at 0:37
  • $\begingroup$ Here is another test case: Suppose you get only one chance to bet some fraction of your bankroll on an $85:15$ shot. How much do you want to risk? This $85\%$ is like pocket aces versus a random hand, and this situation has been discussed in poker forums frequented by professional poker players. The consensus there is not to bet anything close to the Kelly recommendation. (Note that for discrete bets, the Kelly fraction and fraction of the Kelly wager are not the same. You maximize a utility function chosen by the Kelly fraction.) $\endgroup$ Jul 18 '12 at 0:44
  • $\begingroup$ Poker is very tricky though, since there is a strong feedback between what you bet and how the other players respond, so there tends to be a lot more to it than straight odds (I'm sure this is not news to you!). $\endgroup$ Jul 18 '12 at 0:46
  • $\begingroup$ The application to poker is not for bet-sizing within a hand, or at least poker players do not assume they understand the consequences of bet sizing so well that they can use bankroll management that way. Typical applications include the choice of stakes such as the following: "Should I play in a NL \$100 game where I win \$10/hour with a standard deviation of \$50/hour, or should I play in a NL \$200 game where I win \$12/hour with a standard deviationof \$100/hour? What bankroll do I need to prefer to play at the higher stake?" Higher stakes games are tougher, so the wagers are not scaled... $\endgroup$ Jul 18 '12 at 1:07
6
$\begingroup$

1/ do you already know the bias n?

2/ if yes (actually you need only to know which side of the coin is heavier) then you cannot do better than always bet on this side.

In the long term, you'll have a n % success ratio. You cannot do better because the trials are independent.

$\endgroup$
2
  • $\begingroup$ Right, you already know the bias. Would this strategy also work for a dice where one face was heavier (again, you are aware that it is)? $\endgroup$
    – AK.
    Dec 2 '10 at 6:08
  • $\begingroup$ Yes, why would you think that it is different? you always play where the probability to win is the highest. Then you can also think about the sizing of your bet, but as you want to "maximize our probability of winning", that's it I guess $\endgroup$ Dec 2 '10 at 6:20
1
$\begingroup$

A 75% win probability is definitely a good edge to have. To answer your question, yes it is possible to generalize for n: 100 - n. The Kelly criteria is a good way to go, but as is pointed out in this thread, the fractional Kelly would also be a good way forward. A write up describing the Kelly criteria and some simulation done in R to show its merits.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.