Parrondo's paradox

Last updated

Parrondo's paradox, a paradox in game theory, has been described as: A combination of losing strategies becomes a winning strategy. [1] It is named after its creator, Juan Parrondo, who discovered the paradox in 1996. A more explanatory description is:

Contents

There exist pairs of games, each with a higher probability of losing than winning, for which it is possible to construct a winning strategy by playing the games alternately.

Parrondo devised the paradox in connection with his analysis of the Brownian ratchet, a thought experiment about a machine that can purportedly extract energy from random heat motions popularized by physicist Richard Feynman. However, the paradox disappears when rigorously analyzed. [2] Winning strategies consisting of various combinations of losing strategies were explored in biology before Parrondo's paradox was published. [3]

Illustrative examples

The simple example

Consider two games Game A and Game B, with the following rules:

  1. In Game A, you lose $1 every time you play.
  2. In Game B, you count how much money you have left ⁠ ⁠—  if it is an even number you win $3, otherwise you lose $5.

Say you begin with $100 in your pocket. If you start playing Game A exclusively, you will obviously lose all your money in 100 rounds. Similarly, if you decide to play Game B exclusively, you will also lose all your money in 100 rounds.

However, consider playing the games alternatively, starting with Game B, followed by A, then by B, and so on (BABABA...). It should be easy to see that you will steadily earn a total of $2 for every two games.

Thus, even though each game is a losing proposition if played alone, because the results of Game B are affected by Game A, the sequence in which the games are played can affect how often Game B earns you money, and subsequently the result is different from the case where either game is played by itself.

The saw-tooth example

Figure 1 Parrandos Paradox Unbiased Games.PNG
Figure 1

Consider an example in which there are two points A and B having the same altitude, as shown in Figure 1. In the first case, we have a flat profile connecting them. Here, if we leave some round marbles in the middle that move back and forth in a random fashion, they will roll around randomly but towards both ends with an equal probability. Now consider the second case where we have a saw-tooth-like profile between the two points. Here also, the marbles will roll towards either end depending on the local slope. Now if we tilt the whole profile towards the right, as shown in Figure 2, it is quite clear that both these cases will become biased towards B.

Now consider the game in which we alternate the two profiles while judiciously choosing the time between alternating from one profile to the other.

Figure 2 Parrandos Paradox Biased Games.PNG
Figure 2

When we leave a few marbles on the first profile at point E, they distribute themselves on the plane showing preferential movements towards point B. However, if we apply the second profile when some of the marbles have crossed the point C, but none have crossed point D, we will end up having most marbles back at point E (where we started from initially) but some also in the valley towards point A given sufficient time for the marbles to roll to the valley. Then we again apply the first profile and repeat the steps (points C, D and E now shifted one step to refer to the final valley closest to A). If no marbles cross point C before the first marble crosses point D, we must apply the second profile shortly before the first marble crosses point D, to start over.

It easily follows that eventually we will have marbles at point A, but none at point B. Hence if we define having marbles at point A as a win and having marbles at point B as a loss, we clearly win by alternating (at correctly chosen times) between playing two losing games.

The coin-tossing example

A third example of Parrondo's paradox is drawn from the field of gambling. Consider playing two games, Game A and Game B with the following rules. For convenience, define to be our capital at time t, immediately before we play a game.

  1. Winning a game earns us $1 and losing requires us to surrender $1. It follows that if we win at step t and if we lose at step t.
  2. In Game A, we toss a biased coin, Coin 1, with probability of winning , where is some small positive constant. This is clearly a losing game in the long run.
  3. In Game B, we first determine if our capital is a multiple of some integer . If it is, we toss a biased coin, Coin 2, with probability of winning . If it is not, we toss another biased coin, Coin 3, with probability of winning . The role of modulo provides the periodicity as in the ratchet teeth.

It is clear that by playing Game A, we will almost surely lose in the long run. Harmer and Abbott [1] show via simulation that if and Game B is an almost surely losing game as well. In fact, Game B is a Markov chain, and an analysis of its state transition matrix (again with M=3) shows that the steady state probability of using coin 2 is 0.3836, and that of using coin 3 is 0.6164. [4] As coin 2 is selected nearly 40% of the time, it has a disproportionate influence on the payoff from Game B, and results in it being a losing game.

However, when these two losing games are played in some alternating sequence - e.g. two games of A followed by two games of B (AABBAABB...), the combination of the two games is, paradoxically, a winning game. Not all alternating sequences of A and B result in winning games. For example, one game of A followed by one game of B (ABABAB...) is a losing game, while one game of A followed by two games of B (ABBABB...) is a winning game. This coin-tossing example has become the canonical illustration of Parrondo's paradox – two games, both losing when played individually, become a winning game when played in a particular alternating sequence.

