The St. Petersburg Paradox

Mar 24, 2022

A paper I wrote for my game theory class about a fascinating paradox.

The St. Petersburg paradox is a famous problem in decision theory about a simple game, played as follows:

  1. A coin is flipped repeatedly until, on turn n, it lands on heads.

  2. The player is awarded $2n.

Therefore, in each round the player has a 50% chance of winning $2, a 25% chance of winning $4, a 12.5% chance of winning $8 and so on.

Distribution of payouts in one round of the St. Petersburg game.
Distribution of payouts in one round of the St. Petersburg game.

The question is simple: what is a reasonable amount of money to pay to play a round of this game?

Well, a core tenet of decision theory is that any rational person should be willing to pay an amount up to the average payout of the game. However, the St. Petersburg Game is paradoxial: the average payout (expected utility) is infinite.

\[ \begin{aligned} EU &= \sum_{n=1}^{\infty} \frac{1}{2^{n}}\$2^n \\ &= \sum_{n=1}^{\infty}1 \$\\ &= \$\infty\end{aligned} \]

Of course, no reasonable person expects to win an infinite sum. The probability of large payouts is incredibly low and it’s easy to see that most rounds will award less than $10.

On the surface, the answer is simple. It’s irrational to pay a lot to play because the odds of winning a large sum are extremely low. In fancier terms, because the distribution of possible winnings is long-tailed, the mean is a poor measure of central tendency. To illustrate, the following figure and table show the distribution of payouts when one round of the game is simulated for n = 7,900,000 or approximately the global population. While half a dozen people win a billion dollars or more, the overwhelming majority take home only small change.

Distribution of simulated St. Petersburg game payouts for n = 7,900,000,000
Distribution of simulated St. Petersburg game payouts for n = 7,900,000,000
Winnings [$] Number of People
2 3,950,000,000
4 1,980,000,000
8 987,000,000
16 494,000,000
32 247,000,000
64 123,000,000
128 61,700,000
256 30,900,000
512 15,400,000
1,020 7,710,000
2,050 3,860,000
4,100 1,930,000
8,190 965,000
16,400 481,000
32,800 241,000
65,500 120,000
131,000 60,400
262,000 30,100
524,000 15,000
1,050,000 7,540
2,100,000 3,900
4,190,000 1,840
8,390,000 1,000
16,800,000 530
33,600,000 216
67,100,000 123
134,000,000 72
268,000,000 22
537,000,000 26
1,070,000,000 6
2,150,000,000 3
4,290,000,000 3
8,590,000,000 2
17,200,000,000 0

Clearly, expected utility maximization—a core tenet of classical decision theory—fails for this game. However, if the rational price to pay is not infinite, then what is it?

Historical Solutions

Finite funds

In 1754, Alexis Fontaine presented the paradox to the French Académie royale des sciences . He made the case that since the house cannot possibly have infinite funds the expected value may be calculated. For example, if the house has a bankroll of $1,000,000:

$$\begin{aligned} \text{Rounds}_{\text{max}} &= \log_2{1000,000,000} \\ &\approx 30 \\ EU &= \sum_{n=1}^{30}1 \\ &\approx 30\end{aligned}$$

This solution is sensible albeit dissatisfying. Sure, no real-life house can offer an infinite reward. However, the paradox is that even if they could, no one would be willing to pay the expected value to play.

Expected Utility

A classic resolution, introduced by , makes the important observation that in general, EU ≠ EMV. He proposed a logarithmic utility function where U = ln (MV). Consequently, the paradox can be reformulated as follows:

$$\begin{aligned} EU &= \sum_{n=1}^{\infty}\left(\frac{1}{2}\right)^n\ln\left(2^n\right) \\ &= 2\ln 2 \\\end{aligned}$$ Thus one should be willing to pay e2ln 2 = $4 to play. Others have extended this idea to consider the player’s existing wealth . $$\Delta EU=\sum_{n=1}^{\infty}\left(\frac{1}{2}\right)^{n}\left[\overbrace{\ln \left(w-c+2^{n-1}\right)}^{\text {utility after the game }}-\underbrace{\ln (w)}_{\text {utility before the game }}\right],$$ where w is the player’s wealth and c is the cost of a round of play.

These solutions and other variations are again sensible. However, they all may be defeated by increasing the payouts. For example, if the utility function is defined to be U = ln (MV), then the payouts are simply increased to $e2n:

$$\begin{aligned} EU &= \sum_{n=1}^{\infty}\left(\frac{1}{2}\right)^n\ln\left(e^{2n}\right) \\ &= \infty \\\end{aligned}$$

Towards a Better Solution

One may wonder whether a better strategy may be divised when multiple rounds of the game are played. Clearly, in this scenario a rational player should be willing to pay more per round as they have more chance to get lucky.

The figure below plots the average payout per round against the number of rounds played for 5 random simulations. It is interesting to note that while the results vary greatly, in general they seem to follow a linear trendline.

Mean payout of St. Petersburg game after *n* rounds for five random simulations.
Mean payout of St. Petersburg game after n rounds for five random simulations.

