Banner
    Statistical Physics Attacks St. Petersburg: Paradox Resolved
    By Johannes Koelman | November 18th 2012 07:05 AM | 36 comments | Print | E-mail | Track Comments
    About Johannes

    I am a Dutchman, currently living in India. Following a PhD in theoretical physics (spin-polarized quantum systems*) I entered a Global Fortune

    ...

    View Johannes's Profile
    In the history of statistics, economy and decision theory, the St. Petersburg paradox plays a key role. This lottery problem goes back a full three centuries to the mathematician Nicolas Bernoulli who first formulated the problem in 1713. Twenty five years later, in 1738, his nephew Daniel Bernoulli presented the problem to the Imperial Academy of Sciences in St. Petersburg. That presentation not only gave the paradox its name, it also created a lot of commotion amongst mathematicians.
     
    And even today, following three centuries of discussion and debate, the problem continuous to intrigue scientists and lay people alike. Yet, the paradox got fully resolved in the middle of the previous century. I was reminded of this paradox when it came up here at Science 2.0 in the comment section of a recent blog post on math paradoxes. When I checked the Wikipedia page dedicated to this paradox, I was shocked to see that this article mentions several approaches that have been claimed to resolve the paradox, but relegates the real resolution to this paradox to a short remark.

    Time for a blogpost.


    Imperial Academy of Sciences, St. Petersburg

     

    St. Petersburg Lottery


    The rules of the St. Petersburg lottery are straightforward: a fair coin is tossed repeatedly, until a tail appears, ending the game. The pot starts at $2 and is doubled each time a head appears. After the game ends, you win whatever is in the pot.

    So if the first coin toss results in a tail, you get $2. A head followed by a tail pays you $4. Head-head-tail yields $8, etc. Now the question is: how much are you willing to pay to enter this lottery? Statistical reasoning tells us to compute an ensemble average: investigate all potential outcomes and calculate the sum of the gains for each outcome weighted with the probability for that outcome. This weighted sum is known as the expected gain.

    For the St. Petersburg lottery where one wins $2 with probability 1/2, $4 with probability 1/4, $8 with probability 1/8, etc. the expected dollar gain is

    (1/2) 2 + (1/4) 4 + (1/8) 8 + (1/16) 16 + ... = 1 + 1 + 1 + 1 + ... = infinite

    The divergence of the expectation value means that no finite amount suffices as a fair entry fee for this game. Yet, if you play the game, you are sure to win no more than a finite amount. Also in actual practice, participants subjected to this game are not willing to pay more than a small entry fees (typically less than $20).

    What is happening here? Why is the expectation value for the St.Petersburg lottery such a poor representation of human actions in this lottery?

    Interestingly, the resolution to the St. Petersburg paradox becomes particularly transparent when applying statistical physics insights.


    Steinhaus Sequence


    Although I present the results in statistical physics language, the argument below follows the essence of Hugo Steinhaus' 1949 paper. It helps to investigate a simpler, deterministic game that shares its key characteristics with the St. Petersburg lottery.

    Imagine an infinite sequence of powers of two. The numbers generated follow a deterministic rule, that is recursive in nature:

    1) Start with an endless list of empty states and the number '1'
    2) Double the number and, starting with the first empty state, fill every other empty state with the number
    3) Repeat step 2) ad infinitum

    Building a Steinhaus sequence


    So we get a sequence that starts with the number '2', followed by a '4', then a '2', an '8', a '2', a '4', etc. If you would select at random one of he numbers generated, you would half of the time hit a '2', one quarter of the time a '4', and so on. Therefore, the expected value of numbers in the Steinhaus sequence is no different than that for the St. Petersburg lottery. More specifically, the Steinhaus expectation value diverges in exactly the same way as the St. Petersburg expectation value.

    However, one may also ask what value we would obtain when averaging over subsequent numbers in the Steinhaus sequence. For the first two numbers, an average value of (2 + 4)/2 = 3 is observed. For the first four numbers we have (2 + 4 + 2 + 8)/4 = 4. Averaging over eight numbers we have (2 + 4 + 2 + 8 + 2 + 4 + 2 + 16)/8 = 5. We see a simple pattern developing. For 2n subsequent numbers we observe an average value of n + 2. This goes against the widespread intuition that the average gain per game should be independent of the number of games played. At least we expect this to be the case when the number of games played is large. Here, such is not the case.

    Statistical physicists are familiar with this phenomenon. They refer to this peculiarity as 'non-ergodicity'. Ergodicity means that one can replace time averages with ensemble averages. Here, ergodicity does not hold as the time averages (the average values n+2 observed over 2n subsequent numbers) do not coincide with the ensemble average (the divergent expectation value). What is happening in any finite Steinhaus sequence, is that it visit large values contributing strongly to the average only logarithmically slowly, thereby causing a breakdown of the ergodic assumption.

     

    Ergodicity


    Now back to the St. Petersburg lottery. Based on the learnings from the Steinhaus sequence, it is easy to observe that also a sequence of gains from a repeated St. Petersburg lottery shows a pronounced breakdown of the ergodicity assumption. It is straightforward to generate a long sequence of St. Petersburg lottery pay-offs. This can be done with a coin, or more efficiently with any spreadsheet program. As suggested by the Steinhaus exercise, we plot the average gain of the first 2n numbers for progressively larger values of n. This is done in below figure for n up to 15 (2n = 32,384) for two independent runs.


    Although the average gains within each run fluctuate considerably, it is clear from the trends that the expected gains per game increases logarithmically with the number of games, just as we observed in the Steinhaus example. (To guide the eye, I have included in a fainter color the curve describing a pay-out per game of n+2 for 2n games.)

    The conclusion is straightforward: only one type of averages are practically relevant in the St. Petersburg lottery. These are the the time averages. The St. Petersburg time averages are finite, but logarithmically dependent on the number of games played. As these time averages don't converge to a finite value in the long time limit, the ergodic hypothesis breaks down for St. Petersburg lottery results. Therefore, the ensemble average, aka the expectation value for the game, can be cast aside as a meaningless divergent quantity.

    Math is simple if you're a physicist...

    Comments

    dorigo
    Very nice ! I'll propose it at the next party.

    Cheers,
    T.
    Thor Russell
    In the real world there is no such paradox however because people value money more like on a log scale once above a certain value, e.g. 2 million is not 2* 1 million in terms of usefullness for most people (and 2 billion is as good as 1 to me). Also of course the amount of money in the world is finite so in some situations where you play the game, the house has would have to default. People are also risk averse and a loss hurts 2* as much as a gain helps. Even if you know this, you can't stop yourself feeling that way so a rational person should perhaps include this in their calculation. 
    Given this, what is the rational amount for someone to pay to enter the game? What would you pay if you could play once, or if you could play 1000 times?

    On second thoughts this is quite a paradox. I did some runs myself and I am not sure that your n+2 line of best fit is best. On one run I got an average payoff of 264 for 64 games, which clearly doesn't fit the curve. The squared error to the curve in this case is then huge. Do you then make up some reason to ignore this because it is "atypical"? My curve of best fit in that case would be strange. If you were comparing different curves of best fit over many runs, with squared error, then sometimes you get very large errors between the curve and the data for a small number of games. What process/metric are you using to test the curve you have chosen is in fact the "best" curve?
     
    The real world game is different to the Steinhaus sequence because in the real world your values can be taken from any place on the infinite sequence, not at the beginning, so using some metrics, the best fit curves could be different in those two situations. If you do 10,000 runs of 64 games, then the average payoff per game I got was 18.4, a long way off your curve, and not surprisingly perhaps closer to the payoff I got when I did a single run for  200,000 games.

    Thor Russell
    Johannes Koelman
    A non-ergodic game a stranger beast than your analysis presumes. Straightforward averaging is not allowed. If you do 10,000 runs of 64 games and calculate the average payoff per game, you have effectively determined the payoff per game in a 640,000 long sequence, not the payoff per game in a 64 long sequence.  

    I hope I have convinced you that if you would agree to play N trials at a price per game of P, then you would need to agree a price per game P+1 if you were to play 2N games. This is all I wanted (and needed) to demonstrate. 
    Thor Russell
    I would pay P+1 for 2N in the real world case because of non-linear utility function etc, but in the infinite case without this, I am not convinced this is a non-ergodic game. 
    There are still some paradoxical elements to it. Doesn't your claim that it is ergodic depend on your curve of best fit being correct? That is my point, how do you test this curve you have chosen is in fact the best fit other than just claiming the log formula is correct?

    Lets say in the pure infinite case with just one run, I choose to pay $10 for one game. How can you tell me I have made the wrong decision and paid too much? If I make $16 then on what basis have you got for saying I was "lucky" without resorting to multiple runs of a single game, and furthermore If 1 million people all pay $10 for one game, then on average they will likely be up and make more than $10 as per your graph. Still seems pretty paradoxical to me.




    Thor Russell
    vongehr
    You are correct. What is sold here as the "solution", namely claiming that the Steinhaus stuff is the same (it is not - you could never be lucky with it), equals changing the game to a different one that is missing precisely what made the problem a problem. Mature game theory would, as you proposed, consider instead the actual utility.
    "I would pay P+1 for 2N in the real world case because of non-linear utility function etc, but in the infinite case without this, I am not convinced this is a non-ergodic game."

    What a coincidence that you are the descendant of creatures that used a logarithmic utility function. I wonder what happened to creatures that used a linear utility function?

    Johannes Koelman


    "I am not convinced this is a non-ergodic game."

    I am puzzled by this remark. Apparently you believe the St. Petersburg lottery has a pay-off per game that converges to a fixed value for large number of games? All numerical evidence points away from this. You have done some numerical experiments yourself, are you sure this is your conclusion?

    Note that nowhere I have stated that the fair price for participating in 2^N games of the St. Petersburg lottery is precisely N+2. Non-linear utility functions will affect the exact value for the constant (the value 2 is rigorous only for utilities given by the Steinhaus sequence when starting tracking gains from the first term and when including a number of terms equal to a power of two). I used the words "to guide the eye" when including the N+2 relationship in the payout graphs, and did so for a good reason. 

    What I do state as a firm conclusion is that there is a term N included in the payoff per game (and hence twice the number of games giving a payoff per game increase equal to unity). This follows straight from the Steinhaus argument and is confirmed by the direct numerical evidence obtained from a simple spreadsheet exercise. Nowhere did I use non-linear utilities. In fact, my whole point is that you don't need to invoke the non-linear utility argument to demonstrate that the straight ensemble average argument is nonsense. 

    dorigo
    Thanks to Thor also (besides Johannes) for this simple example of why this is still a paradox. Fascinating stuff! A frequentist can't help feeling dizzy here.

    Cheers,
    T.
    Nice article. I never felt at ease with the widely-accepted non-linear utility approach. Only if it would be logically impossible to value money linearly would this solve the Petersburg paradox. The non-ergodicity observation does eliminate the paradox, but it still leaves me confused because it doesn't provide a construction to evaluate the game.

    Johannes Koelman
    You are right. Most reactions here point to the fact that discarding ensemble averages for non-ergodic processes, although this provides an obvious solution to the paradox, is difficult to digest. And indeed, the whole non-ergodicity argument in itself does not provide a construction to evaluate the game. Having said that, Steinhaus' paper (see link in article) makes it explicit that paying for each St. Petersburg game a variable amount that follows the terms of the Steinhaus sequence, does provide a fair (although heavily fluctuating) price. 
    Two points.
    First, it is an empirical fact that 'utility' is nonlinear in 'dollars'. That is the only explanation why people require a 'risk-premium' to buy risky assets, and are willing to accept lower returns if they are risk-free. Think of the difference between high-risk, high-return stocks and low-risk, low-return checking accounts. That resolves the St. Petersburg Paradox right there.
    Second, the whole issue of ergodicity vs. nonergodicity is a red herring. The puzzle lies in explaining why one should use the time average rather than the ensemble average. One way to get an actual value of the game is to ask what price gives one a 50%, or 20%, or 80% chance of making a profit. For any given probability of profit, the corresponding ticket price is easy to compute. Of course, this is literally isomorphic to the nonlinear utility approach: demanding an 80% chance of profit is the same thing as being very risk averse.
    Third, simple numerical experiments are statistically invalid. Try computing the mean and variance of your results - and you will find that both are infinite. Hence, there is no theoretical justification for looking at averages, or curves of average vs. trials, as is done in this article. Classical statistics, and common intuition, break down in cases of infinite variance or means. These "long tailed" distributions all have one common characteristics: the more data your gather, the more the mean and variance explode. Further, the expected difference between any two runs is infinite, so there is no useful sense of "reproducibility" or of "curve fitting". These are very difficult problems -- which is precisely why the St. Petersburgh Paradox remains so interesting.

    Thor Russell
    Numerical experiments can also be misleading even with things are not infinite. e.g. a game gives you a 1/million chance to win $1 billion for the cost of $1. Simulations will likely show you losing money for 1 to about 1 million games, with an average of 1000* return on investment for large numbers of runs. Plotting this would give you a misleading curve and you could try to conclude the game was non-ergodic, which would of course be incorrect.
    Thor Russell
    Johannes Koelman
    you could try to conclude the game was non-ergodic, which would of course be incorrect
    Not really. You would conclude that the game was perfectly ergodic (correct) with a negative gain per game played (incorrect).
    Johannes Koelman
    Two points.
    First, [..]
    Second, [..]
    Third, [..]
    there are three kinds of people: those who can count, and those who can't...
     empirical fact that 'utility' is nonlinear in 'dollars'. [..] That resolves the St. Petersburg Paradox right there.
    What is your response to the comment here that this leaves the paradox for those that value utility linearly in dollars?
    The puzzle lies in explaining why one should use the time average rather than the ensemble average.
    You must be living in a multiverse in which you experience the total of the consequences of your actions averaged over all universes. I don't. I live in a universe in which I experience the consequence of a chain of actions ordered in time.

    Really, give it some thought: only time averages have a physical meaning.
    Try computing the mean and variance of your results - and you will find that both are infinite. Hence, there is no theoretical justification for looking at averages, or curves of average vs. trials, as is done in this article.
    In the above article I haven't computed any ensemble averages. All I have done is to keep track of the total winnings in a sequence of games, and to express the results in gains per game. It is you who is proposing to compute means and variances. That is of course a meaningless exercise for this non-ergodic game.
    Thor Russell
    1. If you value utility linearly with a finite amount of money, its easy put in the max payout and calculate, you get a finite value. In the actual St Petersburg case there is also no paradox. If you are offered $4 to play you accept, if you are offered $1M, $1B or any fininte amount to play you still accept, as the expected return is greater than any fixed value you pay to enter, so no paradox. Yes of course it sounds counter-intuitive, but that hardly means anything as infinite money is counter-intuitive to say the least.    
    2. OK its clear there is some confusion here, I think you are changing how you do things. You talk about time averages yet you do not compute them either. The time average of playing a single game over and over again or playing 1 run with 10,000 games has the same expectation value: not bounded. There is nothing to stop you playing just 1 game for $4, then another for $4 ... and adding up the results. This time average for playing 1 game many times is surely valid but you appear to reject it.  You implicitly accept some kind of ensemble averaging by showing two independent runs in your blog post anyway. Why have two runs if not to claim that they are in some sense representative of some quantity with finite values.

    3. You keep claiming the game is non-ergodic and that I do not understand how such things work. That is the point, you just CLAIM it is non-ergodic without proof. Your simulation does not in any way support your claim. Your simulation where you keep track of winnings is claiming to be representative of something. Otherwise there is no point in presenting it. So what is it representative of? I have explained how your simulation process is not representative. As I explained, if you simulated a game with a 1/M chance of winning $1B then you would get different results depending on the number of games, and by your same method claim that game would be non-ergodic. 

    So put it another way. Given a game, which may be either finite or unbounded in its expected value, describe a test for determining whether a game is non-ergodic or not. You have not put forward such a test, or if you have the method you have used (your graph) is clearly flawed as shown by the counter example earlier. You are either just claiming without justification the game is non-ergodic or using a flawed test to claim it. If you can present a rigorous process for determining ergodic vs non-ergodic then that will help settle this. 
    Thor Russell
    Johannes Koelman

    The time average of playing a single game over and over again or playing 1 run with 10,000 games has the same expectation value: not bounded.
    You keep talking about "expectation value" but this refers to an ensemble average which makes no sense for the St. Petersburg game.
    There is nothing to stop you playing just 1 game for $4, then another for $4 ... and adding up the results. This time average for playing 1 game many times is surely valid but you appear to reject it.
    Of course you can play many games all for $ 4. Let's say you repeat the game a hundred times. Surely you can determine your average gain per game over these hundred games. Such a  time average I do not reject. What I reject is to refer to this average gain as an estimate for the expectation value of a single game. You didn't play a single game, you played a hundred games. 
    You implicitly accept some kind of ensemble averaging by showing two independent runs in your blog post anyway. Why have two runs if not to claim that they are in some sense representative of some quantity with finite values.
    I show two independent runs to ensure no-one can accuse me of hiding the fact that there is a significant stochastic component no matter how long you continue your play. (The hoops a blogger has to go thru in defense to straw men!) Note that I do not average over these two runs. 
    You keep claiming the game is non-ergodic and that I do not understand how such things work. That is the point, you just CLAIM it is non-ergodic without proof.
    The burdon of proof is on you. The ergodic hypothesis is an assumption. You claim that ensemble avarages are meaningful for this game. In stating this you utilise the ergodic hypothesis.
    Your simulation does not in any way support your claim. Your simulation where you keep track of winnings is claiming to be representative of something. Otherwise there is no point in presenting it. So what is it representative of?
    It represents a running time average (up to 32,768 games).
    I have explained how your simulation process is not representative. As I explained, if you simulated a game with a 1/M chance of winning $1B then you would get different results depending on the number of games, and by your same method claim that game would be non-ergodic.
    No, I would observe a convergence to an ergodic behavior (a flat pay-off of $ 1,000 per game). Of course I need to simulate long enough. By the way, if I would stop the simulation run prematurely, I would still conclude the game to be ergodic, but I would draw the wrong conclusion on the pay-off per game ($ 0). 

    I hope you are not claiming here that I stopped the simulation prematurely (at 32,768 games)?
    So put it another way. Given a game, which may be either finite or unbounded in its expected value, describe a test for determining whether a game is non-ergodic or not.
    For a physicist that is easy. As I explained above, the question is "how to substantiate a claim of a game being ergodic?" A physicist runs a long simulation and demonstrate that the pay-off per game flattens off to a constant value. As long as you don't observe a flattening off, you have not substantiated your claim of the game being ergodic.

    For a mathematician, it is more difficult. Either way, you have to mathematically prove your claim. This proof will be different for different games. In his 1949 paper, Steinhaus proved the Saint Petersburg lottery to be non-ergodic. He did so by demonstrating that in the long run the Steinhaus sequence provides a fair payment schedule for participating.

    Thor Russell
    1. "Of course you can play many games all for $ 4. Let's say you repeat the game a hundred times. Surely you can determine your average gain per game over these hundred games. Such a  time average I do not reject."


    OK, now if you do that, then the time average is undefined and unbounded. Now if you reject ensemble averages, how do you even define the "fair price" to enter with x games? It seems to me you can't even define it, not talk about it if you do this. Is the "fair price" then just the first number to pop up from your simulation that looks about what you want to see?It seems that is what you are doing. If you happened to get a run of about 128, 64, 64, 8, 8, 8, with increasing games, you wouldn't have plotted that in the blog post, and have it totally not fit the curve, but rejected it as non-typical. So there is some kind of ensemble median like process going on when you decide that some results are typical and should be plotted.


    "I show two independent runs to ensure no-one can accuse me of hiding the fact that there is a significant stochastic component no matter how long you continue your play. "


    No you do not average them, but they are still supposed to be representative, and in some sense say the values are typical and vary about a mean. This is incorrect, the mean/std are undefined and showing two examples of such a strange skewed distribution mislead. You imply a median, but do not calculate. You cannot meaningfully show two examples of a number between 0 and infinity, however that is what you are doing here. The skewed sampling process makes it appear meaningful.


    "The burdon of proof is on you. The ergodic hypothesis is an assumption. You claim that ensemble avarages are meaningful for this game. In stating this you utilise the ergodic hypothesis."


    OK I think definitions are in order. According to me, a game must have a finite expectation value to even be considered for ergodic vs non-ergodic. If it is infinite, it is neither ergodic or non-ergodic, it is undefined and such concepts only mislead. Applying logic that is correct for a non-ergodic case when in fact you are dealing with infinities is like dividing by zero to me. You get wrong answers. 


    I claim that you need to show that your simulations are a fair and representative sample of the quantity (price to enter) claimed to have merit. You present them as having meaning, but the assumptions, definitions, groundwork are not there for you to do that. e.g. Whats the fair price to enter with 8 games and what is the repeatable process I use to check that claim, and why is it correct? You imply that your simulation is a process to estimate that value, however your simulation just chooses a random number between 2 and infinity each time it is run. It skews the number towards low values but that is still what it is doing. 


    Now to your final point. The Steinhaus sequence proves nothing because it is a different game. It looks similar, but it is obviously not the same. I have shown in my second comment below with a fixed payoff, that it gives a clearly wrong answer for determining the fair payment schedule for participating. 


    You claim that the fair payment schedule for a situation with infinite money and linear utility function is  about $5 for 8 games, and that the Steinhaus sequence helps estimate this. This is clearly wrong. I have shown the fair payment for 8 games exceeds $16 when the payout is finite, and so is always <=  the St Petersburg case. It makes no sense to claim that the fair payment to enter the St Petersbug case is less than the Russell case.  If the Steinhaus sequence estimates anything to do with the St Petersburg lottery, it is something more like the median payout or other similar non-linear and bounded measure which you then take as the fair price to enter. 

    So my claim is that the fair price to enter the St Petersburg lottery with 8 games is either >=$16 or undefined depending on how you view things, but is not about $5. What repeatable process can you show to dispute this?

    Thor Russell
    Johannes Koelman
    OK, now if you do that [time average the result], then the time average is undefined and unbounded.
    Absolutely not. The payoff over any finite number N of subsequent games is finite. Each and every single game gives a finite pay-off (albeit on occasions only after a long time), so the aggregate payoff  for a finite number of games is also finite.

    We can make all of this more precise, based on the work by Steinhaus: a fair price for playing N games behaves asymptotically as N log2 N + O(N). A well-behaved amount. No infinities whatsoever.
    how do you even define the "fair price" to enter with x games? It seems to me you can't even define it, not talk about it if you do this.
    See above.
    If you happened to get a run of about 128, 64, 64, 8, 8, 8, with increasing games, you wouldn't have plotted that in the blog post, and have it totally not fit the curve, but rejected it as non-typical. So there is some kind of ensemble median like process going on when you decide that some results are typical and should be plotted.
    I haven't observed a run where the payoff decreases with increasing number of games. Of course this could happen given the large fluctuations occurring, but it is very unlikely.

    I am not hiding anything, and I invite you to upload in your next comment a dozen or so payoff time averages. Just take the 12 plots that emerge when you run your simulation. Let's then talk how credible is a log2 N term in the time average payoff for N subsequent games.
    OK I think definitions are in order. According to me, a game must have a finite expectation value to even be considered for ergodic vs non-ergodic. If it is infinite, it is neither ergodic or non-ergodic, it is undefined and such concepts only mislead. Applying logic that is correct for a non-ergodic case when in fact you are dealing with infinities is like dividing by zero to me. You get wrong answers.
    This is just wrong. The correct definition for ergodicity is as given in the above blog article: "Ergodicity means that one can replace time averages with ensemble averages". If a game with finite time averages has divergent ensemble averages, it is per definition non-ergodic.  
    I have shown the fair payment for 8 games exceeds $16 when the payout is finite, and so is always <= the St Petersburg case. It makes no sense to claim that the fair payment to enter the St Petersbug case is less than the Russell case. 
    No, you haven't.

    You have to be very careful in the limiting procedure in going from Russellburg lotteries to Petersburg lotteries. You can use 100,000 repeats of an 8 game Russellburg lottery to determine a fair entry fee for an 8 game Russellburg lottery. You can also use your 100,000 x 8 Russelburg results to suggest a lower bound to the entry fee for an 800,000 games long Petersburg game. But you can't straightforwardly translate these 800,000 Russellburg results into a lower bound for an 8 game Petersburg lottery.
    Thor Russell
    There are several things I can disagree with here, but I think definitions are the sticking point. It comes down to how "fair value to enter" or "fair price" is defined. To me "fair value" should be defined as the ensemble average. If the ensemble average diverges, then there is no fair value. However it is clear that this is not your definition.
    So what is your definition of "fair value"? What is the completely specified and reproducible method for calculating it? To me you are using some kind of ill-defined intuitive definition that implies some kind of median measure but you don't acknowledge it. Note I am asking a general definition of "fair price" or "fair value to enter" that should apply to both the erogdic and non-erogodic cases. You certainly cannot just define fair price to be the Steinhaus sequence. That is obviously circular.

    You need to define fair price in the general case, supply a fully specified method of calculating it. You have mentioned uploading 12 cases, so go further and fully specify how many cases to upload and the calculation you are going to do on them, and what you claim that shows. The MEDIAN payoff of those 12 simulations will probably follow the N + log2N formula, but I am not disputing that. 

    Thor Russell
    Johannes Koelman
    Fair value should avoid ensemble averging and is best defined following William Feller:

    The cost Cn for n games is fair if it balances the stochastic return Rn over n games in the sense that for any  > 0 the probability that |Rn/Cn - 1| <  approaches one when n grows without bound.
    Thor Russell
    I can't see any way how this definition supports your claims.
    1. Define stochastic return. It sounds like it implies ensemble average, but if this is not what you mean, then define how is it calculated.
    2. It seems like you are confusing the definition of game here. This definition sounds quite strange when applied to our case. Please show how it applied to our case, because I think there are different things being assumed for words here.


    e.g Applying your definition:
    The cost C8 of 8 games in the St Petersburg lottery is determined by the stochastic return R8 (which is undefined) in the sense that an equation converges as n->infinity?? This doesnt make sense, the value of R8 shouldn't depend on what happens as n->infinity. The cost of 8 games can't depend on the number of games because it is already fixed. It seems clear that in this definition "n" means "run" not game. Please explain how this is properly defined and applied, and put your calculations into it.
    Thor Russell
    Johannes Koelman
    I think you are over-complicating things, do you really want me to spell out all the trivial stuff?
    Ok, here we go:


    1) Establish a value for epsilon. For instance: set epsilon = 0.001. 

    2) Compute Cn, the cost for playing n games. For instance, in a Russellburg game Cn = a n (with the constant a depending on the maximum earning per game) will work. For the Petersburg game, you will need Cn = n log n. 

    3) Play n games, add up the returns. This gives you Rn.


    4) repeat 3) many times and convince yourself that in each case Rn/Cn - 1 is in absolute value smaller than epsilon. 

    Now lower epsilon, increase n, and play around. I hope you get the gist. And no, the repeat of step 3) does NOT represent an ensemble average...

    All of this is well-established and published in the open literature many decades ago. 



    Thor Russell
    No you are confusing two separate things here. You are confusing games and runs. 
    If you want to compute the fair value for the St Petersburg lottery for 8 games, then n is fixed. n should stand for runs, not games in this definition. Lets say we ignore the fact that the number of "games" can vary and have a special case where you can only play 8 "games". So what should you pay to enter in this case? The answer cannot depend on the number of games, that doesn't make sense as it has been fixed and is not a variable.


    Following your steps:
    1. Fix n=8
    You claim the fair value to enter is 5.
    Now what? Your steps don't make sense. Am I just to take one run with n=8 and then extrapolate the fair value from that? Using the values for when n=16,32 ... to estimate the value when n=8 doesn't make sense. f(x) is not calculated by calculating f(2x, 4x ...) then trying to draw a line through the values.
    In many cases Rn/Cn is obviously not meeting your formula. If I do 1e6 runs then what am I supposed to do with the results.

    Once again, supply properly and thoroughly all the steps for calculating n=8. You have not done this, and if you do you should realize the mistakes you are making.
    Thor Russell
    The analysis Johannes refers to is the asymptotic analysis of the repeated game by Feller. In this analysis the variable n does represent the number of repeats in a run (not the number of runs of the repeat game). See the discussion of equation 10 in this recent didactical paper on the paradox:
    http://www.dma.unive.it/quaderni/QD24-2007.pdf
    The beauty of this analysis is that for regular games (with a well-defined ensemble average) it yields a fair value that coincides with the ensemble average. For the Saint Petersburg game it gives a fair value for n iterations of the game is n 2log n.

    Thor Russell
    OK now I see the confusion. The game only becomes asymptotically fair as n->infinity and the price to enter varies depending on the number of games already played. That gives the log(n) formula, however that does not give a fair price to enter when the number of games is fixed. The formula is changing the price per game, NOT giving you a way to price playing 1 game, 8 games etc.
    It does not follow that because the fair price to enter -> n + log(n) as n-> infinity then the fair price to enter when n is fixed at 1 or 8 games is $2 or $5. This formula obviously gives the wrong value in these cases. The fair price to enter when there is just one game, played once is obviously >$2, however the formula says you should only pay $2.
    Thor Russell
    Thor Russell
    OK let me make myself clear:

    1. The game is not non-ergodic.
     
    When it is constrained with a maximum payout of say $1M it is ergodic.  When there is no maximum it is not non-ergodic, because the average payout is unbounded and hence undefined for any number games.
     To understand the unbounded case, first consider the bounded case (only 15 coin tosses ) and the payoffs generated. 
    Here we have a maximum of 15 coin tosses,  (2^16 payoff) and do a number of runs with a certain number of games. 
    For any bounded case (for a given number of games, 15 coin tosses max), there is a well defined distribution of payoffs. It is a non-normal distribution with mean well defined. So for a situation with a fixed number of games, a maximum of 15 coin tosses, lets estimate these values. Simulation is a way of estimating these values, and as the number of simulations tends to infinity, the estimates of these values will converge to the true values. 
    So, simulating with 1 game, with 1e3, 1e4, 1e5, 1e6, 1e7 runs gives the following:

    1 game (runs: payoff)
    1e3:  10.2 1e4:  13.3 1e5:  16.6 1e6: 15.5 1e7: 16.4
     8 games
    1e3:  14.9 1e4:  16.3 1e5:  16.32 1e6: 16.38 1e7: 16.5
    64 games
    1e3:  17.5 1e4:   17.8 1e5: 16.6 1e6: 16.6
    512 games
    1e3: 16.1 1e4: 16.4 1e5: 16.4 1e6: 16.5

    The average payoff is about 16.5 for all these cases as estimated by the value with 1e6/7 runs. The number of games does not affect the average payoff, however the simulation converges on the true value faster with more games as expected. 

    There is no log graph with payoff increasing with number of games in the bounded case. HOWEVER it appears that way because of a sampling artifact. Most of the time the average estimated payoff will be less than the true one, and more so when there are fewer games. This is because the distribution is very non-normal with few values clustered at the higher end. This is a property of the estimation method NOT the game itself however!
    The fact that it fits a log curve is not an endorsement of the Steinhaus method, rather a compounding of errors cancelling out to some extent. 
    Now what happens as you increase the number of coin tosses per game allowed? Well, the average expectation increases and does so without bound as expected. However at no stage does it become a non-ergodic game. The expectation is not affected by the number of games chosen, but by the number of coin tosses allowed. If the number of coin tosses tends to infinity, then the expectation becomes unbounded and hence undefined, therefore it is also not non-ergodic as it is not even defined.

    So where you say: "that there is a term N included in the payoff per game"
    No: when the game allows an infinite number of coin tosses, the payoff is unbounded for all number of games, therefore undefined. When there is a finite number of coin tosses, the payoff is the same for all number of games, however a sampling artifact causes you to believe it depends on the number of games.

    2.Resolving the paradox:

    Any "paradox" involving infinity and money is immediately resolved by noting that "money" implies finite. Money stands for something, therefore there must be a finite amount of it for it to be money. A currency with an infinite amount of  units in circulation would be worth nothing. An "infinite amount of money" is self-contradictory as money is defined in our society. So to get rid of an apparent paradox, just use the maximum amount of money in the world or some similar measure as a bound, then calculate. e.g, the maximum payoff is $100 trillion even if you win all the tosses. So without non-linear utility functions, this paradox and several others are immediately resolved by this method. That's it.

    3. The Steinhaus sequence is misleading and has no bearing on this actual problem.

     It is implied that you start at the beginning with one run of one game, and with larger runs get larger values because you progress to larger numbers, but that is incorrect. A single run of one game is like picking a point on the infinite Steinhaus sequence. It could be any power of 2. Likewise with 100 games, it is like picking 100 unrelated points from an infinite line. Laying the numbers out like this does not resolve anything, only misleads. Yes the Steinhaus sequence is non-ergodic when started at the start, however this has no bearing on the st Petersburg paradox as it is not the same thing. Points are picked at random in the St Petersburg case. 
    Note that to get the non-ergodicity implied, you need some kind of memory from one game to the next, in the Steinhaus sequence that is the case as you go from one point to the next, however in the St Petersburg paradox, there is no such correlation or memory. One game could give, 2, the next 1024, the next 2^324 without visiting the 2's in-between.

    Thor Russell
    Johannes Koelman
    Thor -- you are imposing a maximum pay-off per game (or equivalently, a maximum number of coin tosses per game), which creates an entirely different game. To keep the discussion clear, I will refer to this game as the 'Russellburg lottery'

    The Russellburg and Petersburg games behave entirely differenly.

    Firstly, the Russellburg lottery has a finite ensemble average (finite expectation value), and therefore there is no paradox in the Russellburg lottery. Contrast this with the Petersburg lottery which clearly has an infinite ensemble average (at least that we agree!).

    Secondly, the Russellburg lottery will show a transient behavior: an increasing pay-out per game played, followed by a levelling off. This leveling off makes the game ergodic. This is no artifact, but rather a feature induced by the Russellburg lottery (the pay-out per game at which levelling off takes place can be associated with the maximum pay-out per game). The Petersburg lottery never levels off, and is therefore non-ergodic (by definition).

    Play long sequences of the Petersburg lottery (rather than the Russellburg lottery), and you will see that there is no leveling off.
    Thor Russell
    Yes I am proposing a maximum payoff per game, and then letting that payoff tend to infinity. As that maximum tends to infinity, then the Russell lottery tends to the Petersburg lottery. 
    I do not know what you mean by not leveling off meaning non-ergodic by definition. I understand not leveling off alright, but then claiming that unbounded allows or implies non-ergodic doesn't make sense.

    Surely for the average payout per game to depend on the number of games, the average payoff must be defined! The average payoff for 1 game, (or 5,10 etc) in the St Petersburg lottery is undefined, so to say it depends on the number of games is nonsense. 
    If you say that f(x) is undefined for all x, then you cannot in any meaningful way say that f(x) has a log(x) term in it. 

    That is the point, the average payoff for 64 games is not about 8 as shown in your graph, it is unbounded.  My limited payoff game clearly shows that the average payoff for 64 games is greater than 8. As the max payoff per game increases, (and the Russell lottery becomes like the Petersburg one) so does the average payoff for 64 games. Your data point of an average payoff of around 8 for 64 games is clearly wrong. The average payout in the Petersburg case for 64 games must EXCEED the average payout for 64 games in the Russell case. Therefore the average payout for 64 games in the Petersburg case is > 8. Claiming that it is less is like claiming 1+1+1=3, 1+1+1+1+1=5, but 1+1+1...=2. Are you really claiming that in the infinite case, the process somehow becomes "non-ergodic" and the average payoff for 64 games drops, even though the payout for any given game is >= the Russell case.

    Note that the median however is defined. e.g. the median of [1 1 1 infinity] is 1, but the mean/std are undefined. The median payoff of St Petersburg is defined, finite, and changes with the number of games played, and is therefore non-ergodic. This is more like what your simulation is showing, not the mean (when you present simulations in a blog post, you imply they are "typical". Yes they are "typical" but of the median, not the mean). The mean/std are unbounded for all number of games however.
    Thor Russell
    This post is simply wrong.

    You say:
    For the St. Petersburg lottery where one wins $2 with probability 1/2, $4 with probability 1/4, $8 with probability 1/8, etc. the expected dollar gain is

    (1/2) 2 + (1/4) 4 + (1/8) 8 + (1/16) 16 + ... = 1 + 1 + 1 + 1 + ... = infinite

    That statement is incorrect. Probability does not work that way. The probability of winning $2 includes also includes the probability of winning more. In other words, you cannot win $4 without winning $2 first. That equation would only be valid if the events were discrete, but since they are not discrete events, the equation is nonsense.

    This causes you to make a false conclusion:

    Therefore, the ensemble average, aka the expectation value for the game, can be cast aside as a meaningless divergent quantity.
    That statement is false because you have not in fact computed the expectation value for the game! That equation is NOT the expectation value for the game!

    In particular, the probability of winning exactly $2 is 1/2 minus the sum of probabilities of winning more than $2.

    If we denote P(x) the probability of winning more than x, then the correct equation for the expectation value of the game is:

    (1/2 - P(2)) 2 + (1/4 - P(4)) 4 + (1/8 - P(8)) 8 + ... = non-infinite

    Johannes Koelman
    Suggest you take a good night sleep and read the post again...
    I suggest you read my additional comment if you still don't understand your mistake. What you call an expectation equation is not an expectation equation, which is the source of the paradox. It has nothing to do with time averages vs ensemble averages. Your expectation equation does not compute an average at all. In this respect it is quite similar to the Monty Hall problem, which has the same flaw in the assumed probabilities for non-independent events.

    Never mind. You're right, I'm wrong, it's correct to calculate the expected value that way. You're also right that I need more sleep. Yikes.

    Hank
    ha ha ... we knew something you did not know.  Johannes has a Nobel Prize in Awesome.  And he is never wrong.
    Johannes Koelman
    And he is never wrong.
    Showed this to my spouse. Half an hour later the echos of her laughter are still bouncing around our house...
    Actually, even my own expectation equation is wrong.

    The chance of winning exactly $4 is the chance of winning more than 2 subtracted by the chance of winning more than 4.

    The chance of winning more that $2 is 1 - (1/2 - P(2)) = 1/2 + P(2)
    The chance of winning $4 is therefore 1/2 + P(2) - P(4)

    So the expectation value equation is:
    (1/2 - P(2)) 2 + (1/2 + P(2) - P(4)) 4 + (1/2 - P(2) + P(4) - P(8)) 8 + ... = non-infinite

    Anyway, the point is, your expectation equation is wrong, which is why it gives an absurd answer. You can only calculate an expectation that way if the events are discrete (ie independent). The discrete events are winning exactly $2, winning exactly $4, winning exactly 8$, etc.

    1/2 is the probability if winning $2 or more. 1/4 is the probability of winning $4 or more. 1/2 is not the probability of winning exactly $2. 1/4 is not the probability of winning exactly $4.

    So your expectation equation is wrong. For x = 2, 4, 8, ...., you are multiplying the sum of winning exactly $x by the probability of winning x$ or more, which is not a valid expectation equation. A valid expectation equation would be multiplying the sum of winning exactly $x by the probability of winning exactly $x.

    Ole Peters has a paper on exactly this topic, and he agrees 100% with Johannes' analysis of the St Petersburg Paradox:

    http://arxiv.org/pdf/1011.4404v2.pdf