The Value Of One Bit

I was looking over my "solution" threats, and it seems that about 90% of them begin with "time to post the solution to", so I figure I'm about sick of that. Sick of it this week anyway, next time I'll be back to it. Anyway, now that I have actually began the post with something different, time to post the solution to the bit in a bottle problem.

First I will give my formulation of the solution, and then I will show that it is optimal in a sense (a pretty convincing sense as well, not just some esoteric one). First, consider what happens if you just bet heads all the time. Your total money will simply preform a random walk on the integers starting with N, and will terminate if it ever hits zero. With probability 1, it will hit zero in finite time.

Now, I will construct two strategies, first define the following strategy

Strategy H: Every game, bet heads until you have reached $0 or $2N. If you ever reach $0 or $2N, quit playing.

Similarly, define a strategy for tails

Strategy T: Every game, bet tails until you have reached $0 or $2N. If you ever reach $0 or $2N, quit playing.

Now, we can show that one of these strategies will hit $0 and the other will hit $2N (this should be pretty intuitive, but lets prove it anyway). For a particular sequence of flips, let M(S,k) be the amount of money that strategy S will have after k flips. Then I claim that

M(H,k)+M(T,k)=$2N

This is easy to prove by induction, as it is true when k=0 and every time strategy H gains $1, strategy T loses $1 and vice-versa. The strategies also terminate at the same time, as failing to do so would violate the equality. It is theoretically possible that the strategies do not ever terminate, but that has zero probability of happening.

Now, the question we ask the genie is simple. First define strategy H for the genie, then ask:

If I follow strategy H, will I end with $0?

If the answer is yes follow strategy T, if the answer is no follow strategy H. This guarantees that you will end with $2N (where "guarantees" means "with probability one"). You can also change strategy H to any specific betting sequence rather than all heads if you like, as long as strategy T is the compliment of that sequence, this will still work.

Next I want to prove that this solution is optimal. It might seem surprising that we can optimize over the space of all possible questions, since math usually is not very good at handling human language. To deal with this, first consider C to be the set of all the possible coin flip results, so C contains things like HHTHH..., THTTH.., TTTHT..., and so on. Next consider a possible yes or no question, denoted Q, that for every element of C the question must answer exactly "yes" or "no". Thus Q partitions C into two disjoint subsets, called Y and N. Really, any Q is equivalent to selecting the sets Y and N and asking the genie "is the coming sequence of coin flips in Y?" So, to optimize over all questions Q, we really just need to optimize over choice of sets Y and N, and it is less surprising that math can handle that.

