Two Plus Two Publishing LLC Two Plus Two Publishing LLC
 

Go Back   Two Plus Two Poker Forums > General Gambling > Probability

Notices

Probability Discussions of probability theory

Reply
 
Thread Tools Display Modes
Old 09-06-2007, 12:40 PM   #1
grinder
 
MooBot3000's Avatar
 
Join Date: Sep 2005
Location: GTHCGTH
Posts: 415
Martingale game question...

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.
MooBot3000 is offline   Reply With Quote
Old 09-06-2007, 01:37 PM   #2
Pooh-Bah
 
Join Date: Sep 2006
Posts: 3,655
Re: Martingale game question...

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 .
jay_shark is offline   Reply With Quote
Old 09-06-2007, 01:51 PM   #3
grinder
 
MooBot3000's Avatar
 
Join Date: Sep 2005
Location: GTHCGTH
Posts: 415
Re: Martingale game question...

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.
MooBot3000 is offline   Reply With Quote
Old 09-06-2007, 02:01 PM   #4
Pooh-Bah
 
Join Date: Mar 2004
Posts: 5,363
Surprisingly, not the martingale crap.

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?
pzhon is offline   Reply With Quote
Old 09-06-2007, 02:48 PM   #5
Pooh-Bah
 
Join Date: Mar 2004
Posts: 5,363
Re: Surprisingly, not the martingale crap.

Quote:
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.
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?
pzhon is offline   Reply With Quote
Old 09-06-2007, 03:33 PM   #6
Pooh-Bah
 
Join Date: Sep 2006
Posts: 3,655
Re: Surprisingly, not the martingale crap.

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

By the way , I couldn't access this page either .
jay_shark is offline   Reply With Quote
Old 09-06-2007, 03:42 PM   #7
grinder
 
Join Date: Aug 2005
Posts: 477
Re: Surprisingly, not the martingale crap.

Quote:

I've been trying to post this for the past 30 minutes. Is the server being unresponsive to anyone else?
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
rufus is offline   Reply With Quote
Old 09-06-2007, 05:02 PM   #8
Pooh-Bah
 
Join Date: Mar 2004
Posts: 5,363
Re: Surprisingly, not the martingale crap.

Quote:
By induction, we will show that your equity when the deck is n:k is 2^(2n+k) / (2n+k choose n).
That was supposed to be (n+k):n, as I hope was clear from the rest.
pzhon is offline   Reply With Quote
Old 09-06-2007, 05:30 PM   #9
grinder
 
MooBot3000's Avatar
 
Join Date: Sep 2005
Location: GTHCGTH
Posts: 415
Re: Surprisingly, not the martingale crap.

Quote:
Did you come up with this problem, or did you encounter it somewhere?
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.
MooBot3000 is offline   Reply With Quote
Old 09-06-2007, 05:35 PM   #10
grinder
 
MooBot3000's Avatar
 
Join Date: Sep 2005
Location: GTHCGTH
Posts: 415
Re: Surprisingly, not the martingale crap.

Quote:
Quote:

I've been trying to post this for the past 30 minutes. Is the server being unresponsive to anyone else?
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
I think this was the answer that the quant interviewers were looking for.
MooBot3000 is offline   Reply With Quote
Old 09-06-2007, 07:04 PM   #11
Pooh-Bah
 
Join Date: Mar 2004
Posts: 5,363
Re: Surprisingly, not the martingale crap.

Quote:
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
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.
pzhon is offline   Reply With Quote
Old 09-06-2007, 09:20 PM   #12
grinder
 
Join Date: Aug 2005
Posts: 477
Re: Surprisingly, not the martingale crap.

Quote:

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?
I'm not sure that any uncertain bets will affect your equity, and the certain bets obviously have no variance.

Quote:
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.
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.
rufus is offline   Reply With Quote
Old 09-06-2007, 10:41 PM   #13
Pooh-Bah
 
Join Date: Mar 2004
Posts: 5,363
Re: Surprisingly, not the martingale crap.

Quote:
Quote:

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?
I'm not sure that any uncertain bets will affect your equity, and the certain bets obviously have no 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?

Quote:
Quote:
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.
Fractional Kelly is clearly sub-optimal because we know there are certain bets that it won't adequately exploit.
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.

Quote:
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.
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.
pzhon is offline   Reply With Quote
Old 09-07-2007, 01:15 AM   #14
grinder
 
Join Date: Aug 2005
Posts: 477
Re: Surprisingly, not the martingale crap.

Perhaps it's a lucky coincidence. I'll sleep on it and have more silly ideas in the morning.
rufus is offline   Reply With Quote
Old 09-07-2007, 12:14 PM   #15
grinder
 
Join Date: Aug 2005
Posts: 477
Re: Surprisingly, not the martingale crap.

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.
rufus is offline   Reply With Quote

Reply
      

Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are Off
Pingbacks are Off
Refbacks are Off



All times are GMT -4. The time now is 03:06 PM.


Powered by vBulletin®
Copyright ©2000 - 2014, Jelsoft Enterprises Ltd.
Content Relevant URLs by vBSEO 3.6.0 ©2011, Crawlability, Inc.
Copyright 2008-2010, Two Plus Two Interactive