3
$\begingroup$

The St Petersburg paradox is a hypothetical game. The pot starts at \$1. A fair coin is flipped and if it is heads, the pot doubles, if it's tails, the player takes the pot. The game has a certain cost to enter, $c$ and we assume that the house has unlimited funds.

The probability of winning a particular amount of money is simply $1/2^{\log_2(x)}$ where $x$ is the amount you want to win. You can show by induction that any sequence of games that leads to a total of $x$ winnings has the same probability, that is you could win 4 heads in one game or 2 heads in two games with the same overall odds. This also applies to winning amounts that are not powers of two (i.e. you would need multiple games to win the amount exactly).

My question is then how do I work out the probability of not losing after $n$ games given some amount of money $w$ and a cost $c$?

Or equivalently suppose the player has $y$ dollars and can therefore play $y/c$ games, what are the odds that the player can keep playing forever?

I know the answer for $w = 10^9$ and $c = 15$ to be around 96%, but I don't know why.

There are some useful hints here:

Calculating the median in the St. Petersburg paradox

Playing the St. Petersburg Lottery until I lose everything

But I haven't been able to figure out how to use the results from those answers.

$\endgroup$
  • $\begingroup$ Interesting question. My intuition is that there won't be a closed-form solution to this that doesn't involve the Lambert $W$ function, but I wouldn't swear to that at the moment. $\endgroup$ – Brian Tung Dec 15 '15 at 22:54
  • $\begingroup$ en.wikipedia.org/wiki/Gambler%27s_ruin is relevant at least $\endgroup$ – Greg Martin Dec 18 '15 at 19:56
  • $\begingroup$ How do you know that the answer is around $96\%$? Read it on reddit? I'm getting a significantly lower figure as a ballpark estimate. $\endgroup$ – A.S. Dec 24 '15 at 9:36
  • $\begingroup$ It's the answer to a crossword, I have other answers which I know are correct and the number provided fits. The answer is given to about seven dp so I'm fairly confident the number on Reddit is correct because it fits all the other answers. Plus, the literature suggests that the longer you play, the less chance you have of making a loss. $\endgroup$ – Josh Dec 24 '15 at 17:01
  • 1
    $\begingroup$ projecteuler.net/problem=499 Looks familiar. $\endgroup$ – Patrick Feltes Dec 25 '15 at 19:18
1
$\begingroup$

Variables:

$c$ = cost to enter

$d$ = amount of dollars remaining

We consider the function $f(d)$, whose value is the chance of losing if you have $d$ dollars remaining.

The answer to this question consists of three approximations:

1) We designate a really high value $w$, the sure-win value. We assume that $f(x) = 0$ for $x > w$ (or $f(x) = \left(\frac{c-1}{c}\right)^x$, if you wanna be that precise).

2) Starting with $f(0)$, we recursively compute the value of $f(d)$, in terms of $f(x)$ for $x>d$.

3) Once we have computed $f(d)$ for all $0\leq d\leq w$ in terms of $f(x)$ for $x>d$, then we can go back and compute the exact value of $f(d)$ for $0\leq d\leq w$.

The answer to OP's question will be $f(10^9)$. This will be a lower bound on the chance of losing; the exact answer can be approximated by either

  • making $w$ arbitrarily high, or
  • once the curve direction for $f(x)$ is clear from the first iteration of the above steps, estimating $f(x)$ for $x > w$ (instead of setting $f(x)$ to be =0) will give a more precise answer for the second iteration. Repeatedly iterating this process with new approximations for $f(x)$ should yield an answer of arbitrarily high precision.

For simplicity, we allow to play as long as a player has a non-negative amount of money remaining; the player is broke when he has a negative amount of money remaining. This is clearly equivalent to the standard setup.

Step 1: Recall: $f(x)$ = chance of eventually losing everything if you start with $x$ dollars; so $f(x) = 1$ for $x<0$.

Define the function $g(x) = \frac{1}{2}f(x+1) + \frac{1}{4}f(x+2) + \frac{1}{8}f(x+4) + ...$ to be the expected value of losing if you have $x$ dollars after having payed for one round. Since we assume $f(x)$ has a closed form for $x>w$, then this function can be written as a finite sum.

Step 2: Using the fact that $f(x) = g(x-c)$, we can compute $f(x)$ for small values. For example, if $b=\lceil$log$_2c\rceil$ = the number of heads you need to get at least $c$ dollars from the pot, then $f(0)$ becomes: $$f(0) = g(-c) = (1 - \frac{1}{2^b}) + \frac{1}{2^{b+1}}f(2^b-c) + \frac{1}{2^{b+2}}f(2^{b+1}-c) + \cdots$$

We recursively compute $f(x)$ for all $0 < x < w$. Any time in the expression for $f(x)$ there occurs $f(y)$ for $y<x$, then since we have computed $f(x)$ in terms of higher terms, we can simply replace those occurrences with the corresponding higher terms (starting with the lowest $y$). In terms of statistics, this can be thought of as a random walk, with a huge $w$ x $w$ transition matrix.

Step 3: In the end, we will have computed $f(w-1)$, which will be in terms of $f(x)$ for $x \geq w$, so will have an exact value. We can then use the expressions we got in Step 2 to compute $f(x)$ for repeatedly decreasing values of $x$.

I am sure this can be explained a lot more cleanly; but, I was not able to get an exact value without approximation.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.