The Steinhaus Sequence

To understand why, it is necessary to restate the problem. To do so, consider an empty sequence of infinite length. Now fill every other empty space with a 2…

$$\begin{bmatrix}{\color{RawSienna} 2} & \_ & {\color{RawSienna} 2} & \_ & {\color{RawSienna} 2} & \_ & {\color{RawSienna} 2} & \_ & {\color{RawSienna} 2} & \_ & {\color{RawSienna} 2} & \_ & {\color{RawSienna} 2}\dots\end{bmatrix}$$

Again, fill every other empty space with a 4…

$$\begin{bmatrix}2 & {\color{RawSienna} 4} & 2 & \_ & 2 & {\color{RawSienna} 4} & 2 & \_ & 2 & {\color{RawSienna} 4} & 2 & \_ & 2\dots\end{bmatrix}$$

Once more, now with 8s…

$$\begin{bmatrix}2 & 4 & 2 & {\color{RawSienna} 8} & 2 & 4 & 2 & \_ & 2 & 4 & 2 & {\color{RawSienna} 8} & 2\dots\end{bmatrix}$$

And so on…

This approach was first proposed by H. Steinhaus, whose sequence represents exactly the expected payouts of the St. Petersburg game. A random draw from elements in the sequence will produce a 2 half the time, a 4 one-quarter of the time, an 8 one-eighth of the time, and so forth. What’s more, values are spaced as they are likely to appear at random. While two large values could in theory appear adjacent to one another, entropy favours an even distribution.

Now, the important observation to make is that if this sequence represents expected payouts of the game then it should also represent a fair price to play. For example, if a rational agent has the opportunity to play 3 rounds then he should be willing to pay $2+$4+$2=$8, or $2.70 per round to play.

The Table below records these values for numbers of rounds equal to powers of two. At 4 rounds, the fair price is $4. At 8 rounds, it’s $5. At 16, $6. Clearly, at pattern has emerged—the fair price is given by \(\log_2n+2\), where n is the number of rounds played. This result is verified by Figure 4. While the cumulative average is less than this value when n is not a power of 2, it is always within $1.

Fair per-round prices for the St. Petersburg game.
Number of Rounds Fair Price [$] Fair Price Per Round [$]
4 16 4
8 40 5
16 96 6
32 224 7

Naturally, these findings should be tested experimentally. Figure 5 overlays the simulated mean payouts over n rounds from Figure 3 with the fair price \(\log_2n+2\) It is remarkably accurate.

Average payout after *n* games, plotted against \\(\\log_2n+2\\).
Average payout after n games, plotted against \(\log_2n+2\).

Simulations

The following simulations presented in Figure 6 plot the wealth of 1,000 players over 10,000 rounds of the game with per-round fees of (a) $2 and (b) $100.

Evolution of cumulative payout for 1,000 simulated players over 10,000 rounds of the St. Petersburg game with per-round fees of $2 and $100. Y-axis plotted on a symmetrical log (symlog) scale
Evolution of cumulative payout for 1,000 simulated players over 10,000 rounds of the St. Petersburg game with per-round fees of $2 and $100. Y-axis plotted on a symmetrical log (symlog) scale

Clearly, $2 is too low while $100 is too high. However, it is interesting to note the asymmetry in their evolution. At $2, players’ wealth always increases. At $100, however, only the very lucky—represented by horizontal lines on the positive y-axis—can weather the attraction towards debt. However, at the limit, they too will suffer the inevitable s-shaped fall from grace.

By contrast, Figure 7 plots the same simulations with a per-round fee set to \(\log_2n+2\approx\$15\). While players lose money on most rounds, this is offset by the occasional large payout. Consequently, wealth is asymptotically stable—the game is fair.

Evolution of cumulative payout for 1,000 simulated players over 10,000 rounds of the St. Petersburg game with a per-round fee of \\(\\log_2 10+2\\approx\\$15\\). At this price wealth is asymptotically stable. Y-axis plotted on symmetrical log (symlog) scale.
Evolution of cumulative payout for 1,000 simulated players over 10,000 rounds of the St. Petersburg game with a per-round fee of \(\log_2 10+2\approx\$15\). At this price wealth is asymptotically stable. Y-axis plotted on symmetrical log (symlog) scale.

Conclusion

As with any game of chance, there will never be a completely “correct” solution to the St. Petersburg Paradox. Strategy will always depend on an individual player’s risk tolerance, wealth, and other factors. However, the strategy presented in this paper—that a rational person should be willing to pay $\(\log_2n+2\) per-round—is convincing. While the intersection of people with an interest in logical paradoxes and those will unlimited finances may be too limited to test these strategies in the real world, it is at least a fascinating idea to explore.

Source code for all figures and simulations is available at https://github.com/akoen/petersburg. Made using Julia and Gadfly 1.


  1. https://github.com/GiovineItalia/Gadfly.jl ↩︎


I would love to hear what you thought of this post. Loved it? Hated it? Want to share your hand-written poem with me via carrier pigeon? That might be challenging—try sending me an email.

You can get updates when I post something new.