Two losing games with a memory

Two losing games that win together computed Juan Parrondo’s games exactly and found the paradox lived in a three-state chain: game B tossed a bad coin when the capital was a multiple of three and a good one otherwise, the capital rattled between a multiple of three and the value below it, and the bad coin was played too often. Game A, an ordinary coin with a slight disadvantage, broke the rattle by moving the capital at random, and the mixture won. That essay ended by noting that the effect depended on the capital’s remainder — on where the walk stood — and that Parrondo, Gregory Harmer and Derek Abbott had published a second version in 2000 whose game B looks at something else, with “conditions of its own”.

This essay computes that second version, and the reason it matters is that it removes the thing the first seemed to need. The new game B never looks at the capital. Its coin depends only on whether the last two rounds were won or lost. The walk of the capital therefore treats every position exactly alike — it is translation invariant, as a walk in a walk that follows its own footsteps was — and nothing about the paradox can come from a sawtooth in the capital, because there is none. The paradox survives anyway.

A game that remembers two results #

Game A is a coin winning with probability $\tfrac12 - \varepsilon$. Game B looks at the results of the two previous rounds, whichever game was played in them, and tosses one of three coins:

• after two losses, a coin winning with probability $\tfrac{9}{10} - \varepsilon$;
• after a loss and a win, in either order, a coin winning with probability $\tfrac14 - \varepsilon$;
• after two wins, a coin winning with probability $\tfrac{7}{10} - \varepsilon$.

Parrondo, Harmer and Abbott used $\varepsilon = 0.003$, and so does every figure here. The hero follows the expected capital from nought over 300 rounds. Game A loses $0.006$ a round, $1.80$ in all. Game B loses a little faster, $1.94$ over the 300 rounds. A fair coin choosing between A and B each round gains $1.74$, and the fixed cycle A, B, B gains $1.91$. The expected capital is computed exactly, not simulated: what game B needs to know — the last two results — is a pair of letters, four possible states, and the chance of being in each state after any sequence of rounds follows from multiplying four-by-four matrices.

The state is not the capital. In the first version the remainder of the capital on division by three was the state, and it was a property of where the walk stood. Here the state is a property of the walk’s recent history, and two players at different capitals with the same last two results are in exactly the same situation. That is the precise sense in which the walk treats every position alike: shifting the whole capital by any amount changes nothing about the future.

Fair by a balance of pairs #

As for the capital games, a naive average says game B should win: two of its three coins are good, and a loss-loss or win-win pair is followed by a winning coin. It is the frequencies of the pairs that decide. Played alone with no handicap, game B’s chain of pairs settles into the long-run shares

$$\pi_{LL} = \tfrac{5}{22}, \qquad \pi_{LW} = \pi_{WL} = \tfrac{6}{22}, \qquad \pi_{WW} = \tfrac{5}{22},$$

which the figure prints as 22.73%, 27.27%, 27.27% and 22.73%. The bad coin, after mixed pairs, is used in twelve rounds of every twenty-two, more than half the time, and the long-run chance of winning a round is

$$\tfrac{5}{22} \cdot 0.9 + \tfrac{12}{22} \cdot 0.25 + \tfrac{5}{22} \cdot 0.7 = \tfrac{4.5 + 3 + 3.5}{22} = \tfrac12$$

exactly. Game B without a handicap is perfectly fair, and the fairness is a balance between the good coins and how often the bad one comes round.

The mechanism of the balance is easy to see. The good coin after two losses usually wins, producing the pair loss-win, which calls the bad coin; the bad coin usually loses, producing win-loss, which calls the bad coin again; and that usually loses too, returning to two losses. So the typical cycle is two losses, a win, a loss, a loss — and two of every three rounds in it are played on the bad coin. Game B, left to itself, keeps leading the player back into the state where it plays badly. With the handicap of $0.003$ the balance tips and B loses $0.0066$ a round.

Mixing in A changes the shares. A’s coin is independent of the past, so it produces runs of equal results as often as mixed ones, and with A played half the time the share of rounds following a mixed pair falls from 27.36% to 26.15% for each kind while the shares following loss-loss and win-win rise. The bad coin is used less, B’s good coins more, and the mixture gains $0.0058$ a round although A, every time it is played, loses. Exactly as in the capital games, A wins nothing itself; it changes where B’s rounds are played, and the “where” is now a place in the history rather than in the capital.

