Let us call X(t), the capital at time t. A game is winning (loosing) if the average <X(t)> is a monotonously increasing (decreasing) funtion of t and it is fair if <X(t)> is constant.
It is easy to prove that game A is a loosing game if e positive:
<X(t+1)>-<X(t)> = <X(t+1)-X(t)> = (1/2 - e) - (1/2 + e) = -2e
| Game A | ||
| COIN 1 |
Prob. of winning | Prob. of losing |
| 1/2 - e | 1/2 + e | |
The analysis of game B is not that easy. Remember the rules:
| Game B | |||||
| Is X(t) a multiple of 3? | |||||
| NO | YES | ||||
| Coin 2 |
Prob. of winning | Prob. of losing | Coin 3 |
Prob. of winning | Prob. of losing |
| 3/4 - e | 1/4 + e | 1/10 - e | 9/10 + e | ||
a naive (and wrong) argument is as follows: coin 3 is used 1/3 of the time, whereas coin 2 is used 2/3 of the time. Then, the probability of winning is:
pwin= (2/3) (3/4-e) + (1/3) (1/10 - e) = 17/30 - e
which is slightly bigger than 1/2 for e = 0. Then, game B, according to this argument, is not a loosing game.
The argument is not correct because coin 3 is not used one third of the time, but a little bit more often. If X(t) is a multiple of three, say 9, then we use coin 3 and the most likely result is loosing. Then, the most likely value of X(t+1) is 8. We have now to use coin 2, and the most likely result is now winning. Therefore, oscillations between 9 and 8, or between 3n and 3n-1 have a high probability. As a consequence, the frequency of using coin 3 is between one third and one half.
The calculation of this frequency is a little technical. Let us define the variable:
Y(t) = X(t) mod 3
which can take only three values: 0,1, and 2. Y(t) is a Markov chain with three states and a transition matrix given by:
| P= | 0 | 1/4 + e | 3/4 - e |
| 9/10 + e | 0 | 1/4 + e | |
| 1/10 - e | 3/4 - e | 0 |
The probability distribution P(t), i.e., the vector whose components are the probabilities Pi(t) of Y(t)=i with i=0,1,2, obeys the evolution equation:
P(t+1) = P P(t)
The matrix P has three eigenvalues: one is equal to 1 and the modulus of the other two is smaller than 1. The eigenvector corresponding to eigenvaue 1 is the stationary probability distribution, i.e., its components are the probability of Y(t)=0,1, and 2 for t very large.
We are interested on the probability of Y(t)=0, which reads, for e small:
P0= 5/13 - (440/2197) e = 0.3846 - 0.2003 e
which is the probability of using the bad coin 3. The probability of winning is:
pwin= (1-P0) (3/4-e) + P0 (1/10 - e) = 1/2 - 147/169 e = 0.5 - 0.87 e
which is smaller than 0.5 for e positive.
Now, when games A and B are combined, we have:
P'0= 245/709 - 48880/502681 e = 0.3456 - 0.9724 e
and
p'win= (1-P0) (5/8-e) + P0 (3/10 - e) = 727/1418-486795/502681 e = 0.5127 - 0.9684 e
The paradox occurs for e small enough to have:
pwin<0.5 and p'win>0.5.