Parrondo’s Paradox

Two losing games can combine into a winning game.

by Dan Velleman and Stan Wagon

. Introduction

In a recent issue of Nature, Abbott and Harmer [Harmer and Abbott 1999] present the quite surprising ideas of a paradox basically due to physicist Juan Parrondo. Consider three biased coins (Subscript[c, i]), where (Subscript[c, 1]) comes up heads with probability 0.495, (Subscript[c, 2]) comes up heads with probability 0.095, and (Subscript[c, 3]) is heads with probability 0.745. We shall consider heads to be a win (and a gain of $1) and tails to be a loss (of $1). Now define two games A and B. A is simply the game based on (Subscript[c, 1]), obviously a losing game with expected return of -0.01. Game B is slightly more complicated: if the current value of the player’s capital is divisible by 3, game B uses coin (Subscript[c, 2]); otherwise it uses (Subscript[c, 3]). It takes a little algebra to work out the details (see section 3), but game B is also a losing game, with expected return -0.0087.
Now comes the surprising part: If we let R denote the game where a fair coin is used to determine, randomly, which of A and B to play, then R is a winning game. It is this highly counterintuitive situation — that two losing games, when combined in a random fashion, can yield a winning game — that leads to the use of “paradox” to describe these observations. Winning games also result from certain periodic combinations, such as AABB AABB AABB…, or ABABB ABABB ABABB… .
We will focus on the probabilities just given, though one can change these in several ways. For example, the behavior is the same if 0.745 is changed to 0.75.

. Simulations

It is a simple matter to program some simulations of these games. We represent a game as a triple giving the probabilities of winning when the capital is congruent to 0, 1, and 2 (mod 3).  In game A the probabilities in all three cases are the same, and in game B there is one probability when the capital is congruent to 0 (mod 3), and another when it is 1 or 2 (mod 3):

A[p_] := {p, p, p};
B[p_, q_] := {p, q, q};

We'll use a and b for the probability triples of the A and B games that produce the paradox.

a = A[0.495];
b = B[0.095, 0.745];

Next we define a function that can simulate a large number of trials of, say, 100 plays of any of these games. It is best to use a compiled function to do this, as that gives the speed necessary for thousands, or even millions, of trials. The code that follows defines a function that accepts as its arguments

• the game, which is to be a finite list of probability triples and which is to be played periodically;
• n, the number of games to be played, where a game refers to a single coin-toss; and
• trials, the number of trials that will be used to obtain an average return.

Note that Module, Do, NestList, Mod, and Random all work inside compiled functions. The approach that follows starts out with a vector of n + 1 0s, and then runs several trials of the game updating the appropriate position in the vector after each trial. Dividing by the number of trials gives the empirical expected capital after k plays, as k goes from 0 to n.

