1. ON ASTUMIAN'S PARADOX
- Author
-
Ehrhard Behrends
- Subjects
Computer Science::Computer Science and Game Theory ,Markov chain ,Generalization ,General Mathematics ,General Physics and Astronomy ,State (functional analysis) ,Zero (linguistics) ,Position (vector) ,If and only if ,Fair coin ,State space ,Algorithm ,Mathematical economics ,Mathematics - Abstract
An Astumian game is defined by a finite Markov chain with state space S with precisely two absorbing states, the winning and the losing state. The other states are transient, one of them is the starting position. The game is said to be losing (respectively fair respectively winning) if the probability to be absorbed at the winning state is smaller than 0.5 (respectively = 0.5 respectively larger than 0.5). Astumian's paradox states that there are losing games on the same state space S a stochastic mixture of which is winning. (By "stochastic mixture" we mean that in each step one decides with the help of a fair coin whether to use the transition probabilities of the first or the second game.) Most of our results concern fair games. Mixtures are systematically investigated. Rather surprisingly, the winning probability of the mixture of fair games can be arbitrarily close to zero (or to one). Even more counter-intuitive are examples of definitely losing games (this means that the winning probability is exactly zero) such that the winning probability of the mixture is arbitrarily close to one. We show, however, that such extreme examples are possible only if one tolerates huge running times of the game. As a natural generalization one can also consider arbitrary mixtures: the fair coin is replaced by a biased one, with probability λ respectively 1-λ one plays with the first respectively the second game. It turns out that fair games exist such that — depending on the choice of λ — the λ-mixture can be fair, losing or winning.
- Published
- 2005