Daily Archives: 9/7/2009

Parrondo’s Paradox

earl53_1909pennyfront2webI 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:

  1. 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.
  2. 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.
  3. 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)