Resolving the paradox

The apparent paradox has been explained using a number of sophisticated approaches, including Markov chains, [5] flashing ratchets, [6] simulated annealing, [7] and information theory. [8] One way to explain the apparent paradox is as follows:

  • While Game B is a losing game under the probability distribution that results for modulo when it is played individually ( modulo is the remainder when is divided by ), it can be a winning game under other distributions, as there is at least one state in which its expectation is positive.
  • As the distribution of outcomes of Game B depend on the player's capital, the two games cannot be independent. If they were, playing them in any sequence would lose as well.

The role of now comes into sharp focus. It serves solely to induce a dependence between Games A and B, so that a player is more likely to enter states in which Game B has a positive expectation, allowing it to overcome the losses from Game A. With this understanding, the paradox resolves itself: The individual games are losing only under a distribution that differs from that which is actually encountered when playing the compound game. In summary, Parrondo's paradox is an example of how dependence can wreak havoc with probabilistic computations made under a naive assumption of independence. A more detailed exposition of this point, along with several related examples, can be found in Philips and Feldman. [9]

Applications

Parrondo's paradox is used extensively in game theory, and its application to engineering, population dynamics, [3] financial risk, etc., are areas of active research. Parrondo's games are of little practical use such as for investing in stock markets [10] as the original games require the payoff from at least one of the interacting games to depend on the player's capital. However, the games need not be restricted to their original form and work continues in generalizing the phenomenon. Similarities to volatility pumping and the two envelopes problem [11] have been pointed out. Simple finance textbook models of security returns have been used to prove that individual investments with negative median long-term returns may be easily combined into diversified portfolios with positive median long-term returns. [12] Similarly, a model that is often used to illustrate optimal betting rules has been used to prove that splitting bets between multiple games can turn a negative median long-term return into a positive one. [13] In evolutionary biology, both bacterial random phase variation [14] and the evolution of less accurate sensors [15] have been modelled and explained in terms of the paradox. In ecology, the periodic alternation of certain organisms between nomadic and colonial behaviors has been suggested as a manifestation of the paradox. [16] There has been an interesting application in modelling multicellular survival as a consequence of the paradox [17] and some interesting discussion on the feasibility of it. [18] [19] Applications of Parrondo's paradox can also be found in reliability theory. [20]

Name

In the early literature on Parrondo's paradox, it was debated whether the word 'paradox' is an appropriate description given that the Parrondo effect can be understood in mathematical terms. The 'paradoxical' effect can be mathematically explained in terms of a convex linear combination.

However, Derek Abbott, a leading researcher on the topic, provides the following answer regarding the use of the word 'paradox' in this context:

Is Parrondo's paradox really a "paradox"? This question is sometimes asked by mathematicians, whereas physicists usually don't worry about such things. The first thing to point out is that "Parrondo's paradox" is just a name, just like the "Braess's paradox" or "Simpson's paradox." Secondly, as is the case with most of these named paradoxes they are all really apparent paradoxes. People drop the word "apparent" in these cases as it is a mouthful, and it is obvious anyway. So no one claims these are paradoxes in the strict sense. In the wide sense, a paradox is simply something that is counterintuitive. Parrondo's games certainly are counterintuitive—at least until you have intensively studied them for a few months. The truth is we still keep finding new surprising things to delight us, as we research these games. I have had one mathematician complain that the games always were obvious to him and hence we should not use the word "paradox." He is either a genius or never really understood it in the first place. In either case, it is not worth arguing with people like that. [21]

See also

Related Research Articles

Minmax is a decision rule used in artificial intelligence, decision theory, game theory, statistics, and philosophy for minimizing the possible loss for a worst case scenario. When dealing with gains, it is referred to as "maximin" – to maximize the minimum gain. Originally formulated for several-player zero-sum game theory, covering both the cases where players take alternate moves and those where they make simultaneous moves, it has also been extended to more complex games and to general decision-making in the presence of uncertainty.

The prisoner's dilemma is a game theory thought experiment that involves two rational agents, each of whom can cooperate for mutual benefit or betray their partner ("defect") for individual reward. This dilemma was originally framed by Merrill Flood and Melvin Dresher in 1950 while they worked at the RAND Corporation. Albert W. Tucker later formalized the game by structuring the rewards in terms of prison sentences and named it the "prisoner's dilemma".

