Expected value of money left from a coin flipping game

Question

Say we were to play a game. We started off with \$100 and kept flipping a fair coin. If it turned out heads, we won \$1, else our money got inverted. For example, if on the first flip we got heads, then we'd have \$101. And if we got tails, we'd have \$0.01. What is the expected value of the money we have after N flips?

One way to think about it is to use recursion, i.e. to find the recursive relation between f(n) and f(n-1), where f(n) is the expected money after n flips. Without too much effort we can find: $$f(n) = \frac{1}{2}(f(n-1)+1) + \frac{1}{2f(n-1)}$$ However, if we use this relation, we'll have our money go down exponentially fast, which goes against common sense.

For example, if we use the above relation, starting off with \$100, after 7 flips, we'll have around \$1. But a simple computer simulation shows it should be slightly above \$18.

Can anyone help shed some light on this problem?

Answer 1

Expectation is linear but you have a non-linear term ($1/f(n)$, although i believe it should be $1/f(n-1)$, but that's a minor point). What makes you think you can compute expectation $f(n)$ by naively plugging in expectation $f(n-1)$ into a simple recurrence for the random variable that is non-linear?

In any event, if your current amount of money is a bit large (say, 3 dollars or more) then with probability $ 1- 1/2^k$ you will get the inverse and hence very little on the $k$th flip, and then with probability $1/2$ you will afterwards get close to 1 dollar and then no matter what happens, your amount will stay low with high probability.

Answer 2

When the tails come in pairs, you end with close to \$100. For example, with $n=7$, the following sequences of flips leave you with a large amount of money:

$$\begin{array}{rl} TT\,TT\,TT\,H & $ 101\\ TT\,TT\,H\,TT & $ 101\\ TT\,TT\,H\,H\,H & $ 103\\ TT\,H\,TT\,TT & $ 101\\ TT\,H\,TT\,H\,H & $ 103\\ TT\,H\,H\,TT\,H & $ 103\\ TT\,H\,H\,H\,TT & $ 103\\ TT\,H\,H\,H\,H\,H & $ 105\\ H\,TT\,TT\,TT & $ 101\\ H\,TT\,TT\,H\,H & $ 103\\ H\,TT\,H\,TT\,H & $ 103\\ H\,TT\,H\,H\,TT & $ 103\\ H\,TT\,H\,H\,H\,H & $ 105\\ H\,H\,TT\,TT\,H & $ 103\\ H\,H\,TT\,H\,TT & $ 103\\ H\,H\,TT\,H\,H\,H & $ 105\\ H\,H\,H\,TT\,TT & $ 103\\ H\,H\,H\,TT\,H\,H & $ 105\\ H\,H\,H\,H\,TT\,H & $ 105\\ H\,H\,H\,H\,H\,TT & $ 105\\ H\,H\,H\,H\,H\,H\,H & $ 107\\ \end{array} $$

There are $F(n+1)$ such “good” sequences of flips, where $F(n)$ is the $n$th fibonacci number, approximately $\frac1{\sqrt 5}\phi^n$ where $\phi\approx 1.618$. For large $n$, this is an insignificant fraction of the space of all flips. But when $n$ is small, say $n=7$, then it is significant. For $n=7$ there are $F(7+1) = 21$ such “good” sequences of flips out of 128. So we can get a very rough estimate that the expected result for $n=7$ is around $$\$100\cdot \frac{21}{128} + \$1\cdot \frac{115}{128} \approx \$17.24$$ which is not too far off from what the computer simulation says.

To get a better estimate, we need to account for the fact that the big winning jackpots exceed \$100 by up to $n$ dollars each, and that when all the tails appear in pairs, plus there is one more tail at the end, (as $H\,TT\,H\,TT\,T$ for example) then we end not with close to \$1 but with close to \$0.

When $n$ becomes large, $2^{-n}F(n+1)\ll1$, because $\phi<2$, so the additional contribution of the lucky flips (and the unlucky flips) becomes insignificant, and the expected return is close to $1$.