St. Petersburg paradox | Hacker News Reader

St. Petersburg paradox

en.wikipedia.org

144 pointsgmac74 comments

Infinity can be difficult to grasp.

Fortunately, there is a huge difference between "infinite" and "really large," which is often key. So applying these results to the real world often doesn't work out.

As the Wikipedia article points out, although the expected value of the game is infinite if the casino has infinite money, it's not only finite but quite small if the casino has finite money. Even if the casino were backed by the entire world GDP, the expected value of the game is only around $50.

This to me is a satisfying resolution to the problem presented.

Not only that, but the most common outcome is $2. The median is $3. The chance of winning $1024 is less than 1/10th of a percent.

Even if the house had unlimited resources, it'd be hard to convince me to pay a large amount of money to play -- assuming I could only pay once.

I fully agree with this simple observation. If you have below $1M in your pocket, then there is no point to pay more than $1K for the game unless you are a gambler because probability of win is low (not expected value but probability) even with multiple runs. On the other hand if I had $2M spare money, then I would happily invest $1K in each of 1000 runs even if casino only had $10M in the bank. I would not spend $1M for a single run.

These analyses mostly ignore the obvious fact that the value of infinite money isn't, in fact, infinite, because eventually you'd run out of things to buy. Using the aggregate wealth of the entire world (which is probably in the neighborhood of $250 trillion[1]) as a bankroll yields a expected value of about $50.

[1] http://blogs.reuters.com/felix-salmon/2014/04/04/stop-adding...

That's somewhat covered in the "Expected utility theory" section of the Wikipedia article. In short, if you double your money it doesn't double the usefulness you get out of it, so you have to take that into account.

However, that analysis assumes that additional money always adds some additional usefulness, and then you can make the problem reappear. To get rid of it entirely you have to declare that there is some point beyond which provides zero additional value no matter how much more money you add. And as you say, such a point surely exists.

To get rid of it entirely you have to declare that there is some point beyond which provides zero additional value no matter how much more money you add.

No, you merely have to declare that there is some amount of utility which can never be obtained no matter how much money you have. (Or as the Simpsons put it: There's one thing you can't buy: A dinosaur.)

In mathematical terms, if your utility function is f(x) = 1 - 1/x, every marginal dollar adds utility; but the added utility is never enough to make the gamble profitable.

Oh but you can but a dinosaur - a dead one. Given enough money you could potentially clone one too.

Utility function analysis is arbitrary just as the article says. Compare this to ergodic theory (used for proper dynamic system analysis), where you can clearly derive the value function over number of plays, including infinite number.

What an ergodic process is you can see here: https://en.wikipedia.org/wiki/Ergodic_process By computing the limit of the ensemble average you will derive the logarithmic utility function. This works for finite resources as well, but then you can also derive the time it takes to bankrupt the bank, as well as probability of that ever happening.

To rephrase your observation, the human utility function might have a maximum. Imagine the best day of your life; now imagine every day of your future life was this good, even a bit better, and that you live a rather long life. If you're altrustic, you can even imagine this number multiplied by the Earth's population. If you're a sci-fi fan/futurist, you can even imagine this number multiplied by the number of expected planets in the universe, multiplied by the amount of time until the stars burn out (as an aside, this is extremely optimistic because it's highly unlikely that even with arbitrarily large wealth that you would be able to figure out how to spend it in such a way to give every person a perfect life until the end of the universe). There's a good chance that you can't get much better than that, no matter how wealthy you became.

The paradox wants you to imagine that, for very small probabilities, you can get utilities indefinitely large. The paradox wants you to say, I'll devote my entire life to earning as much money as possible and spending it all on this game because the payoff is so large that this is worth it for the tinest chance. But if there's an upper bound on the human utility function, then this doesn't work. It doesn't work because when you imagine how happy you'd be with arbitrarily large wealth, you don't imagine an arbitrarily large utility, you imagine the "max utility" situation described above where every day is like the best day of your life, which is nice but not as nice as would be required to justify almost certainly throwing your life away for a small chance of this.

If you were paying 50$ to play this game, you would have to play around 2^50 (each time paying 50$) times to even break even! I think the article is a good illustration of how expected value can't be really used as the only parameter.