In game theory, the Nash equilibrium, named after the mathematician John Nash, is the most common way to define the solution of a non-cooperative game involving two or more players. In a Nash equilibrium, each player is assumed to know the equilibrium strategies of the other players, and no one has anything to gain by changing only one's own strategy. The principle of Nash equilibrium dates back to the time of Cournot, who in 1838 applied it to competing firms choosing outputs.

In physics, the CHSH inequality can be used in the proof of Bell's theorem, which states that certain consequences of entanglement in quantum mechanics cannot be reproduced by local hidden-variable theories. Experimental verification of the inequality being violated is seen as confirmation that nature cannot be described by such theories. CHSH stands for John Clauser, Michael Horne, Abner Shimony, and Richard Holt, who described it in a much-cited paper published in 1969. They derived the CHSH inequality, which, as with John Stewart Bell's original inequality, is a constraint—on the statistical occurrence of "coincidences" in a Bell test—which is necessarily true if an underlying local hidden-variable theory exists. In practice, the inequality is routinely violated by modern experiments in quantum mechanics.

A martingale is a class of betting strategies that originated from and were popular in 18th-century France. The simplest of these strategies was designed for a game in which the gambler wins the stake if a coin comes up heads and loses if it comes up tails. The strategy had the gambler double the bet after every loss, so that the first win would recover all previous losses plus win a profit equal to the original stake. Thus the strategy is an instantiation of the St. Petersburg paradox.

<span class="mw-page-title-main">Martingale (probability theory)</span> Model in probability theory

In probability theory, a martingale is a sequence of random variables for which, at a particular time, the conditional expectation of the next value in the sequence is equal to the present value, regardless of all prior values.

<span class="mw-page-title-main">Brownian ratchet</span> Perpetual motion device

In the philosophy of thermal and statistical physics, the Brownian ratchet or Feynman–Smoluchowski ratchet is an apparent perpetual motion machine of the second kind, first analysed in 1912 as a thought experiment by Polish physicist Marian Smoluchowski. It was popularised by American Nobel laureate physicist Richard Feynman in a physics lecture at the California Institute of Technology on May 11, 1962, during his Messenger Lectures series The Character of Physical Law in Cornell University in 1964 and in his text The Feynman Lectures on Physics as an illustration of the laws of thermodynamics. The simple machine, consisting of a tiny paddle wheel and a ratchet, appears to be an example of a Maxwell's demon, able to extract mechanical work from random fluctuations (heat) in a system at thermal equilibrium, in violation of the second law of thermodynamics. Detailed analysis by Feynman and others showed why it cannot actually do this.

<span class="mw-page-title-main">St. Petersburg paradox</span> Paradox involving a game with repeated coin flipping

The St. Petersburg paradox or St. Petersburg lottery is a paradox involving the game of flipping a coin where the expected payoff of the theoretical lottery game approaches infinity but nevertheless seems to be worth only a very small amount to the participants. The St. Petersburg paradox is a situation where a naïve decision criterion that takes only the expected value into account predicts a course of action that presumably no actual person would be willing to take. Several resolutions to the paradox have been proposed, including the impossible amount of money a casino would need to continue the game indefinitely.

In game theory, the centipede game, first introduced by Robert Rosenthal in 1981, is an extensive form game in which two players take turns choosing either to take a slightly larger share of an increasing pot, or to pass the pot to the other player. The payoffs are arranged so that if one passes the pot to one's opponent and the opponent takes the pot on the next round, one receives slightly less than if one had taken the pot on this round, but after an additional switch the potential payoff will be higher. Therefore, although at each round a player has an incentive to take the pot, it would be better for them to wait. Although the traditional centipede game had a limit of 100 rounds, any game with this structure but a different number of rounds is called a centipede game.

<span class="mw-page-title-main">Two envelopes problem</span> Puzzle in logic and mathematics

The two envelopes problem, also known as the exchange paradox, is a paradox in probability theory. It is of special interest in decision theory and for the Bayesian interpretation of probability theory. It is a variant of an older problem known as the necktie paradox. The problem is typically introduced by formulating a hypothetical challenge like the following example:

Imagine you are given two identical envelopes, each containing money. One contains twice as much as the other. You may pick one envelope and keep the money it contains. Having chosen an envelope at will, but before inspecting it, you are given the chance to switch envelopes. Should you switch?

Determinacy is a subfield of set theory, a branch of mathematics, that examines the conditions under which one or the other player of a game has a winning strategy, and the consequences of the existence of such strategies. Alternatively and similarly, "determinacy" is the property of a game whereby such a strategy exists. Determinacy was introduced by Gale and Stewart in 1950, under the name "determinateness".