ParrondoSimulation = 
        Compile[{{game, _Real, 2}, n, 
            trials}, 
Module[{v = Table[0, {n + 1}], 
              i}, 
Do[
              i = 0; 
     v += 
                NestList[(i = Mod[i, Length[game]] + 1; # + 
                        If[Random[] < 
                            game[[i, 
                              Mod[#, 3] + 1]], 
                          1, -1]) &, 0, 
                  n], 
   {trials}]; 
(v/trials)]];

Here is the result of 10,000 trials of 10 rounds of game B. This takes about a second on a PowerMac 9600, not bad considering that 100,000 random numbers are computed and processed.

ParrondoSimulation[{b}, 10, 10000] // Timing

Figure  shows graphically the results of 100 plays of the games AABB and BBABA along with A and B by themselves, and also the random-choice game R. Note that the probabilities for R are just the averages of the probabilities for A and B.

Needs["Graphics`MultipleListPlot`"]

r = (1/2) (a + b);

n = 100;  trials  =  10000;
AddXVals[d_]  :=  
        Transpose[{Range[0, Length[d] - 1],  d}];

MultipleListPlot [AddXVals[
              ParrondoSimulation[#, n, 
                trials]] &  /@  {
{a, a, b, b},  {b, 
              b, a, b, 
              a}, {r},  {a},  {b}}, 
SymbolShape -> 
          None,  PlotJoined -> 
          True,  
PlotStyle -> {{}, {}, 
            Dashing[{0.0008,  0.006}] , {}, {}}, 
        Frame -> True];

. Theoretical Analysis

In analyzing these games it is helpful to think of each game as determining a 3-state Markov process, where the states represent the mod-3 congruence classes of the capital. The transition matrix of this Markov process is the 3×3 matrix whose (i,j) entry is the probability, when in state i, that the state will be j after the next coin flip. Since the capital always goes up or down by 1 on each flip, the state always changes on each flip, and therefore the diagonal entries of the matrix are all 0.

transition[
          g_] := {
{     0         ,      g[[1]]    ,  
            1 - g[[1]]}, 
{1 - 
              g[[2]],      0           ,     g[[2]]    }, 
{    g[[3]]   ,   1 - 
              g[[3]],        0        }  };

For example, in game A with head-probability p, one goes from 0 to 1, or 1 to 2, or 2 to 0 with probability p, and takes the other three steps with probability 1 - p.

transition[A[p]] // MatrixForm

Game B with probabilities p (for 0 mod 3) and q otherwise is similar.

transition[B[p, q]] // MatrixForm

We can use the transition matrix of a game, together with some matrix algebra, to compute the probabilities of various outcomes in the game, and our expected gain or loss.  If M is the transition matrix for a game, and v=((Subscript[p, 0]), (Subscript[p, 1]), (Subscript[p, 2])) is a vector giving probabilities of being in each of the states before playing the game, then v.M is the vector of probabilities after playing the game. Thus, if we play the game repeatedly, then v.(M^n) is the probability vector after n plays. If we start with a capital of 0, then our initial probability vector is (1, 0, 0), so the probability vector after n plays will be (1, 0, 0) . (M^n).
In a game in which we win $1 with probability p and lose $1 with probability 1 - p, our expected gain in dollars is p - (1 - p) = 2  p - 1. It follows that if v is the vector of probabilities of being in each of the states before playing a game, and the probabilities of winning when the capital is congruent to 0, 1 and 2 (mod 3) are p, q, and r respectively, then the expected gain is v.(2  p - 1, 2  q - 1, 2  r - 1).
Putting this all together, we can compute the expected outcome of n plays, using a sequence game of probability triples periodically. In other words, we can compute the expected value of ParrondoSimulation[game, n, trials]. For large values of trials, this should match the output of ParrondoSimulation closely.

payoff[g_] := 2 g - 1;
ParrondoExpected[game_, n_] := 
        Module[
{freq = {1, 0, 0}, capital = 0, 
            capitalList = Table[0, {n + 1}], pos = 0, len = Length[game], 
            pay = payoff /@ game, 
            trans = transition /@ game}, 
Do[
            pos = Mod[pos, len] + 1; 
capital += 
              freq . pay[[
                  pos]]; 
capitalList[[i]] = capital; 
            freq = freq . 
                trans[[pos]], {i, 2, 
              n + 1}]; 
capitalList];

Here are examples showing that these theoretical calculations match the results of our earlier simulations:

ParrondoExpected[{b}, 10]

MultipleListPlot[AddXVals[
              ParrondoExpected[#, 100]] &  /@  {
{a, a, 
              b, b},  {b, b, a, b, 
              a}, {r},  {a},  {b}}, 
SymbolShape -> 
          None,  PlotJoined -> 
          True,  
PlotStyle -> {{}, {}, 
            Dashing[{0.0008,  0.006}] , {}, {}}, 
        Frame -> True];

The key step in understanding the long-term behavior of these games is understanding the amount of time one stays in the different mod-3 states during a long run of the game. As we saw earlier, the vector of probabilities of being in each of the three states after n plays of the game will be (1, 0, 0) . (M^n), so to study the long-term behavior we can look at (1, 0, 0) . (M^n) for large values of n. For example, for the game A, the state has nothing to do with the result of the game, and so one would expect that the long-term frequencies for the three states would each be (1/3).

{1, 0, 0} . MatrixPower[transition[a], 100]

On the other hand, it turns out that after a large number of plays of game B, our capital is much more likely to be congruent to 2 (mod 3) than 1 (mod 3):

{1, 0, 0} . MatrixPower[transition[b], 100]

To get the exact values, we use a theoretical result about Markov processes (see [Grinstead and Snell, 1997, thm. 11.9]) that says that (lim_(n -> ∞))(1, 0, 0) . 
          (M^n) is the unique probability vector v such that v.M=v. In other words, v=((Subscript[p, 0]), (Subscript[p, 1]), (Subscript[p, 2])) is the unique solution to the system of equations ((M^T) - I).v = 0 and (Subscript[p, 0]) + (Subscript[p, 1]) + (Subscript[p, 2]) = 1. (In more technical language, v is an eigenvector for the matrix (M^T) associated with the eigenvalue 1.) This is a system of four equations with three unkowns, but one of the equations is redundant: since each row of M sums to 1, each column of (M^T) - I sums to 0, and therefore each row of (M^T) - I is just the negative of the sum of the other two. Thus we can drop any of these rows to get a system of three equations with three unknowns that can be solved to find the long-term frequencies:

longterm[M_] := 
        LinearSolve[
          ReplacePart[Transpose[M] - IdentityMatrix[3], {1, 1, 1}, 3], {0, 0, 
            1}];

longterm[transition[a]]

longterm[transition[b]]

longterm[transition[b]] . payoff[b]

This last calculation shows that, in the long run, we lose about 0.87¢ per game if we play B repeatedly .
A sequence of games played periodically can also be treated as a Markov process whose transition matrix is the product of the transition matrices of the individual games:

longterm[Dot @@ transition /@ {b, b, a, b, a}]

This indicates that, if we play the sequence of games BBABA repeatedly, then in the long run, at the beginning of each cycle of BBABA, it is more likely that our capital will be congruent to 1 (mod 3) than either 0 or 2. This may help to explain why we do so well when playing this game: if our capital is congruent to 1 (mod 3) at the beginning of a cycle, then we have a good chance of winning both of the first two B games, since in game B we usually win unless our capital is congruent to 0 (mod 3). For a more detailed analysis of what happens throughout the cycle, we define the following function:

ParrondoAnalyze[game_] := 
        Module[{trans = transition /@ game, freq, freqList, valueList}, 
          freq = longterm[
              Dot @@ trans]; 
valueList = freqList = 
              Table[0, {Length[game]}]; 
          Do[freqList[[i]] = 
              freq; 
valueList[[
                i]] = 
              freq . payoff[game[[i]]]; 
            freq = freq . 
                trans[[i]], {i, 
              Length[game]}]; {freqList, valueList, 
            Plus @@ (valueList/Length)[game]}];

ParrondoAnalyze[{b, b, a, b, a}]

As we have already seen, the first triple of numbers in this output gives the long-term frequencies for the three states at the beginning of the cycle. The next four triples are the long-term frequencies before the second, third, fourth, and fifth games of the cycle. The next list of numbers is the expected gain on each coin flip in the cycle. Of course, we expect to lose a penny every time we play game A, regardless of what our capital is, but on average we gain money each time we play B. We do especially well when we play B on the fourth step of each cycle, since our probability of having a capital that is congruent to 0 (mod 3) at this point is only a bit over (1/4). The last number in the output is the long-term expected gain per coin flip; we can expect to earn more than 6.5¢ per flip when we play BBABA repeatedly!

The Parrondo package in the electronic supplement includes several of the functions that we have already defined, and also ParrondoValue, which gives just the per-play value of a game.

ParrondoValue[{b, b, a, b, a}]

These calculations can be done not only numerically, but also symbolically. Here is the analysis of any game of type B, with arbitrary probabilities p and q:

AnalyzeB = ParrondoAnalyze[{B[p, q]}]

The last entry in this list is the expected gain per coin flip:

ValueB = Last[AnalyzeB]

An immediate application of this formula is to get the fair p-value for a given q:

Solve[ValueB == 0, p]

FairB[q_]  :=  ((1 - 2 q + (q^2))/(1 - 2 q + 2 (q^2)))

In particular, when q = (3/4), the fair p-value is (1/10). This explains how the probabilities 0.745 and 0.095 were chosen.

FairB[(3/4)]

The fairness function gives us a slick way to understand why the random game R outperforms A and B. Figure  shows a plot of the fairness function, with the horizontal axis being q and the vertical axis p. This means that if (p, q) is underneath the graph, then the game B[p, q] is a losing game, while points above the graph lead to a winning game. The convexity change at (1/2) allows the paradox to work, since the line segment that joins the two losing games (games A and B) has its midpoint (game R) above the curve.

Finally, here is a cute example: the game ABBB.

ParrondoAnalyze[{a, b, b, b}]

Note that on the third step of each cycle, one gains on average more than 15¢. Then on the fourth step, one loses more than 17¢. But this is just the long-term behavior; it takes a while for this pattern to emerge:

ListPlot[AddXVals[ParrondoExpected[{a, b, b, b}, 40]], 
        PlotJoined -> 
          True];

ListPlot[AddXVals[ParrondoExpected[{a, b, b, b}, 300]], 
        PlotJoined -> True];

. The Best Games

For ease of interpretation, we assume that some games (i.e., their probability triples) have been stored in symbols, just as we have used a, b, and r in the preceding sections. Then the ParrondoSortAll function from the Parrondo package sorts all possible fixed-length strings in the names according to their asymptotic per-game expected value when played forever (or for a fixed number of times). The following example shows that, for period 4, the best game when using A, B, and R is RRRR.

Needs["Parrondo`"]

Short[ParrondoSortAll[{"a", "b", "r"}, 4], 3]

But for the period-5 case, the best long-term game is ABBAB (whose value is the same as the rotated versions BBABA, BABAB, etc.)

Take[
      ParrondoSortAll[{"a", "b", "r"}, 5], -6]

However, for plays of 100 games, there is a unique best period-5 choice, and that is ABABB.

Take[
      ParrondoSortAll[{"a", "b", "r"}, 5, 
        100], -6]

We think that ABABB (or any of its rotations) may be the absolutely best game for the infinite play, no matter what the period. Searches up to period-length 12 have found nothing that pays off as highly as this one, with its handsome return of 6.52¢ per game.

Here is how the sorting routines were implemented. We first define a basic sorting function that sorts pairs according to their Parrondo value, where the first entry in a pair is a sequence of triples and the second is a string-name for the triple.

\(ParrondoSort[{\ {{a, b, a, 
            b}, "abab"}, \ 
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ {{a, b, b, 
            b}, "abbb"}, 
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ {{b, a, b, a}, "baba"}}, 10]\)

Here is the definition.

ParrondoSort[x_List, gamelength_ : ∞] := 
      Reverse /@ 
        Sort[{ParrondoValue[#[[1]], 
                  gamelength], #[[2]]} & /@ x]

To search all possibilities, we require that the games have string-names, such as "a". We first get all possible strings, and then use ParrondoSort. This can be cleanly done with Distribute as follows.

Distribute[Table[{"a", "b"}, {2}], List]

This should be read as Distribute[List[{"a", "b"}, {"a", "b"}, List]], which causes the first List to be be distributed over other Lists. Since the List is implicit in the output of Table, this actual code is quite short. In the following definition of ParrondoSortAll, ToExpression is used to turn each name into its matrix. This gives all possible games, and then ParrondoSort does the sorting.

ParrondoSortAll[names_, len_Integer, gamelength_ : ∞] := 
      ParrondoSort[
({#[[1]], 
                  StringJoin @@ #[[2]]} &) /@ Transpose /@ 
Distribute[
  Table[{ToExpression[#], #} & /@ names, {len}], List], 
          gamelength]        /; And @@ StringQ /@ names

References

[Harmer and Abbot 1999] G. P. Harmer and D. Abbott, Losing strategies can win by Parrondo’s paradox, Nature 402, Dec. 23 1999, 864.

[Grinstead and Snell 1997] C. Grinstead and J. L.Snell, Introduction to Probability, 2nd ed., American Mathematical Society, Providence, 1997.

About the Authors

Dan Velleman's interests include logic, philosophy of mathematics, and foundations of quantum mechanics. He is the author of How To Prove It (Cambridge Univ. Pr.) and coauthor of Which Way Did the Bicycle Go? (MAA). He is the editor of the Dolciani Mathematical Expositions and a member of the editorial board of the American Mathematical Monthly.

Dan Velleman
Department of Mathematics and Computer Science
Amherst College
Amherst, MA 01002
djvelleman@amherst.edu

Stan Wagon uses Mathematica extensively in his research, teaching, and exposition, and is especially appreciative of the new ways Mathematica allows us to look at mathematical objects. He is author or coauthor of several books, including Animating Calculus, VisualDSolve, Which Way Did the Bicycle Go?, the just-released and much expanded second edition of Mathematica in Action, and the recently released A Course in Computational Number Theory. He teaches a high-altitude course, Rocky Mountain Mathematica, every summer in the mountains of Colorado, and has used Mathematica to help design geometric entries in snow sculpture contests.

Stan Wagon
Department of Mathematics and Computer Science
Macalester College
St. Paul, MN 55105
wagon@macalester.edu

Electronic Subscriptions

Included in the distribution for each electronic subscription is the file Wagon93.nb containing Mathematica code for the material described in this article.

Parrondo package (for electronic file)

Off[General::spell];

If[Flatten[Names /@ 
   {"ParrondoSimulation", "ParrondoValue","A", "B",
    "ParrondoSort", "ParrondoSortAll", "ParrondoAnalyze",
    "ParrondoExpected"}]!= {}, 
   Remove /@ Flatten[Names /@ {"ParrondoSimulation", "ParrondoValue","A", "B",
    "ParrondoSort", "ParrondoSortAll", "ParrondoAnalyze",
    "ParrondoExpected"}]];
BeginPackage["Parrondo`"];

ParrondoSimulation::usage = "ParrondoSimulation[game, n, t, s:0] returns the average result of t simulations over a game of length n for the Parrondo game using, periodically, the probability triples in game. Each of these triples specifies the probabilities of winning in the three cases of the capital being 0, 1, and 2 (mod 3). The starting value of the capital is s."; 

ParrondoValue::usage = "ParrondoValue[game, n:∞, s:0] gives the expected per-game return for a run of n games (n can be ∞), with starting capital s, where the games are given by game, played periodically. game is to be a list of probability triples."; 

FairB::usage = "FairB[q] gives the unique value of p so that the expected return of the game B[p, q] is 0.";

A::usage = "A[p] gives the probability triple for the game played on a coin with probability p of winning."; 

B::usage = "B[p, q, res:0] gives the probability triple for the game played on a coin with probability p of winning when the capital is congruent to res (mod 3), and with probability q of winning when the capital is not res (mod 3)."; 

R::usage = "R[p, q, r, {res, s}:{0, 0.5}] gives the probability triple for the game in which, for each coin flip, one chooses randomly whether to play A[p] or B[q, r, res], choosing the first with probability s."; 

ParrondoSort::usage = "ParrondoSort[games, names, len:∞] sorts the periodic games in the family games along with their Parrondo values at length len. It is assumed that each game has a name and all the names that occur are listed in names.";

ParrondoSortAll::usage = "ParrondoSortAll[names, len, gamelength:∞] sorts all possible games of length len according to their per-game expected value over gamelength games, where names is the set of string-names of the basic probability triples.";

ParrondoAnalyze::usage = "ParrondoAnalyze[game] analyzes the long-term behavior of the Parrondo game using, periodically, the probability triples in game. It produces a list of three outputs. The first output is a list giving, for each entry in game, the fraction of the time that the capital will be 0, 1, or 2 (mod 3) when that game is played. The next output is a list giving, for each entry in game, the expected gain or loss when that game is played. The last output is the average of the values in the previous list, which is the expected per-game gain or loss overall.";

ParrondoExpected::usage = "ParrondoExpected[game, n, s:0] gives a list of the expected capital at each step for a run of n games, with starting capital s, where the games are given by game, played periodically. In other words, it is the expected value of ParrondoSimulation[game, n, t, s].";

Begin["`Private`"];

FairB[q_] :=(1 - 2 q + q^2)/(1 - 2 q + 2 q^2);

ParrondoSimulation[game_/; TensorRank[game]==2, n_Integer, trials_Integer, s_Integer:0] := 
  ParrondoSimulationC[game, n, trials, s];

ParrondoSimulationC = Compile[{{game, _Real, 2}, n, trials, {s, _Integer}}, 
     Module[{v = Table[0, {n + 1}], i}, 
       Do[i = 0; v += NestList[(i = Mod[i, Length[game]] + 1;
         #1 + If[Random[] < game[[i, Mod[#1, 3] + 1]], 1, -1]) & , s, n], 
         {trials}];
       v/trials]];

A[p_] := {p, p, p}; 

B[p_, q_, res_:0] := ReplacePart[{q, q, q}, p, Mod[res, 3] + 1];

R[p_, q_, r_, params_List:{0, 0.5}] := 
  params[[2]]*A[p] + (1 - params[[2]])*B[q, r, params[[1]]];

payoff[g_] := 2*g - 1;

transition[g_] := {{0, g[[1]], 1 - g[[1]]},
	{1 - g[[2]], 0, g[[2]]}, {g[[3]], 1 - g[[3]], 0}};

longterm[M_] := LinearSolve[
	ReplacePart[Transpose[M] - IdentityMatrix[3], {1, 1, 1}, 3], {0, 0, 1}];

ParrondoAnalyze[game_] :=
    Module[{trans = transition /@ game, freq, freqlist, valuelist},
      freq = longterm[Dot @@ trans];
      valuelist = freqlist = Table[0, {Length[game]}]; 
      Do[freqlist[[i]] = freq; valuelist[[i]] = freq.payoff[game[[i]]]; 
        freq = freq.trans[[i]], {i, Length[game]}]; {freqlist, valuelist,
        (Plus @@ valuelist)/Length[game]}];
        
ParrondoExpected[game_, n_, s_:0] :=
    Module[{freq = {0, 0, 0}, capital = s, capitallist = Table[0, {n + 1}],
        pos = 0, len = Length[game], pay = payoff /@ game,
        trans = transition /@ game},
      freq[[Mod[s, 3] + 1]] = 1;
      capitallist[[1]] = capital;
      Do[pos = Mod[pos, len] + 1;
        capital += freq.pay[[pos]]; capitallist[[i]] = capital; 
        freq = freq.trans[[pos]], {i, 2, n + 1}]; capitallist];
        
ParrondoValue[game_, n_:Infinity, s_:0] :=
	Module[{freq, winnings = 0, pos = 0, len = Length[game], steps,
		pay = payoff /@ game, trans = transition /@ game},
	If[n==Infinity, freq = longterm[Dot @@ trans]; steps = len,
		freq = {0, 0, 0}; freq[[Mod[s, 3] + 1]] = 1; steps = n];
	Do[pos = Mod[pos, len] + 1;
		winnings += freq.pay[[pos]];
		freq = freq.trans[[pos]],
		{steps}];
	winnings/steps];
	
	Clear[ParrondoSort, ParrondoSortAll];
	
ParrondoSort[x_List, gamelength_:Infinity]:=
Map[Reverse, Sort[{ParrondoValue[#[[1]], gamelength], #[[2]]}& /@ x]]

ParrondoSortAll[names_, len_Integer, gamelength_:Infinity]:=
ParrondoSort[{#[[1]], StringJoin @@ #[[2]]}& /@ Transpose /@
Distribute[Table[({ToExpression[#], #}& /@ names), {len}], List], gamelength] /; And @@ StringQ /@ names

End[]; 
EndPackage[];

Electronic Subscriptions