5

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?

Siphenx
  • 161
  • One thing I'm noticing what makes his calculation so hard is order of flip matters. Also as pointed out you can't use a recursive equation like you had. Because that is computing a conditional expectation, but given the expected value of n-1 flips gives us no information $E(X_n| E(X_{n-1})$ which doesn't really make sense since $E(X_{n-1}$ is a number not a random variable – Kamster Feb 17 '15 at 18:39
  • Also I'm not completely sur Ed my comment is valid so if anyone things anything wrong please point it out – Kamster Feb 17 '15 at 18:46
  • The recursion for $f(n)$ is not correct. In general, it is not true that $E(1/Y)=1/E(Y)$. – user164118 Feb 18 '15 at 09:53

2 Answers2

4

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

MJD
  • 65,394
  • 39
  • 298
  • 580
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.

user2566092
  • 26,142
  • This is wrong. Note that you can get several tails and still end with a large amount of money. For $N=5$, for example, the sequence $T,T,H,T,T$ finishes with $$101$. – MJD Feb 17 '15 at 18:28
  • I said "with probability $1/2$" you will get close to one dollar after a tail if you started with a decent amount of money. That's not wrong. Of course if the tails come two in a row (which has probability $1/2$ after the first tail, like I said) then you can finish with a large amount of money. – user2566092 Feb 17 '15 at 18:54
  • Sorry, my comment was too strongly worded. I agree with your diagnosis about the problem in the original argument. – MJD Feb 17 '15 at 19:03
  • @MJD No problem. I liked your analysis in your answer. To me the most interesting question is what is $\lim_{n \to \infty} f(n)$? I believe it should be finite and small, somewhere around 1 dollar. – user2566092 Feb 17 '15 at 19:08
  • A lower bound is 1.618..., see http://math.stackexchange.com/questions/1153572/lim-n-to-infty-mathbb-ex-n-for-a-coin-flipping-payoff-problem – user164118 Feb 18 '15 at 10:03