In game theory, trembling hand perfect equilibrium is a type of refinement of a Nash equilibrium that was first proposed by Reinhard Selten. A trembling hand perfect equilibrium is an equilibrium that takes the possibility of off-the-equilibrium play into account by assuming that the players, through a "slip of the hand" or tremble, may choose unintended strategies, albeit with negligible probability.

Juan Manuel Rodríguez Parrondo is a Spanish physicist. He is mostly popular for the invention of the Parrondo's paradox and his contributions in the thermodynamical study of information.

<span class="mw-page-title-main">Monty Hall problem</span> Probability puzzle

The Monty Hall problem is a brain teaser, in the form of a probability puzzle, based nominally on the American television game show Let's Make a Deal and named after its original host, Monty Hall. The problem was originally posed in a letter by Steve Selvin to the American Statistician in 1975. It became famous as a question from reader Craig F. Whitaker's letter quoted in Marilyn vos Savant's "Ask Marilyn" column in Parade magazine in 1990:

Suppose you're on a game show, and you're given the choice of three doors: Behind one door is a car; behind the others, goats. You pick a door, say No. 1, and the host, who knows what's behind the doors, opens another door, say No. 3, which has a goat. He then says to you, "Do you want to pick door No. 2?" Is it to your advantage to switch your choice?

The mathematics of gambling is a collection of probability applications encountered in games of chance and can get included in game theory. From a mathematical point of view, the games of chance are experiments generating various types of aleatory events, and it is possible to calculate by using the properties of probability on a finite space of possibilities.

Proper equilibrium is a refinement of Nash Equilibrium by Roger B. Myerson. Proper equilibrium further refines Reinhard Selten's notion of a trembling hand perfect equilibrium by assuming that more costly trembles are made with significantly smaller probability than less costly ones.

In game theory, a stochastic game, introduced by Lloyd Shapley in the early 1950s, is a repeated game with probabilistic transitions played by one or more players. The game is played in a sequence of stages. At the beginning of each stage the game is in some state. The players select actions and each player receives a payoff that depends on the current state and the chosen actions. The game then moves to a new random state whose distribution depends on the previous state and the actions chosen by the players. The procedure is repeated at the new state and play continues for a finite or infinite number of stages. The total payoff to a player is often taken to be the discounted sum of the stage payoffs or the limit inferior of the averages of the stage payoffs.

Quantum pseudo-telepathy is the fact that in certain Bayesian games with asymmetric information, players who have access to a shared physical system in an entangled quantum state, and who are able to execute strategies that are contingent upon measurements performed on the entangled physical system, are able to achieve higher expected payoffs in equilibrium than can be achieved in any mixed-strategy Nash equilibrium of the same game by players without access to the entangled quantum system.

<span class="mw-page-title-main">Conditional probability</span> Probability of an event occurring, given that another event has already occurred

In probability theory, conditional probability is a measure of the probability of an event occurring, given that another event (by assumption, presumption, assertion or evidence) is already known to have occurred. This particular method relies on event A occurring with some sort of relationship with another event B. In this situation, the event A can be analyzed by a conditional probability with respect to B. If the event of interest is A and the event B is known or assumed to have occurred, "the conditional probability of A given B", or "the probability of A under the condition B", is usually written as P(A|B) or occasionally PB(A). This can also be understood as the fraction of probability B that intersects with A, or the ratio of the probabilities of both events happening to the "given" one happening (how many times A occurs rather than not assuming B has occurred): .

Quantum refereed game in quantum information processing is a class of games in the general theory of quantum games. It is played between two players, Alice and Bob, and arbitrated by a referee. The referee outputs the pay-off for the players after interacting with them for a fixed number of rounds, while exchanging quantum information.

