Say that you have $1 and that your friend proposes a game to you. He will take a standard 52 card deck, shuffle it, and flip over cards one-by-one. Before he flips a card, you have the chance to bet anywhere from $0 to your entire bankroll on whether the card will be red or black getting 1:1 odds. What is the strategy that maximizes your EV?

Note 1: One obvious strategy is to let him flip 51 cards betting nothing, waiting for the last card (which after counting cards you will know whether it is red/black) and then bet all of the $1 and end up with $2 total at the end.

Note 2: After you've seen the first card, the deck will be biased towards one color.

If you bet before the first card is drawn, then your EV=0 whether or not you bet any amount x s.t 0<=x<=1 .

If the first card is red , then there are more black cards in the deck . The probability the second card is black is 26/51 .
EV if you bet $1 is 26/51*1 - 25/51*1 = 0.0196...
Clearly it's much better to bet $1 than any other amount .

So , since you don't lose anything and you're getting 1:1 on your bet , you should wait until the last card which gives you an EV=1 .

Maybe this isn't clear from the OP, but the game lasts the entire deck and you can make a bet on EVERY flip (not just one flip). i.e. One strategy could be bet 1/2 my current bankroll on red every flip. Therefore, we want to develop strategies that give us an EV above a final bankroll of $2. One such strategy would be to wait for the last 2 cards. There's a 50% chance that they'll be the same color and that we can martingale our way to 4 dollars, if not we just wait for the last card and just double our bankroll to 2, giving an EV of 3.

I'm not sure why you called this a martingale question.

If betting everything is worth x, and betting nothing is worth y, then betting a fraction z gives you z*x + (1-z)*y. So, you might as well restrict yourself to betting everything or not at all.

If you bet whenever the deck is in your favor, you will average (52/51)(50/49)...(2/1) ~ 9.08. You will bust out whenever the deck deviates from even by more than 1 card, but you will rarely win about $67 million. I hope your friend is good for it.

If you wait until the game is a lock, then double up 1-26 times, you will average the same amount!

I've checked 2:1 and 3:1, and my conjecture at this point is that it doesn't matter whether you bet or not when the game is not a lock, so any sensible strategy which bets everything when the deck only has cards of one color should average the same $9.08. I should be able to prove this shortly.

Did you come up with this problem, or did you encounter it somewhere?

Proof:

By induction, we will show that your equity when the deck is n:k is 2^(2n+k) / (2n+k choose n).

At the base of the induction, this is true for small counts.

Inductively, this equity is how much you get on if you bet everything, or if the deck is n:n. What must be shown is that you can't do better (in fact, you average exactly the same amount) if you bet nothing when the deck is (n+k):n.

n/(2n+k) of the time you end up with a deck that is (n+k)n-1), in which case your equity is
2^(2n+k-1) / (2n+k-1 choose n-1)
by induction.

(n+k)/(2n+k) of the time, you end up with a deck that is (n+k-1):n, in which case your equity is
2^(2n+k-1) / (2n+k-1 choose n)
by induction.

So, your equity if the deck is not a lock, and you bet nothing, is

2^(2n+k-1) (n/(2n+k) / 2n+k-1 choose n-1) + 2^(2n+k-1) ((n+k)/(2n+k) / 2n+k-1 choose n)

= (2^(2n+k-1) / (2n+k-1)!) * ( (n /(2n+k)) (n+k)!(n-1)! + ((n+k)/(2n+k)) (n+k-1)! n!)

= (2^(2n+k-1) / ((2n+k)(2n+k-1)!)) * (n (n-1)!(n+k!) + (n+k)n! (n+k-1)!)

= (2^(2n+k-1) / (2n+k)!) * (2 n! (n+k)!)

= 2^(2n+k) / 2n+k choose n.

QED

Interestingly, both of the cases contribute half of your equity.


I've been trying to post this for the past 30 minutes. Is the server being unresponsive to anyone else?

Interesting Pzhon , I'll see if I can come up with something different .

