St Petersburg Paradox

Suppose you are offered the following peculiar gamble. You flip a symmetric coin until you get tails. Once you get tails, you get paid 2n2^n dollars, where nn is the number of times you flipped the coin (remember that you must stop flipping once you get tails). For example, if you get tails on your first flip, you get 2 dollars. If you get tails on your second flip, you get $4, etc. How much would you be willing to pay to play this game? You would definitely be willing to pay $2, but what about $100, $1000 or a million?

It is probably not a good idea to pay more than $1000 to play this game, because the chance of getting 10 heads in a row is less than 0.1%. In other words, with probability 99.9% you would lose money. So where is the paradox? Well, you can expect to make infinite amount of money from playing this game just once. More precisely, if X is how much money you will be paid (a so-called random variable), the expected value of XX is 122+144+188+=1+1+1+=\frac{1}{2}\cdot 2 + \frac{1}{4}\cdot 4 + \frac{1}{8}\cdot 8 + … = 1 + 1 + 1 + … = \infty. So in theory you should be willing to pay any amount, no matter how large, in order to play this game just once. It is interesting to observe that the expectation is infinite despite the fact that with probability 1 you will receive a finite amount of money.

Let's try to resolve this paradox. Suppose that instead of playing this game once, you can play it as many times as you want (let's disregard how long it would take to flip a coin a billion times) and receive the average of your winnings. Further suppose that it costs SS dollars (say, SS = 1 million) to play the game, and you get to play it as many times as you choose. But you must choose how many times you will play before you start playing; otherwise you could just keep playing until you make enough profit, which seems unfair. To summarize:

Now the question becomes: given SS, how many times NN will you play the game to come out positive? How will you go about figuring it out, at least approximately?

The relevant terms from probability theory are Law of Large Numbers and the Central Limit Theorem. But we must be careful using them in our setting. Not only is the second moment of our random variable X infinite, the first moment is as well! Instead we can analyze a truncated random variable XX', which agrees with XX on the first 2n2^n values, but is equal to 0 for larger values. For example, if n=10n = 10, X(1)=2,X(2)=4,X(3)=8,,X(10)=210,X(11)=0=X(12)=X'(1) = 2, X'(2) = 4, X'(3) = 8, …, X'(10) = 2^{10}, X'(11) = 0 = X'(12) = \dots. So XX' is an underestimate of the amount of money you actually win. Intuitively, XX' makes a lot of sense: if the probability of flipping over 10 heads in a row is less than 0.1%, we may as well treat it as zero, and just pretend that it will never happen. It is convenient that the expected value of XX' is exactly n, instead of infinity. Now that we got our hands on a simpler random variable, let's see what will happen to the average of X1,.,XNX'_1, …., X'_N.

Let Xˉ=1/Mi=1NXi\bar X' = 1/M\cdot \sum_{i=1}^N X'_i be the average of our new random variables X1,.,XNX'_1, …., X'_N. Since XX' are all iid (independent and identically distributed), the expected value of Xˉ\bar X' is n as well. Also, the variance of Xˉ\bar X' is 1M(variance of X)\frac{1}{M} \cdot (\text{variance of }X'). The variance of X is E[X2]E[X]2=2n+11n22n+1\mathbb{E}[X'^2] - \mathbb{E}[X']^2 = 2^{n+1} – 1 – n^2 \approx 2^{n+1}. So The variance of Xˉ\bar X' is approximately 2n+1/M2^{n+1}/M.

Let's pause here to ponder what we just computed. Since we only use n to simplify our analysis, we are free to choose it any way we like. Increasing n increases the expected value for XX' but it also increases its variance exponentially! Recall that variance is a measure of how sure we can be that XX' lands close to its expected value. So there seems to be a trade-off between higher expected value and being confident that we are not too far off from the expected value.

Now we will play fast and loose with the Central Limit Theorem by treating Xˉ\bar X' as a normal random variable (it is not necessary but will simplify the analysis). Since it costs S dollars to play the game, we want the expected value of Xˉ\bar X' to be at least S. So let's take nn to be 2S2S. Now the variance of Xˉ\bar X' is 22S+1/M2^{2S+1}/M. Now taking MM to be 22S+1=2(2S)22^{2S+1} = 2 \cdot (2^S)^2 ensures that the variance is 1. Since we are treating Xˉ\bar X' as a normal random variable, the probability that Xˉ\bar X' is below SS is very low. Since XX' is an underestimate of XX, Xˉ\bar X' is an underestimate of the average of X1,,XMX_1, …, X_M. So with overwhelming probability, the average of your winnings will be above SS.

We have now answered the question: taking MM to be 2(2S)22 \cdot (2^S)^2 ensures coming out positive when the cost is SS. The important bit here is that MM is exponential in SS. For example, if S=10S = 10, i.e. it costs $10 to play, then our computations suggest M=22201,000,000M = 2 \cdot 2^{20} \approx 1,000,000. This seems like a gross over-estimate. Perhaps using finer techniques such as tail bounds on subgaussian random variables will yield a more realistic estimate.