References

  1. 1 2 Harmer, G. P.; Abbott, D. (1999). "Losing strategies can win by Parrondo's paradox". Nature. 402 (6764): 864. doi: 10.1038/47220 . S2CID   41319393.
  2. ↑ Shu, Jian-Jun; Wang, Q.-W. (2014). "Beyond Parrondo's paradox". Scientific Reports. 4 (4244): 4244. arXiv: 1403.5468 . Bibcode:2014NatSR...4E4244S. doi:10.1038/srep04244. PMC   5379438 . PMID   24577586.
  3. 1 2 Jansen, V. A. A.; Yoshimura, J. (1998). "Populations can persist in an environment consisting of sink habitats only". Proceedings of the National Academy of Sciences USA. 95 (7): 3696–3698. Bibcode:1998PNAS...95.3696J. doi: 10.1073/pnas.95.7.3696 . PMC   19898 . PMID   9520428..
  4. ↑ D. Minor, "Parrondo's Paradox - Hope for Losers!", The College Mathematics Journal 34(1) (2003) 15-20
  5. ↑ Harmer, G. P.; Abbott, D. (1999). "Parrondo's paradox". Statistical Science. 14 (2): 206–213. doi: 10.1214/ss/1009212247 .
  6. ↑ G. P. Harmer, D. Abbott, P. G. Taylor, and J. M. R. Parrondo, in Proc. 2nd Int. Conf. Unsolved Problems of Noise and Fluctuations, D. Abbott, and L. B. Kish, eds., American Institute of Physics, 2000
  7. ↑ Harmer, G. P.; Abbott, D.; Taylor, P. G. (2000). "The Paradox of Parrondo's games". Proceedings of the Royal Society of London A. 456 (1994): 1–13. Bibcode:2000RSPSA.456..247H. doi:10.1098/rspa.2000.0516. S2CID   54202597.
  8. ↑ G. P. Harmer, D. Abbott, P. G. Taylor, C. E. M. Pearce and J. M. R. Parrondo, Information entropy and Parrondo's discrete-time ratchet, in Proc. Stochastic and Chaotic Dynamics in the Lakes, Ambleside, U.K., P. V. E. McClintock, ed., American Institute of Physics, 2000
  9. ↑ Thomas K. Philips and Andrew B. Feldman, Parrondo's Paradox is not Paradoxical, Social Science Research Network (SSRN) Working Papers, August 2004
  10. ↑ Iyengar, R.; Kohli, R. (2004). "Why Parrondo's paradox is irrelevant for utility theory, stock buying, and the emergence of life". Complexity. 9 (1): 23–27. doi:10.1002/cplx.10112.
  11. ↑ Winning While Losing: New Strategy Solves'Two-Envelope' Paradox at Physorg.com
  12. ↑ Stutzer, Michael. "The Paradox of Diversification" (PDF). Retrieved 28 August 2019.
  13. ↑ Stutzer, Michael. "A Simple Parrondo Paradox" (PDF). Retrieved 28 August 2019.
  14. ↑ Wolf, Denise M.; Vazirani, Vijay V.; Arkin, Adam P. (2005-05-21). "Diversity in times of adversity: probabilistic strategies in microbial survival games". Journal of Theoretical Biology. 234 (2): 227–253. Bibcode:2005JThBi.234..227W. doi:10.1016/j.jtbi.2004.11.020. PMID   15757681.
  15. ↑ Cheong, Kang Hao; Tan, Zong Xuan; Xie, Neng-gang; Jones, Michael C. (2016-10-14). "A Paradoxical Evolutionary Mechanism in Stochastically Switching Environments". Scientific Reports. 6: 34889. Bibcode:2016NatSR...634889C. doi:10.1038/srep34889. ISSN   2045-2322. PMC   5064378 . PMID   27739447.
  16. ↑ Tan, Zong Xuan; Cheong, Kang Hao (2017-01-13). "Nomadic-colonial life strategies enable paradoxical survival and growth despite habitat destruction". eLife. 6: e21673. doi: 10.7554/eLife.21673 . ISSN   2050-084X. PMC   5319843 . PMID   28084993.
  17. ↑ Jones, Michael C.; Koh, Jin Ming; Cheong, Kang Hao (2018-06-05). "Multicellular survival as a consequence of Parrondo's paradox". Proceedings of the National Academy of Sciences. 115 (23): E5258–E5259. Bibcode:2018PNAS..115E5258C. doi: 10.1073/pnas.1806485115 . ISSN   0027-8424. PMC   6003326 . PMID   29752380.
  18. ↑ Nelson, Paul; Masel, Joanna (2018-05-11). "Reply to Cheong et al.: Unicellular survival precludes Parrondo's paradox". Proceedings of the National Academy of Sciences. 115 (23): E5260. Bibcode:2018PNAS..115E5260N. doi: 10.1073/pnas.1806709115 . ISSN   0027-8424. PMC   6003321 . PMID   29752383.
  19. ↑ Cheong, Kang Hao; Koh, Jin Ming; Jones, Michael C. (2019-02-21). "Do Arctic Hares Play Parrondo's Games?". Fluctuation and Noise Letters. 18 (3): 1971001. Bibcode:2019FNL....1871001C. doi:10.1142/S0219477519710019. ISSN   0219-4775. S2CID   127161619.
  20. ↑ Di Crescenzo, Antonio (2007). "A Parrondo paradox in reliability theory" (PDF). The Mathematical Scientist. 32 (1): 17–22.[ permanent dead link ]
  21. ↑ Abbott, Derek. "The Official Parrondo's Paradox Page". The University of Adelaide. Archived from the original on 21 June 2018.

Further reading

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.