Expected value is limit at infinity. Instead, you should use ergodic theory expected value, which takes number of plays into account. Then the result is a simple log function.

It is debatable which is the more unlikely out of the two premises "The entire world puts up their GDP for a year to back the game against a player paying $50" and "The game is played around 2^50 times".

I thought it was even more satisfying that the number given by Ian Hacking (few of us would pay even $25 to enter such a game) turned out to be near what the equation would give you for a realistic casino bankroll ($16M < W < 34M).

Infinite return would also take infinite time to toss the coins.

Indeed, and modern economics as a discipline goes out of its way to keep everything finite. I was going to post the same thing: that the finite version solves this problem completely.

The only case where economics cannot avoid dealing with infinite quantities, is with dynamic issues, since most models assume that various quantities though finite at a given point, could grow without bound (e.g. GDP). One case this comes up is in debt, especially national debt. Most models posit a transversality/"no ponzi" condition, that states that the present value of debt at time t will converge to zero as t goes to infinity. On the other hand, if national debt was a constant proportion of GDP (which in the long run should grow at the same rate as the risk free interest rate) then this would in fact be false, and national debt is a kind of free money that comes out of nowhere, i.e. a real ponzi scheme.

Imposing a finiteness condition (e.g. and end to the universe) would imply that in the far future, some generation will pay for current consumption that is based on either national debt, or the corresponding internal borrowing from future generations (e.g. social security as understood in the overlapping generations model). That is why, in my opinion, it is completely wrong to say that household finances don't apply to government. The only difference is the kind of consumption and investment being done, but the financial constraints are identical.

I think the problem is with the assumption that expected wins are a good guide of behavior at the granularity of individual plays of the game.

The expected win is infinite because very rare scenarios have huge payouts. However, any one play of the game has a 50% chance of paying out nothing. If I get to play the game a large enough number of times for the rare scenarios to actually occur, then I would be willing to pay a higher price than if I only got one shot at it.

The way I read the rules, there's no chance of a zero payout. You're guaranteed at least $2, if the first toss comes up tails. So you should be willing to pay at least $2 to enter, since if the first toss comes up heads, you're then on for a chance to win at least $4.

Sure. The question is more like, should you be willing to pay $1 million to play? And honestly, if you can't afford to burn $1 million, that would be a pretty bad idea.

However! Suppose you were allowed to modify things ever so slightly. Suppose you get to say, "Sure, I'll pay $1 million to play. But instead of playing once and taking my winnings, I want to play a million times, and only take one millionth of whatever I win each time." You haven't done anything to change the average payout of the game. But you've made it a much better idea to play, by reducing the variance.

That's what it means to say the game has infinite expected value. You really should be willing to pay anything to play it, as long as you're allowed to repeat the game over and over.

Of course, if you're stuck with playing the game just once, then lots of games look like a bad idea despite having a positive expected value. The St. Petersburg game is hardly alone here. For example, suppose you have a 1-in-a-million chance of winning $10 billion, but it costs $1000 to play. Should you play? The expected value is good, but I don't think most people would touch it. Not much of a paradox there.