How small a handicap, how much of A #

The paradox is not a knife-edge here either, though its margin is narrower. At $\varepsilon = 0$ games A and B are both fair and the mixture gains $0.0117$ a round. As $\varepsilon$ grows the three gains fall almost in parallel, and the mixture keeps winning while both games lose until $\varepsilon$ reaches $0.0060$. The capital games allowed a handicap of $0.0131$ before the mixture stopped winning; the memory games allow less than half of that. Removing the dependence on position has narrowed the effect without destroying it.

The proportion of A matters in the same way. Playing A with probability $\gamma$ and B otherwise gives a gain that is a smooth hump: negative at $\gamma = 0$, where only B is played, and at $\gamma = 1$, where only A is, and positive for every $\gamma$ from 0.155 to 0.855, with its best, $+0.0058$, at $\gamma = 0.505$. The hump is more symmetric than for the capital games, where the best mixture played A only 41% of the time. There, a little A was enough to break the rattle; here, A’s influence works through the two-round memory, and both ingredients are needed in about equal measure — A to break the runs of mixed pairs, B to exploit the runs of equal ones.

Where in the plane of coins #

How special are the published coins? The figure varies the two good coins over the whole square — the chance of winning after two losses across, after two wins up — and keeps the bad coin at a quarter. In the pale corner game B wins on its own, because the good coins are good enough to outweigh the bad one however often it comes round. In the unshaded remainder of the square everything loses. Between them, along the edge of the pale region, lies a thin red band in which B loses on its own and the mixture wins: 0.6% of the square, and the published coins, 0.9 and 0.7, are inside it.

The band is narrow because of what the paradox needs. For the mixture to win while B loses, B must be very nearly fair on its own — close to the curve where its good and bad coins balance — and A must tip the balance by changing the frequencies of the pairs. A game B that loses badly cannot be rescued by A, because A’s effect on the frequencies is small; a game B that wins needs no rescue. The paradox is a property of games poised near fairness, and the band is where they are poised.

Fixed rhythms #

A fixed rhythm of plays works too, and here the comparison with the capital games is sharpest. For each plan of $a$ plays of A followed by $b$ plays of B, repeated, the chain of pairs settles into a distribution that repeats with the plan, and the figure computes the gain per round from it. Fifteen of the sixteen plans win. The best is plain alternation, A B, at $+0.0172$ a round, three times the best random mixture. The gain falls steadily as either game is played longer in a block, and only AAAABBB, four of A then three of B, loses.

In the capital games, plain alternation lost, and the table of rhythms was irregular, because what mattered was how the plan’s period meshed with the capital’s period of three. Here B’s memory is two rounds, and the plan A B puts the result of one independent coin directly in front of every play of B: half of each pair B sees is a fresh, unbiased result, which is exactly what breaks B’s habit of cycling through the mixed pairs. Longer blocks of B let the habit return; longer blocks of A spend more rounds on A’s losing coin. The regularity of this table and the irregularity of the other are one fact seen twice: the best rhythm is the one that lines up with the structure of B’s memory.

What the memory games show about the paradox #

The two versions together isolate what the paradox is. It is not about money being made from nothing, and it is not about the shape of a potential, which is how Parrondo first thought of it — as a discrete version of a flashing ratchet, a particle in a sawtooth potential switched on and off. The capital games are a ratchet; the memory games are not, and they show the same effect. What both have is a game B whose gain depends on a state, and whose own dynamics drive that state towards the part where B plays badly. A second process that moves the state without regard to B’s coins — game A, a fair coin, anything independent — changes the long-run frequencies of the states, and with them B’s gain.

In the language of the time spent and the share held, B’s long-run gain is an average over its stationary distribution, and that distribution is a property of the whole rule acting on the state, not of B’s coins alone. Two rules that each have an unfavourable stationary distribution can have a combined rule with a favourable one, because stationary distributions do not combine linearly: the distribution of the mixture is not the mixture of the distributions. It is the same fact that makes a walk that samples a distribution work in reverse — there, a chain is designed so that its stationary distribution is a target; here, two chains are combined and the combination’s stationary distribution lands somewhere neither was aiming. Nor is there any reversibility to lean on: the chain that runs the same backwards balanced its flows pair by pair, but game B’s chain of pairs flows round a cycle — loss-loss to loss-win to win-loss and back to loss-loss — and the circulation is exactly what keeps it in the states where it plays badly. That is the whole of the paradox, and it holds for any state a game can depend on — a remainder of the capital, the last two results, or the last ten.

