Parrondo's Paradox

Until a couple of years ago, if someone had asked me if it was possible to somehow combine two games with negative expectations into a game with a positive expectation, I would have told them it wasn't possible. If asked why I would probably have said something inane like it seems clear that it is counter intuitive. And I would have been wrong. Sorry ladies but intuition is a fickle friend.

Juan Parrondo, a physicist at the Universidad Complutense de Madrid, is responsible for the following principle know as Parrando's Principle: Two games, each with a negative expectation, can be combined via deterministic or nondeterministic mixing of the games to produce a game with a positive expectation. Parrando's work was first revealed in a paper published by Gregory Harmer and Derek Abbot in 1999 in the journal Statistical Science.

Since that time there have been many examples of Parrando's Principle in action, many involving Markov chains, and most would not be appropriate for this article. Note, however, that it just takes one example to establish the principle and there is a dandy one due to R. D. Astumian that was published in Scientific American in 2001. The example is fine for this article because it is simple and it is quite dramatic.

An Astumian game is probabilistic in nature and is played on a board that looks like the following:

The play begins with a player's marker on the Start position and then moves either right or left according to fixed probabilities. Notice that if the player makes two moves then he either ends up on the Lose, the Start, or the Win positions. If we let r be the probability of moving left from the start position then 1 - r is the probability of moving right. If s is the probability of moving left from the Left position to the Lose position then 1- s is the probability of moving right back to the Start position. Finally, if t is the probability of moving right from the right position to the Win position then 1- t is the probability of moving left to the Start position. Hence the triple (r, s, t) completely defines an Astumian game.

Consider now two games A and B determined respectively by the triples (1, p, 1) and (p, p, 0). Let us suppose that the payoff in these games is even money though, as you'll see, this is really a convenience so that we can talk about expected return but in reality no one in their right mind would ever play either of these games. Why? In game A the first move will be to the left with certainty then the next move will be to the Lose position or back to Start. If Start then the process just repeats itself. It is impossible to get to the Win position. Game B is the same. If you get to the Right position then the next move moves you back to Start with probability 1. You can't win but you certainly can lose. As we'll see below both these games have an expected return of -1.

Next consider the following combined game. A coin is flipped and if heads occurs the first move in the game uses game A; otherwise game B is used. For the second move the coin is flipped again and the second move uses either game A or B according to heads or tails respectively. That's it! There are four possible game patterns: AA, AB, BA, or BB. Let me show you what the probabilities look like for the BA pattern.

In the BA pattern the first move is either to the right position with probability 1 - p or to the left with probability with probability p. In the case you are in the right position then the A game moves you to the win space with probability 1. Under this scenario you end up on the Win spot with probability 1 - p. If your first move was to the Left position then your next move will be to the Lose position with probability p or to the Start position with probability 1 - p. Thus from the Start position you either move to Lose with probability p2 or back to Start with probability p(1 - p).

A similar analysis of the other three game patterns produces the following probability chart for two moves in each pattern (which, it turns out, is all we will need).

Each of the game types occur with probability ¼ (two flips of a coin) so if we divide each of the sums in the above table by 4 we have the following probabilities

P(Lose) = (2p2 + 2p)/4

P(Start) = (1 - p)(3 + 2p)/4

P(Win) = (1 - p)/4

Okay, were ready to look at expected values. Notice in Figure 2 that the game type AA and BB are essentially the games A and B. Let's look at game A. If E is the expected return to the player at the start of the game then if the player returns to the Start after two steps the expected return will still be E. Hence we have the relation

E = -p + (1 - p)E

since a move to the Loss position (expected return -1) occurs with probability p and a move back to Start position (expected return E) occurs with probability 1 - p. As long as p is not zero the above equation can be solved and the solution is E = - 1 as expected. Note that one can make p as small as one wishes and, although it might affect the duration of the game, the expected return will still be - 1.

Now let us calculate the expected return for the combined game. Using the probabilities listed above we have

E = - P(Lost) +P(start)E +P(Win)

or

E = - p(1 - p)/4 + [(1 - p)(3 + 2p)/4]E + (1 - p)/4

Solving this last expression for E we obtain

E = (1 - 3p - 2p2)/(1 - p + 2p2)

Notice that by making p very small we can make both the numerator and the denominator of the above fraction very close to 1 and hence E very close to 1. So our combined game has a positive expectation and moreover can be made close to a certain win.

If you would like to learn more about Parrando's Principle I suggest the book Optimal Play: Mathematical Studies of Games and Gambling edited by Stewart Ethier and William Eadington and published by the Institute for the Study of Gambling and Commercial Gaming at the University of Nevada, Reno. See you next month.

Don Catlin can be reached at 711cat@comcast.net