First, the N=1 case. There is little point in betting on the first card, the adversary will just make you wrong anyway, so after the first card comes by, you know what the second card is. You bet everything on the second card, are correct, and end with $2.
Now for N=2. There is actually still no point in betting on the first card (this is a pretty general result), so lets say the first card is red. Now there is 1 red and 2 black in the deck. One might be inclined to say there is no point in betting here, but then the adversary will surely show us a black card the second time and we are in the N=1 case. Really, the fact is we would be very happy is the adversary showed us the second red card on the second round, so happy that we might be willing to pay him a small amount of money to make it happen.
Suppose you bet $0.1 on the second card being black, then if it is black, you have $1.1 and are in the N=1 case, so you get to double that to $2.2. If the second card is red, you have $0.9, but now there are only black cards in the deck, so you get to quadruple that and end with $3.6. Clearly the adversary will let you end with $2.2. Now suppose we instead bet $0.5 on the second card being black. If it is black we have $1.5 and get to double that to $3. If it is red we have $0.5 and get to quadruple that to $2. Clearly the adversary will let us have $2.
Alright, we need a middle ground. Bet x on the second card being black. If it is, we have 1+x and we get to double that to 2+2x. If it is not black we have 1-x and we get to quadruple that to 4-4x. The adversary will give us whichever is lower, and since one is an increasing function and the other is a decreasing function, the lowest one is maximized when they are equal. Solving 2+2x=4-4x we have x=1/3. So we should bet 1/3 on the second card being different than the first one and we are guaranteed to end with $8/3.
Note that in the solution to the N=2 case the answer comes out path independent, in that after two black cards and one red card have come by, you have $4/3 no matter if it was BRB or BBR (I'm sort of assuming that the adversary chooses to show black cards rather than red when the situation is symmetric). Naturally it has to be path independent, if the different paths gave different amounts of money, the adversary would send you on the worst path he can find. Due to this, it is a general feature that the solution for general N be path independent.
Now let us try to solve with general N. As we have seen, since the solution is path independent on how the adversary shows us cards, there must be a function f(r,b) that represents how much money we have when r red cards have gone by and b black cards have gone by. Clearly f(r,b) could depend on the specific value of N we use, so it really should be f(r,b,N), but I'm going to suppress that last variable. We also know that f(0,0)=1, and f(r,b) must equal f(b,r) by a similar argument to the one that shows path independence, and f(N,N) is the answer we seek.
Suppose we have see r red cards and b black cards go by, so we have f(r,b) money according to our strategy, and we now bet x on the next card being red (if we are instead betting on black, we just let x run negative). If the next card is red, we have f(r,b)+x money and if it is black we have f(r,b)-x money. This means that:
f(r+1,b)=f(r,b)+x
f(r,b+1)=f(r,b)-x
For some value of x. Eliminating x, we have
2f(r,b)=f(r+1,b)+f(r,b+1)
Similar to the relation for Pascal's triangle. To make it look a bit more familiar, lets define g(r,b) by f(r,b)=2r+bg(r,b), then g obeys the relation
g(r,b)=g(r+1,b)+g(r,b+1)
Now that looks like the Pascal relation, but its backwards. Next lets define h(r,b)=g(N-r,N-b), so h counts how many cards are left in the deck rather than how many cards we have seen go by. Then h obeys
h(r,b)=h(r-1,b)+h(r,b-1)
Perfect for solving as a previously solved problem. But since we knew f(0,0)=1, this means we know h(N,N)=1, so h is a bit backwards. We simply modify this by defining p(r,b)=h(r,b)/h(0,0). Now p obeys
p(r,b)=p(r-1,b)+p(r,b-1)
and p(0,0)=1, so p is the Pascal function, that is
p(r,b)=(r+b)!/(r!b!)
We can find h(0,0) by noting that p(N,N)=h(N,N)/h(0,0)=1/h(0,0), so h(0,0)=1/p(N,N), giving
h(0,0)=N!N!/(2N)!
so that we have h
h(r,b)=p(r,b)h(0,0)
=(r+b)!N!N!/(r!b!(2N)!)
This gives us g
g(r,b)=h(N-r,N-b)
=(2N-r-b)!N!N!/((N-r)!(N-b)!(2N)!)
Finally, we get f
f(r,b)=2r+bg(r,b)
=2r+b(2N-r-b)!N!N!/((N-r)!(N-b)!(2N)!)
ugh.
At least we really only care about 1 thing, f(N,N), its simple enough:
f(N,N)=22NN!N!/(2N)!
Which is just 22N divided by 2NCN. For N big enough to use Stirling's approximation (which 26 is), we have
f(N,N)=22NN2Ne-2N(2π N)/((2N)2Ne-2N √(2π 2N))
=√(π N)
Actually comes out quite simple. For N=26 this is about 9.
So this actually is the complete construction of the strategy. At any given time you have seen r red and b black cards come by, you have f(r,b) money left, and you should bet f(r+1,b)-f(r,b) on red (or, equivalently, f(r,b+1)-f(r,b) on black) and you will end with f(N,N) money. Actually performing the strategy can be done in a slightly different way though.
Suppose you have K assistants, where K is the number of possible configurations of the cards in the deck (that is, K=2NCN). Each assistant is given 1/K money to start and is told a list of R's and B's that could correspond to the cards in the deck (for N=2, the assistants are told RRBB, RBRB, RBBR, BRRB, BRBR, BBRR), and you let them all bet simply assuming that their own list is correct. Precisely one of them will be correct and will double his money 2N times (once for each card). The rest all lose their money. The correct assistant ends with 22N divided by 2NCN money, exactly f(N,N).
Lets try this for N=2, we have our 6 assistants which will be labeled as follows:
1.RRBB
2.RBRB
3.RBBR
4.BRRB
5.BRBR
6.BBRR
Each assistant is given $1/6.
This game starts, and assistans 1,2,3 bet their $1/6 on red while assistants 4,5,6 bet their $1/6 on black. We (the real holder of the $1) add this up and bet a net zero. Suppose the first card is red. This eliminates assistants 4,5,6 and assistants 1,2,3 now all have doubled their money to $1/3. We have a total money of $1.
Next card, assistant 1 bets his $1/3 on red and assistants 2 and 3 bet their $1/3 on black. We add this up and bet $1/3 on black. Suppose the next card is black. This eliminates assistant 1 and doubles assistants 2 and 3's money to $2/3. We have a total money of $4/3.
Next card, assistant 2 bets his $2/3 on red and assistant 3 bets his $2/3 on black. We add this up and bet nothing. Suppose the card is black. Assistant 2 is eliminated and assistant 3 doubles his money to $4/3. We have a total money $4/3.
Final card, assistant 4 bets his $4/3 on red. We add this up and bet $4/3 on red. We double our money to $8/3.
This game also has one other neat feature if you actually play it. All betting strategies are fair, as long as you never bet on a card that does not remain in the deck. That is to say, in any given position of red and black cards left, no matter what you bet on what card coming next, your expectation of final money (against a shuffled deck, not an adversary) is the same, as long as when the deck is out of one type of card you bet maximally on the card colour that is left.
No comments:
Post a Comment