The chain of pairs mixes fast, which is why the hero’s curves become straight lines within a few rounds: how long until it forgets measured the time a chain takes to reach its stationary distribution, and a four-state chain whose transitions all have reasonable probabilities forgets its start within a handful of steps. The paradox is therefore visible quickly in expectation, and, as for the capital games, slowly in any single run, where the drift of a few thousandths per round is buried under fluctuations of order $\sqrt n$.

Why the history is not a disguised position #

It is tempting to say that the last two results are just a coarse record of the capital — two wins means the capital went up by two — and so that the memory games are the capital games in disguise. They are not, and the difference is checkable. The capital games’ state, the remainder modulo three, is a function of the current capital alone, so two players at capitals 9 and 12 face the same coins whatever their histories. The memory games’ state is a function of the last two steps alone, so two players at capitals 9 and 12 with the same last two results face the same coins, and two players at capital 9 with different histories face different ones. Neither state can be read from the other.

That is also why the memory games interact with Penney’s game in a way the capital games do not. In both, patterns of recent results — runs and alternations — carry information about what comes next, and in both the information comes from overlaps: a pair loss-win overlaps the pair win-loss, which is why one mixed pair leads so often to the other under game B, exactly as overlapping patterns made Penney’s game non-transitive. The paradox and the non-transitive dice of Penney’s game are cousins, both arising when the next step depends on a short window of the past.

An expected gain buried under its own spread #

Everything is exact: the expected capitals are sums over the four-state distribution, which is propagated round by round by matrix multiplication; the stationary shares are the limits of that propagation, checked against the exact fractions $5/22$ and $6/22$ at $\varepsilon = 0$; the gains for cycles use the distribution that repeats with the cycle. The plane of coins is computed on a grid of 120 by 120 settings, so its band’s boundaries are accurate to the grid’s spacing, and its 0.6% is a measurement of the band at that resolution.

None of this says what happens to a single player in a finite run. The gains are expectations, and the spread of the capital after $n$ rounds is about $\sqrt n$, far larger than the drift of $0.006n$ for any number of rounds a person would play; over 300 rounds the mixture’s expected gain of 1.74 is buried under a standard deviation of about 17, and half the time is the rarest answer showed how long a nearly fair walk can stay on one side of nought by chance alone. The figures also hold only for the specific games of Parrondo, Harmer and Abbott and their neighbours in the plane; for games with longer memories or more coins the band where the paradox holds is a region in a higher-dimensional space, and its size there is not computed.

Still open: a condition that can be read from the coins #

For games of either kind, whether a mixture of two losing games wins is decidable by computation — find the stationary distribution of the mixed chain and compute its gain — and the figures here do exactly that. What is missing, for the memory games as for the capital games, is a structural answer: a condition, readable directly from the coins, that says whether some mixture or some cycle wins and how large the best gain can be. For the simplest families partial conditions are known, expressed through inequalities between products of the coins that are equivalent to the stationary gain changing sign. For memories longer than two rounds, or for games mixing dependence on the capital and on the history, even the shape of the region where the paradox holds is known only by computation.

There is also a question the cycle table raises. With a two-round memory the best rhythm was plain alternation; with a capital period of three it was A B B. Is the optimal rhythm always determined, in some simple way, by the structure of B’s state — its period, its memory length — or can the optimum be irregular in general? The examples suggest a rule and nobody has stated, let alone proved, one.

A paradox that never needed a position #

A coin that wins nine times in ten after two losses, one time in four after mixed results and seven times in ten after two wins is exactly fair on its own, because it keeps leading the player back to mixed results; handicapped by three thousandths it loses, and so does a coin of $0.497$ — and played at random together they win, $0.0058$ a round. Nothing in either game looks at the capital, so the walk treats every position alike: the paradox lives in the frequencies of the last two results, which game A tilts towards the runs where B plays well. It holds only in a thin band of coins poised near fairness, it survives a handicap less than half as large as the capital games allowed, and its best rhythm is plain alternation, which in the capital games lost.