Before moving on, I must state an obvious but important fact of probability theory. Consider we have two disjoint events, X and Y (that is to say, exactly one of them must happen (thats not actually what disjoint means, but I don't know the correct term)), and a third event called A. Let P(x) is the probability that event x happens, and P(x|y) is the probability that event x happens given that event y happened. Then, the probability that event A happens can be written as:

P(A)=P(A|X)P(X)+P(A|Y)P(Y)

That is, A must happen with X or Y, so we calculate the chance it happens with X plus the chance it happens with Y. We need not subtract the chance it happens with both, as X and Y are disjoint. It is easy to generalize this to more disjoint events X,Y,Z,... We can also make a similar statement about expectation values, let E(A) be the expectation value of some variable A and E(A|x) is the expectation value of A given that event x is true. Then for disjoint events X and Y we have:

E(A)=E(A|X)P(X)+E(A|Y)P(Y)

An intuitive result, to be sure, but an important one anyway.

OK, now that that is out of the way, the next important step in the proof is to consider what will happen with no genie. Suppose you have some strategy S, and after k flips the strategy has an expected value E(S,k). The expected value will be determined by the chance that you went up a dollar on that flip (call that P(+)) and that chance that you went down a dollar on that flip (call that P(-)), and the chance that your strategy had told you to stop (call that P(O)). Specifically:

E(S,k+1)=(E(S,k)+1)P(+)+(E(S,k)-1)P(-)+E(S,k)P(O)

It is clear that P(+)+P(-)+P(O)=1 (since every round you either gain a dollar or lose a dollar or stop), and also P(+)=P(-) since without access to a genie we have no knowledge about the coin flips. This means that:

E(S,k+1)=E(S,k)

So, E(S,k) is a constant, and that value must equal $N, since E(S,0) is $N. This proves that with no genie, all strategies have the same expectation value after a fixed number of flips. Note that something funny happens if you just let k=∞ since strategies such as "play until I run out of money" are guaranteed to have zero money at the end, even though after a finite number of flips there is a chance of the player having a large amount of money for the time being (this is known as the "gamblers ruin").

Alright, now let us find what is the best we can do given our genie scenario. First let x represent the coming sequence of coin flips, the genie knows the value of x. Consider that we have a strategy specified by a question Q (which simply selects the sets Y and N), a strategy S(Y) (which is what we will do if the genie tells us x is in Y), and a strategy S(N) (which is what we will do if the genie tells us x is in N). We want to find E(S,k), the expectation value of our strategy S (=(Q,S(Y),S(N))) after k flips. Letting Y represent the event "x is in Y" and N represent the event "x is in N", we see that Y and N are disjoint events, so that:

E(S)=E(S|Y)P(Y)+E(S|N)P(N)

I really should have some k's in there also, but they are going to get cumbersome so I am just going to drop them for now. Now, E(S|Y) is just E(S(Y)|Y), since S says to play S(Y) when Y is true, also E(S|N)=E(S(N)|N) for the same reason. That is to say

E(S)=E(S(Y)|Y)P(Y)+E(S(N)|N)P(N)

To get any more information out of this, consider again what would happen to us with no genie. We could just play S(Y) anyway, but we already know that E(S(Y))=$N (one would expect that E(S(Y)|Y) would be higher, since then we also know that x is in Y, but if we just play S(Y) with no other information then its expectation value is $N) (I must say this is only true after k flips, if the number of flips is infinite weird things might happen). How else could we calculate E(S(Y))? we could just consider if x is in Y or N, specficially

E(S(Y))=E(S(Y)|Y)P(Y)+E(S(Y)|N)P(N)

That is the value of strategy S(Y) when Y is true plus the value of strategy S(Y) when N is true (remember, we have no genie right now). Now since E(S(Y)|N) cannot be negative, and P(N) cannot be negative, that second term cannot be negative. Thus we have a bound on E(S(Y)|Y)P(Y), given by

E(S(Y)|Y)P(Y) ≤ $N

Similarly, switching Y for N we have

E(S(N))=E(S(N)|Y)P(Y)+E(S(N)|N)P(N)

and therefore

E(S(N)|N)P(N) ≤ $N

We can put this together in our last equation for E(S) to get

E(S) ≤ $2N

Proving the optimality of the solution presented earlier. It appears that the value of one bit is to exactly double your cash. If you can instead ask the genie a question with possible answers 1,2,3,... up to some fixed K then you can extend this proof to show it is optimal to multiply your money by K.

Naturally, it is possible to get other strategies to end with more than $2N, they just cannot guarantee ending with that much. Even with no genie one can simply play the game and only quit if you hit $0 or $3N, you might end with $3N in this case, but it cannot be guaranteed. I will also point out that the proof relied on the game not taking an arbitrarily long amount of time, my intuition is that the result is still valid even without that assumption, but I do not see a good proof.

I do like this solution in that it is practical, one would reasonably use it if actually presented with this situation, and the genie does not even need to do an infinite amount of work (probably not anyway, its possible that the random walk never terminates, but thats probability zero). The genie can even be replaced by a mathematically competent human who simply has access to the coming flips.

There is a harder problem posed of the xkcd forums where losing a flip costs you a $1 and winning a flip gains you $(1-q) where q is a small positive number. I have not made any real progress to finding a solution to this problem, but anything involving random walks seems risky, so another approach might be needed.

Bit In A Bottle

New puzzle time I suppose. This one looked like it was a bit of a silly one, but it turns out that there is a bit more interesting math in it than I expected. I first found this on the forums at xkcd:

You are playing a game where you are betting on the outcome of coin flips. Playing the game costs $1 and you get to guess either heads or tails. A coin is then flipped and if you guessed correctly you win back your $1 and another $1, if you guessed wrong you lose your $1. You may play the game as many times as you want as long as you have the money to continue, or may quit anytime. Before the game, you have access to a genie that will answer any one yes/no question about the coin flip game. The genie knows the results of all the coming flips. Given that you start the game with $N, find a strategy that maximizes your winnings.

Earlier I had posed the problem stating that the genie knew the future, but that can cause weird possible questions involving not having a well posed question. Anyway, the intention is that the genie be capable of answering your question solely knowing what the coin flips are going to be. If a genie who knows the outcome of random events bothers you, we can instead suppose all the flips have been determined ahead of time and the genie simply has access to all the results.

Clearly with no genie, the only thing you can do will have an expected final outcome average of $N, since the game is fair for all strategies, so the question is to find out how much the one bit of information the genie gives you is worth. One thing I found interesting about this problem is that you can also prove optimality of the correct answer.

Giving Cards

Time for the solution to the card game from last time. I suppose the standard thing to do is consider simpler cases.

In the case when N=1, the start player must simply take the card (if they are playing optimally, anyway). Next, if N=2 it is optimal to give the 1 card and take the 2 card.

For N=3 we have a real choice. We can simply take the 1 card, in which case the opponent will give us the 2 so they can keep the 3 (ending with 3 vs. 3 total utility). If instead we give the 1 card we will be left in the 2,3 case and it is clearly optimal to give the 2 and take the 3 (again, a 3-3 ending).

Next we must study N=4. This gets a bit trickier, as in order to choose what to do with the top card we must first find the optimal play in the 2,3,4 case. This is not particularly difficult, but it does show that in general we must solve a subgame with cards K,K+1,K+2,...N left in the pile.

Consider a situation where the top card is K and there are L cards left. Specifically the remaining cards are numbered K through K+L-1 (To convince yourself of that -1 consider L=2). Now let us inductively solve this on L. When L=1 we take (this is obvious). When L=2, we give then take, getting K+1 utility instead of just K. When L=3 we have a choice. If we choose to take, we will get card K and the opponent will give us K+1 to take K+2. If we give when L=3, we must also give when L=2 and take the last card, getting K+2 instead of K and K+1. So when L=3, choosing take gets 2K+1 vs choosing give getting K+2, comparing these we can see that 2K+1>K+2 iff K>1, and 2K+1=K+2 iff K=1. In a typical case K>1, so we should keep, and in the exceptional case K=1 we can do whatever (and might as well keep). In particular, being the active player when L=3 and card K is on top is worth K-1 utility.

Next, consider L=4. If we keep, then we get to keep card K, the opponent will keep card K+1 allowing us to give card K+2 and keep card K+3. If we give K we will keep K+1 (L=3 then, so we keep at that point) and the opponent will give K+2 to keep K+3. In the end, keeping gets us K+K+3 vs giving getting us K+1+K+2. These are the same, this result is somewhat clearer when you note that it is worth K utility to be the active player when L=3 and K+1 is on top, but keeping the top card of L=4 is worth exactly K, so keeping the top card of L=4 and being the next active player are worth exactly the same amount, so we do not care. Note that a result of this is that being the active player when L=4 is worth zero utility.

Next, L=5 (hopefully this goes somewhere soon). When L=5, we do not care who is the active player on the coming turn, being active when L=4 is worthless anyway. Thus, when L=5, we might as well keep. For L=6, whoever gets to go on the following L=5 turn will just take the top card worth K+1, so we should give K to the opponent and take K+1 when L=6.

When L=7, we get a similar analysis to L=3. We can take K and receive K+1, watching the opponent take K+2 (because the following initiative on L=4 is worthless). Or we can give K and K+1 to take K+2 (sounds sad unless K=1). This means we should take when L=7. L=8 comes out the same as L=4, being a worthless turn to have the initiative, we can keep or give, it does not matter.

We can see a pattern here. We need only look at how many cards are left mod 4. If the number of cards is 0 mod 4, this turn does not matter. If it is 1 mod 4, keep because the next turn does not matter. If it is 2 mod 4, give so you can keep the next card. If it is 3 mod 4, keep because the opponent is going to give then keep (unless the top card is K=1, then you can give it if you want).

So, if the total number of cards left is odd, you should always keep. If the total is even then give if it is not a multiple of 4, and play random if it is, alternately, you can just always give when the number of cards left is even and you will not be making any mistakes.

This means that the optimal play will have the players constantly performing give-keep actions. There is another way to see this, consider a pair of players that constantly keep the top card. They will divide the deck between them until one of them takes the last card. It is not hard to see that the person who gets the last card has a much higher utility than the other person, as their cards are all 1+ the other persons card. That is to say, the person who got to keep on the turns with odd numbers of cards left is much happier. Two optimal players are just taking turns trying to be the person who gets to take the cards when there are odd numbers of cards left.

The result of the game is that the players divide up the utility quite evenly. Let n be N mod 4. If n=0, the players will split the utility evenly. If n=1, then the first player gets a 1 utility advantage, but the rest is even. If n=2 the active player again gets a 1 utility advantage, by giving the 1 and taking the 2. If n=3, then the players split it evenly again.

How much utility is in the deck? With N cards, there is N(N+1)/2 in total (the N^th triangle number). Exactly one of N or N+1 is even, so the total utility in the deck will only be even if that number is also a multiple of 4. So, the only way that the utility can be split evenly is if N or N+1 is a multiple of 4, that is n=0 or n=3. In the other two cases, there is an odd utility out and the first player to take a turn will always get it.

Taking Cards

So, while I was away for new years stuff, I played boardgames (as I usually do) and while playing a game of Strozzi I came up with a new logic puzzle. It turned out that that puzzle sucked, so I modified it into a different one. That one was less sucky but more boring, so I changed it again to come up with this:

There is a stack of N cards numbered 1 to N in order, with 1 on the top and N on the bottom. Two players are going to play a game where they will each wind up keeping some of these cards. The utility a player gets from playing the game is equal to the sum of the numbers on all the cards the player kept.

The game works by the players taking turns. On a turn, the active player may either keep the top card or give it to the other player. If the active player kept the card, then the other player gets the next turn. If the active player gave the card away, then the active player gets to take another turn. The play continues until the deck is empty.

Assuming optimal play, what is the result?

If you don't like utility, instead assume that the cards are worth $1 to $N, in order, with the $1 card on top and the $N card on the bottom. A player gets to cash out all of the cards that that player kept at the end of the game. People like money, right?