Simulation of St. Petersburg Paradox

St. Petersburg Paradox exemplifies a situation where the expected value of an outcome doesn't reflect the realistic outcomes. The game can be played by flipping a coin until heads comes up. Let the outcome be 2 to the power of the number of coin flips. The derivation won't be shown here in detail (but is available on the link below), but essentially, there is 1/(2^n) chance of an outcome of (2^n), for all positive integers n. The expected payoff for each integer n is therefore 1, and the sum of the expected payoffs, the expected value of this game, is therefore infinity.

Realistic outcomes are far from this expected value. One can briefly visualize this by realizing that there's 50% chance of an outcome of 2, 25% chance of an outcome of 4, 12.5% chance of an outcome of 8, etc. Simply put, the chances of very high outcomes are very small. Let's use programming to simulate numerous rounds of this game. The Java code for the simulation method is as follows:

public static int simulation()
 {
     int times = 0;
     double flip = 0;
     while(flip < 0.5) //reflecting the 50% chance of getting heads
     {
         flip = Math.random();
         times++;
     }
     double result =  Math.pow(2,times);
     return (int)result;
 }

Writing a for loop code, this method was called 1,000,000 times, with the output values exported onto Microsoft Excel. The values were sorted and counted, and the results are as follows, along with the expected frequency of the different outcomes.

n	Outcome (2^n)	Frequency	Expected Freq	Deviation
1	2	500,592	500,000.00	0.118%
2	4	249,969	250,000.00	-0.012%
3	8	124,870	125,000.00	-0.104%
4	16	62,262	62,500.00	-0.381%
5	32	30,951	31,250.00	-0.957%
6	64	15,741	15,625.00	0.742%
7	128	7,843	7,812.50	0.390%
8	256	3,883	3,906.25	-0.595%
9	512	1,900	1,953.13	-2.720%
10	1,024	993	976.56	1.683%
11	2,048	484	488.28	-0.877%
12	4,096	233	244.14	-4.563%
13	8,192	144	122.07	17.965%
14	16,384	71	61.04	16.326%
15	32,768	34	30.52	11.411%
16	65,536	12	15.26	-21.357%
17	131,072	11	7.63	44.179%
18	262,144	3	3.81	-21.357%
19	524,288	4	1.91	109.715%

Even with 1 million trials, the greatest output value was only 524,288, which reflects the rare instance of 18 straight flips of tail before finally getting a heads. This only happened 4 times out of the 1 million trials, and was even considered strong positive deviation from the expected frequency of 1.91. The expected value of this game (expected average value) is still infinity, as the math demonstrates.

In this simulation of 1,000,000 trials, the average output value was 20.496084. The results are, as expected, very skewed to the right. If we let the output value measure monetary amount, it's interesting to note that the top 996 trials (0.0996%) contains 51.30% of the values. The top 0.7772% contains 65.86%. The bottom 96.8644% contains only 24.33%.

Sources:

• http://plato.stanford.edu/entries/paradox-stpetersburg/