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.
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
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.