By the way , I couldn't access this page either .

Yeah.

...
I'm also pretty sure that correct betting will end up providing a return of 9.08 with very little variance using something like the kelly criterion:
Fraction of bank to bet = (2 * favorable cards - total cards)/total cards

That was supposed to be (n+k):n, as I hope was clear from the rest.

My buddy asked me it. He's studying to be a quantitative analyst right now and apparently this was a question that is supposed to help him prepare for the interview process.

I think this was the answer that the quant interviewers were looking for.

For there to be a 0-variance system of bets, at (n+k):n, then with probability 1, you should have

final equity
-----------------
expected gain at (n+k):n

For this to work, you should bet whatever amount will drop you to the right amount at n+k:n-1 if you lose,

final equity ( 2n+k choose n / 2^(2n+k) - (2n+k-1 choose n-1)/2^(2n+k-1))

= current amount (1 - 2 (2n+k-1 choose n-1) / (2n+k choose n))

= current amount (1 - 2 (2n+k-1)!n!(n+k)!/((2n+k)!(n+k)!(n-1)!) )

= current amount (1 - 2n/(2n+k))

= current amount * k / (2n+k)

This agrees with the Kelly criterion, as you suggested.


What property of this problem lets a 0-variance solution exist? Is there some way to see that a 0-variance optimal solution exists for a class of problems where the amount you bet affects your equity, or is there an easy way to see that the amount you bet when you might lose doesn't affect your equity?

Why is the 0-variance solution betting according to the Kelly criterion, as opposed to, say, 1/2 Kelly? The Kelly criterion optimizes the expected logarithm of your bankroll, but fractional Kelly systems maximize expected powers of your bankroll. The Kelly criterion manages to optimize globally, while the fractional Kelly systems don't, and I'm not sure why they don't.

I'm not sure that any uncertain bets will affect your equity, and the certain bets obviously have no variance.

Fractional Kelly is clearly sub-optimal because we know there are certain bets that it won't adequately exploit.

The Kelly criterion (maximizing the expected log) effectively maximizes the expected long term ROI. In a setting where the EV is (effectively) fixed, it will generally minimize variance.

I proved that the uncertain bets do not affect your equity. How does that answer the questions I asked? Failing to make any uncertain bets, or not sizing them exactly correctly, will produce a strategy with positive variance. So, while the uncertain bets don't affect your equity, they affect the variance.

Why don't the uncertain bets affect your equity? Can a 0-variance optimal strategy exist in problems where the uncertain bets do have to be sized properly to produce the optimal equity?

No, fractional Kelly systems should not be viewed as betting a fixed fraction of the amount recommended by the Kelly criterion. That is a description for some continuous gambles, but for discrete gambles such as this, fractional Kelly rules should be viewed as maximizing a different expected utility, where the utility of x is not ln(x), but something like -1/x. That is increasing, so you bet your whole bankroll when you are a lock to win.

If EV is fixed, globally maximizing the expected value of any concave function such as -1/x produces the 0-variance solution. What I pointed out was that using a fractional Kelly system to choose each bet size locally does not result in globally optimizing with respect to that function in this sequence of dependent gambles.

Look at what happens when the deck is 2:1. You can choose to optimize 1/3 V(1-x) + 2/3 V(1+x), but afterwards, you double up once or twice, so the global expected value is 1/3 V(4-4x) + 2/3V(2+2x). Optimizing the former generally doesn't optimize the latter, but for the Kelly criterion, it does. That's specific to this problem, not a tautology from the definition of the Kelly criterion, and I still don't have an explanation.

Perhaps it's a lucky coincidence. I'll sleep on it and have more silly ideas in the morning.

Aside from not betting, there are no zero-variance betting strategies for situations where there are non-certain wagers where the amount wagered affects the EV.

