Parrondo’s Paradox
I was reading Nahin’s Digital Dice, which I bought a while ago but which I didn’t really dive into deeply, and he had a nice exposition of Parrondo’s Paradox, which is very neat. Here’s the idea:
- We are going to play two different coin tossing games. In each case, if we win, we gain one unit. If we lose, we lose one unit.
- In Game A, we will toss a coin, and if it comes up heads, we win, otherwise we lose. Unfortunately for us, the coin is not a fair coin, it is more likely to come up tails than heads. Let’s call the probability of winning this game as 0.5 – ε. Clearly, this game is a losing one for ε > 0.
- In Game B, we have two coins. One is clearly biased against us: the chance of winning is just 0.1 – ε, the second is biased for us, and has probability of winning as 0.75 – ε. Here’s the wrinkle: if our bankroll is an exact multiple of three, we toss coin the first coin, otherwise we toss the second coin.
Game B is a bit harder to analyze, but let’s give it a try (it’s wrong, but it’s not too far wrong): 1/3 of the time, we gain one unit wth probability 0.1-ε and 2/3 of the time, we gain one unit with probability 0.75-ε. This means that our probability of winning is 8/15 – ε. If we set ε to be 0.005, we maintain a narrow advantage.
Or do we? Let’s go ahead and simulate this. I wrote some Python code that played both games for one million rounds. The results from a typical round:
GAME A: played 1000000 rounds, started with 0, ended with -8642 GAME B: played 1000000 rounds, started with 0, ended with -8532
So, here’s the first thing issue: Game B appears to be a loser as well. Why would that be? (Think about it).
But if we accept the fact that Game A and Game B are losing propositions, let’s play a new game called the combination game. It’s very simple, we randomly pick (perhaps by tossing a fair coin) which of the games we want to play in each round. If we simulate this game, we get the following (again, from a run of 1000000):
COMBINATION: played 1000000 rounds, started with 0, ended with 16620
What’s this about? We’re alternating between two losing games, and yet, we emerge as winners? What’s going on here?
Enjoy!
Addendum: Here’s some python code that I wrote to simulate the game.
#!/usr/bin/env python
#
# $Id$
# parrondo.py
#
import random
def play_game_a(capital, eps):
return random.uniform(0, 1) < (0.5 - eps)
def play_game_b(capital, eps):
if capital % 3 == 0:
return random.uniform(0, 1) < 0.1 - eps
else:
return random.uniform(0, 1) < 3.0/4.0 - eps
def play_game_combo(capital, eps):
if random.randint(0, 1):
return play_game_a(capital, eps)
else:
return play_game_b(capital, eps)
def play(name, f, n, icap, eps):
cap = icap
for i in range(n):
if f(cap, eps):
cap = cap + 1
else:
cap = cap - 1
print "%s: played %d rounds, started with %d, ended with %d" % (name, n, icap, cap)
play("GAME A", play_game_a, 1000000, 0, 0.005)
play("GAME B", play_game_b, 1000000, 0, 0.005)
play("COMBINATION", play_game_combo, 1000000, 0, 0.005)
I recall burning three or four weeks of a sabbatical getting Saccade.com on the air with Wordpress. So much tweaking…