Actually, for the 1/1,000,000 chance of GBP 10,000,000,000 then GBP 1,000 seems OK? My EV is GBP 10,000 or 10.0 times my stake, which is _much_ better that buying 1,000 lottery tickets at GBP 1.00 each, for a 1/14,000 chance of GBP 10,000,000 (nominal; neglecting rollovers) and an EV of GBP 714.28 (approximately) which is an under unity gain (0.71 of the stake returned). However using the Kelly criterion for placing bets, I think it turns out that even though the return is high for the ten billion wager, you should only place the GBP 1,000 bet if you have a bankroll of 1,000,000,000 already ;( Corrections to my maths welcome!

> For example, suppose you have a 1-in-a-million chance of winning $10 billion, but it costs $1000 to play. Should you play?

I'd happily take those odds.

It's not only the odds but the magnitude of the bet that matter. Because losing $1000 wouldn't bother you much, you're happy to do it. But scale the proposition up enough, perhaps 10^3, and you wouldn't be so relaxed about it. E.g. 1-in-a-million chance of winning $10 trillion, but it costs $1 million to play.

Do you think that maximizing expected utility in general is not how a rational person should act? If yes, how do you deal with https://en.wikipedia.org/wiki/Von_Neumann%E2%80%93Morgenster...?

Expected utility is great, expected money is silly.

I don't think that's enough to solve this problem. If you replace money by utility, it seems like it would still be a paradox.

On of the failings of decision theory is our 'utility functions' are not necessarily static. The most obvious case being people don't necessarily order the same thing every time they go to a restaurant.

Arguably you could model this with hidden variables. So: A mathematician might go to vegas and spend 1,000$ gamboling with the expectation that they will lose that money. With novelty being the reason that becomes a reasonable trade-off.

In that context maximizing expected utility becomes hard because you can't accurately model your utility function.

>>The expected win is infinite because very rare scenarios have huge payouts.

Not quite. The expected win is infinite because of the one single scenario where the games continues on an infinite basis.

The average win is approx $46 if the bankroll is all the money in the world.

Thinking about the one single scenario where it goes on forever, as if it were an event unto itself, is misleading imo -- by that reasoning, in that scenario, you would win an infinite amount even if you were only getting paid $1 on each flip. But the EV is clearly not infinite for that game. The increasingly huge rare payouts are essential to the EV calc.

Yes, I think so too. Tumblr user su3su2u1 wrote a post which argued the same thing in more detail: http://su3su2u1.tumblr.com/post/120899546078/resolving-the-s...

At least for me, the comparison to the expected payouts of the "finite versions" completely resolves the paradox. People aren't used to reasoning about infinities, especially when dealing with such tangible quantities as money. Very large and very small numbers confuse us. It's no wonder that when faced with astronomically large payouts at infinitesimal probabilies, our intuition disagrees with "the math". We think about money intuitively in terms of scales that are meaningful in the real world. We can't imagine playing against a casino with $10^100, so we would not be willing to pay $330 to play, which would be the expected payoff for such a casino.

On a related note, we don't have a way of measuring the value of money beyond quantities we subconsciously label " all the money". Is it better to have $10^90 or $10^100? In the computation of the expectation, the difference is crucial. To a human player, there is no distinction.

$10^90 and $10^100 are identical since both would represent 99.9999...% of all dollars. Spending just a small fraction would flood the market and decrease the value of USD. Consequently, unless you have a large military at your disposal, the U.S. government will come after you regardless of the money's legality since you represent a threat to the monetary system.

Presumably, with that amount of cash you could buy enough political power that the US military would be on your team

I don't have infinite money and time to play this forever. And there is a certain probability that I will lose $10, $100 or $1000 and have to stop playing because I no longer can or want to afford it. I wouldn't mind losing $10 with near certainty but I would only play if I had a good chance to win some money before losing $1000 and having to stop. And I would not risk losing $1000 if the expected gain is small, say $100, or if I had to play the entire day to get there. Probably not to easy to quantify but certainly doable.

You only pay a fixed sum at the beginning to play. The question is, what is the upper bound on that fixed sum, and why is it so much smaller than your expected winnings?

You pay the fixed sum before every game. If you go with Ian Hacking's suggested low price of $25, I can easily see losing several thousand dollar before you get lucky and hit one of the rare, high value events.

You have to pay for every game. Half of the time you win $2 which means half of the time you lose $3 if a game costs $5.

(you've misunderstood the description.)

Correct, half the time you win $2, but what happens the other half of the time?

With the other half... half of the time you win at least $4. With the other half of that... half of the time you win at least $8. With the other half of that... half of the time you win at least $16.

So, if you simulate the average winnings in a single round, you get data like this:

[8, 2, 8, 2, 8, 32, 8, 8, 4, 4, 2, 4, 4, 16, 2, 2, 16, 4, 8, 2]

Which even with losses of $3 and $1 for most games still works out to a $44 profit at $5 game.

However, and this is the point of the paradox, if you run the numbers for 100 rounds, you start to see average winnings per round like:

[6.48, 6.6, 15.68, 10.02, 10.26, 17.04, 5.86, 11.96, 8.92, 7.34, 6.56, 17.14, 9.92, 9.64, 11.48, 12.44, 19.64, 171.42, 12.82, 5.9]

So if you had played those 20 times, at $5/game * 100 rounds you would have a $27,000 profit on $10000.

If I pay 2 dollars to play, I have a 50% chance each game of at least breaking even and being able to continue playing.

If I pay 4 dollars to play, I have a 25% chance each game of at least breaking even and being able to continue playing.

The minimum payout is $2. You have 100% chance each game of at least breaking even if you pay $2 to play.

I ran a quick simulation assuming that the banker and the player both start with $100 and the game ends when either party gets to $0. It seems like the break-even entry fee is somewhere around $5.50, anything higher and the player almost always loses first. If the banker has more money than the player, it only makes the possibility of the player winning smaller. And even if the player has more money than the banker, they may have to play hundreds of games to come out ahead. This game doesn't seem very fun.

> I ran a quick simulation assuming that the banker and the player both start with $100 and the game ends when either party gets to $0.

Why are you modeling it that way? Nothing in the game requires that a player spend the bank to $0.

You might be looking for the Kelly criterion. It provides a quantitative answer to what percent of your bankroll you should bet, given the characteristics of a game. Roughly, it tries to avoid having you run out of money before you start winning.

So an answer to the paradox is that some people, like yourself, have intuition about the Kelly criterion: that they should limit the portion of their bankroll that they bet.

In a way this is like waiting for a good black swan event to happen. It is going to happen and it will be great, but do you have enough money to play long enough till it happens? I think we don't play this kind of game for the same reason we are bad preparing for black swan events. If I spent huge amounts of money on preparing for a black swan disaster that might happen chances are still high that I will only get theoretical benefits from the investment and nothing ever happens during my lifetime. Similarly here, I statistically win, but in practice I have a high chance of running either out of money or out of time, because I don't have infinite of those, even if the imaginary casino had infinite money.

> It is going to happen and it will be great, but do you have enough money to play long enough till it happens?

I think this can also be said as "The market can remain irrational longer than you can remain solvent".

I wrote up a quick version of this in python (assuming I read it right).

Rather than try to keep track of profit and loss it just plays for 1000 rounds and figures out the max cost per game that would have broken even. There's different ways of doing it obviously.. like assign actual values to starting money and cost per game and then play until a 20% profit or bankruptcy.

From what I see for 1000 rounds, paying $6 would mean a profit 100% of the time. Also, average breakeven should probably take the 90th percentile.

  #!/usr/bin/env python3
  import random
  
  def play():
      profit = 2
      while True:
          if random.choice([0,1]):
              return profit
          profit *=2
  
  def simulate():
      profit = 0
      plays = 0
      max_win = 0
      threshold=10
  
      for i in range(1, 1001):
          win = play()
          profit += win
          max_win = max(win, max_win)
      print("Round: {}, win: {}, Max win: {}, profit: {}, Breakeven cost: {:0.2f}".format(i, win, max_win, profit, profit/i))
      return profit/i
  
  def avg(l):
      return sum(l) / len(l)
  
  def main():
      breakevens = []
      for _ in range(1000):
          be = simulate()
          breakevens.append(be)
  
      print("Lowest breakeven cost: {:0.2f}".format(min(breakevens)))
      print("Average breakeven cost: {:0.2f}".format(avg(breakevens)))
      print("Highest breakeven cost: {:0.2f}".format(max(breakevens)))
  
  if __name__ == "__main__":
      main()

The classic solution is that $s are not equal to utility. People have some discount rate. But you can trivially rephrase the problem, so the $ increase at the same rate of your discount rate, and you get the same problem.

Only a bounded utility function is a solution - there must be some amount of money where literally even a trillion dollars more doesn't matter.

That seems acceptable, but it still means this game is worth some amount to play, and that amount can still grow very large before reaching your bound. Also there must be some things which we can't bound.

There is a very related problem called Pascal's Mugging: http://wiki.lesswrong.com/wiki/Pascal's_mugging

In Pascal's mugging, a mugger asks you to pay him $5, or he will kill 3↑↑↑3 people (an incomprehensibly huge number, that for all intents in purposes, might as well be infinity.) He says that he is the matrix lord and likes playing games with simulated people.

This is of course, incredibly unlikely. But is the probability he is telling the truth greater than 1/3↑↑↑3? Is $5 worth more than a human life? If so you should pay him.

This is a general problem with expected utility. EU only cares about the average utility. The utility of all the possible outcomes, weighted by their probability. A single outlier can throw the average case off a lot.

EU is forced to trade away utility from the majority of probable outcomes to really weird unlikely outcomes, like the mugger, or winning an infinite series of coin flips. EU is optimal in most everyday problems, but it can fail in extreme cases.

The problem with the original lottery is that most of its value is from high-EV tiny-probability events, e.g. the 2^{-50} probability of winning 2^50 dollars. The practical result of that event does not seem to be worth 2^50 utilons, to say the least. It is hard to think about events worth that many.

However, many perturbations of this lottery can actually be good bets.

For example, suppose you gain 3^n dollars with probability 2^{-n}. Then you have a 1/128 chance of winning $2187, a 1/256 change of winning $6561, and this game starts looking much nicer.

The "Pascal's Mugging" divergence is a different problem, where Solomonoff-style priors imply negative-exponential probabilities of Busy-Beaverish payoffs. Ordinary priors don't really have this problem.

It seems like the same class of problems, because they are both about high payoff, low probability bets. Solomonoff induction is just a formalization used to show the result is very general.

Any reasonable prior should have similar cases. Unless you really believe the mugger being a matrix lord has 0 probability, or that God has 0 probability, etc, you are forced to act as if they are true. Which results in wasted effort in the vast majority of possible outcomes, in exchange for a massive payoff in incredibly rare outcomes.

Assigning 0 probability is not something you should do lightly. It would mean you could wake up and find yourself outside of the matrix, and you still would not believe it had any chance of being true. It would mean God himself could come to and say "yeah it's all real." And you would be forced to believe there is still 0 probability he exists.

Assigning a finite value is a classic "Black Swan" fat-tail misapprehension. How much you would pay to play it is only one side of the equation; the other is how much you would charge to allow someone else to play it.

Our inability to reason about infrequent events means that a casino that plays this game may look like a very attractive proposition, because in practice (finite small-scale simulation) the expected payouts are quite reasonable. So it would behoove the casino to leverage itself up to its eyeballs to maximize the return on investment.

While the numbers for the "finite versions" part of the article seem quite reasonable, it's easy to forget that when leverage comes into play, a game like this can not only bankrupt the casino, but can ripple back to all of the investors (lenders) as a loss that far exceeds the profits in the history of the casino.

Even better, as any casino would be quickly bankrupt by playing this game multiple times, even without leverage. The small payoffs quickly add up.

This is why all games of chance have a "bank wins" feature.

I believe the equation used on the page is wrong. It states projected winnings as 1/2 x $2 + 1/4 * $4 + ... But you only have a 1/4 chance of winning $2, since have the time you get a heads on first flip, you also get a heads on the second flip, meaning you'll win more than $2.

The equation should be: 1/4 x $2 + 1/8 x $4 ...

Still goes to infinity, but at half the pace.

Why not edit it with the correct equation? Wikipedia needs you!

I think if you get tails on the first flip you still get the $2 payout.

You're right! Turns out Wikipedia doesn't need me after all.

This is essentially the flip side to the more banal paradox of the casino itself: the expected value of casino games are strictly negative for the player, but people choose to play them anyway. In the case of the St Petersburg game, the variance means that you're far more likely to lose money than win it in a single game, despite the highly positive EV; in the case of the casino, the variance means that you can often walk out ahead after playing roulette for an hour or two despite the slightly negative EV.

Also, there is another point I want to make, lot of readers assume that they can only play it once. I dont think that is a constraint at all. If that is a constraint, problem is simplified. If you were to play only once you have less than 1/(amount) chance of seeing your investment or more.

If you invested 1024$ (10 successive head rolls), you have less than 1/1024 chance of seeing it back.

Of course, you start from 2$ and not 0$ (I have simplified a few things to drive the point).

There is nothing in the game about 1024/being 10 rolls. You pay X to enter tge game on start, then you roll up to infinitely many times, and the paradox is what X should be.

It is tricky. The expected value is mathematics term people invented for easy calculation. It is different from the "value" in human perception.

How much is a $1 lottery ticket worth? It is probably 40 cents depending on the probability. It's worth zero for all the people who lose and millions of dollar for the luck one. There is no "between" value which is what expected value represents.

How long does each coin flip take, and how soon can I repeat the game? Does each flip takes an equal and finite amount of time? Do subsequent flips take half as much time? Can I play Graham's number of games in an hour? An countable infinite number of games in an hour? If we're wondering about "most people" they might be sub-consciously taking the time factor into account.

Log utility is a fairly extreme way of discounting huge rewards. A less extreme way is to consider that there is only so much money or wealth in the world, on the order of $100T. Huge payouts would require printing more money, reducing the relative value of all money. So a linear utility function for a finite world looks like x / (1 + x/$100T).

Another interesting risk analysis problem is where you have a million boxes. All but one box has a fixed sum of money X under it, and the remaining box has a bomb that will kill you if you open it.

How high would X have to be for you to be willing to play the game?

So the conflict of this paradox is that most people will not play this game, but it actually is a worthwhile game to play - if someone were to offer you to play it.

That's not the usual meaning of the word paradox.

The original 1738 paper by Bernoulli:

https://news.ycombinator.com/item?id=9902047

This Platonic idea that just because it works on theory, therefore reality works just the same, is an old misunderstanding.

But before I criticize these "attempts" at solving this problem by these deft mathematicians, I'd like to see a single video example of 10 coin tosses all coming up either heads or tails.

After we can all see that this can happen, then we can start worrying about how much money a casino in the real world would charge for such game being played in the real world, by real players, with real coins.

It is amazing that out of all mathematicians listed on Wikipedia that attempted this, only one considered actually sampling (supposedly simulated coin tosses).

This can be easily simulated, but they'd rather stay within the comfy confines of calculation, so that presumably they can publish more papers.

A coin toss isn't exactly 50% for both sides in a real life scenario, hence the difficulty to reproduce the experiment exactly like its theoretical description. A sequence of 10 coin tosses resulting in heads/tails is not impossible even if it is hard to reproduce, it simply has an absurdly low probability of ocurring.

This focus on the theoretical side of things, the 'comfy confines of calculation', isn't a bad thing, the paradox is still an interesting thought experiment.

The paradox does not depend on the fairness of the coin.

A real coin toss is, say, at least 25% probability for heads and at least 25% probability for tails. Therefore you can multiply the winnings by 4 and not by 2, which will give you a divergent series even with a real, "unfair" coin.

I don't get your idea with sampling. It will work in practice. To see that yourself: write a program that repeats this experiment again and again, compute the averages of the winnings, and you will see that they cannot be bounded by any constant. Or use a real coin and a piece of paper, though this will require a lot of patience.

While it cannot be bound by any constant, it is described by a function over number of tosses. When you introduce an entry price, you will suddenly get negative values in the beginning, and can reason again against expected value over time much better.

Tossing the coins can be useful to help our intuition, but we have a pretty good understanding of how they work, to put it mildly. I think it's fair to assume that a mathematician isn't going to change their mind after a quick experiment.

https://youtube.com/watch?v=rwvIGNXY21Y

And there are several more.

http://www.youtube.com/watch?v=rwvIGNXY21Y

Not that hard to do. Just a matter of perseverance and a bit of luck. Yes, it could be faked, but I trust him.

Similarly, here's another fellow rolling a Yahtzee. https://www.youtube.com/watch?v=fiTwar7mFws

So then, you have an answer for how much a person should be willing to pay to play the game, based on your simulation approach?

If you asked for, say, 40 heads in a row, I could see it. But 10? That's merely a one-in-a-thousand occurrence. Or one-in-five-hundred if you accept either heads or tails.

If only he/she actually bothered to throw coins before writing that comment...

Reply on news.ycombinator.com