Assume there is a zero-variance strategy for non-certain wagers which effect EV.
In a zero variance strategy, the final result is equal to the EV.
Prior to the wager the EV is equal to V(1), and, after the wager the EV is equal to V(2). Since the strategy has zero variance V(1)=V(2), but since the wager effects ev, there is a non-zero probability that V(1) != V(2). This is a contradiction, therefore no suitable strategy exists.

Now, let's say we have a binary wagering system like this one where there are only two possible outcomes for each wager, and where returns are proportional to the bankroll (this is where the log comes in)
Now, if we're in situation S which can go to S1 or S2, and the wager doesn't affect the EV, we have:
er(S)=(1+b)p(S1)er(S1)+(1-b)p(S2)er(S2)
because we know this is independent of the bet, we can get the er by setting b to zero:
er(S)=p(S1)er(S1)+p(S2)er(s2)
Now, to minimize variance, we want to have the EV of each result to be equal to the prior EV:
(1+b)er(S1)=er(S)=trategy, the final result is equal to the EV.
Prior to the wager the EV is equal to V(1), and, after the wager the EV is equal to V(2). Since the strategy has zero variance V(1)=V(2), but since the wager effects ev, there is a non-zero probability that V(1) != V(2). This is a contradiction, therefore no suitable strategy exists.

Now, let's say we have a binary wagering system like this one where there are only two possible outcomes for each wager, and where returns are proportional to the bankroll (this is where the log comes in)
Now, if we're in situation S which can go to S1 or S2, and the wager doesn't affect the EV, we have:
er(S)=(1+b)p(S1)er(S1)+(1-b)p(S2)er(S2)
because we know this is independent of the bet, we can get the er by setting b to zero:
er(S)=p(S1)er(S1)+p(S2)er(s2)
Now, to minimize variance, we want to have the EV of each result to be equal to the prior EV:
(1+b)er(S1)=er(S)=trategy, the final result is equal to the EV.
Prior to the wager the EV is equal to V(1), and, after the wager the EV is equal to V(2). Since the strategy has zero variance V(1)=V(2), but since the wager effects ev, there is a non-zero probability that V(1) != V(2). This is a contradiction, therefore no suitable strategy exists.

Now, let's say we have a binary wagering system like this one where there are only two possible outcomes for each wager, and where returns are proportional to the bankroll.
Now, if we're in situation S which can go to S1 or S2, and the wager doesn't affect the EV, we have:
er(S)=(1+b)p(S1)er(S1)+(1-b)p(S2)er(S2)
because we know this is independent of the bet, we can get the er by setting b to the entire bankroll.
er(S)=2p(S1)er(S1)
Now, to minimize variance, we want to have the EV of each result to be equal to the prior EV:
(1+b)er(S1)=2p(S1)er(S1)
(1+b)=2p(s1)
b=2p(s1)-1
which is Kelly.

It is easy to show that if you only bet when the game is a lock , then your EV is the same .

2/52c26*[2^26 + 2^25*26c1 + 2^24*27c2 + 2^23*28c3+...2*50c25]= 52/51*50/49*48/47*...*2 .

Again , the best way to show this is to use induction but it's interesting to see if there is a direct way to equate the two .

Ok I found a direct way to show that if you bet when the game is a lock , then it's equivalent to always betting when the deck is in your favor . This is true for any size deck with 2n cards where n is black and n is red .

We wish to prove the following :

2n*(2n-2)*(2n-4)*...*2/[(2n-1)*(2n-3)*...*1] =

2/(2nCn)[2^n + 2^(n-1)*n + 2^(n-2)*(n+1)C2*...2^1*(2n-2)C(n-1)]

We may rewrite the lhs as 2^n*n!*2^n*n!/(2n)! = 2^(2n)*n!*n!/(2n)!

ie , 8*6*4*2 = 2^4*4!

Now the rhs can be written as 2*n!*n!/(2n)!*[...]

Where [...] = 2^(2n-1) which can be shown very easily using a combinatorial argument .

So rhs = 2^(2n)*n!*n!/(2n)! and so lhs =rhs so we're done !