Sunday, July 26, 2009

St. Petersberg Paradox

A few days ago we explored the St. Petersberg Paradox.

Here's how I stated it: We'll play a game involving coin flips, and I'll play you depending on how the coins flip. You have to decide how much you are willing to pay to play the game.

A warmup game: I flip a coin, and if it comes up heads I give you $1, tails I give you $2. How much to play?

Both 13-year olds immediately said "up to $1.50".

The real game: I flip a coin. If it comes up heads I give you $1. If it comes up tails, I flip again. If it comes up heads this time, I give you $2. If it comes up tails, I flip again. If it comes up heads this time I give you $4. In general if I flip k tails in a row I pay you 2k dollars.

My 13-year-old boy thought for a minute and growled at me, complaining that the game was worth an infinite amount of money, and that no such game could really exist. He said he should be willing to pay any amount. My 13-year-old girl (at a different time) thought about at and found it much less upsetting, concluded that it had infinite value and offered $5 to play the game. (We didn't actually play it.)

We ran a few simulations, and found that it's really hard to get that $5 back even if you play many times.

Analysis: The game has no expected value (it's worth an infinite amount of money), but since I only have a finite amount of money in my pocket it's not really worth that much to play against me as the casino. Even if I had a lot of money, it takes a long time to recover a large payments because it requires events that are unlikely to ever be seen. For example, if you paid $100 to play this game, you wouldn't expect to come out ahead until we had played about 2100 games, because it requires a sequence of 100 tails in a row to cover all the accumulated losses.

About Me

I work in the Google cloud now. Previously I worked in the Oracle cloud and before that I was research faculty at MIT, and Chief Architect at Tokutek. Before that I worked at Akamai, was a Yale CS professor, and worked at Thinking Machines.