# Expected value of game when flipping a coin

You start off with \$$$10,000$$. You flip a fair coin. • If you get heads, you get paid \$ $$1$$.
• If you get tails, you pay your friend half your current money.

What is the expected amount of money you have after $$n$$ rounds ?.

So let's define the initial amount as $$x_{0} = 10000$$. Then in round 1, we expect $$x_{1} = {1 \over 2}\left({x \over 2} + x + 1\right)$$ Note in round $$1$$, we could have $$2$$ possible values for $$x_{1}$$. $$5000$$ and $$10,001$$. So in round $$2$$, we could have $$4$$ possible values. So clearly at round $$n$$, we have $$2^{n}$$ possible values, all with equal probability.

Now this is one of the parts that I think I'm doing correctly, but don't know how to justify. To simplify things, I am claiming that instead of having $$2^{n}$$ possible values in round $$n$$, we have a single value, which is the average of the $$2^{n}$$ values. So, for example, I can collapse the $$2$$ values for round $$1$$ into $$\left(10001 + 5000\right)/2 = 7500.5$$. Then by doing so, it becomes clear that our recursion is

$$x_{n} = {1 \over 2}\left({x_{n - 1} \over 2} + x_{n - 1} + 1\right)$$

1. My first question is: how can I justify the "collapsing" ?. If you write out a few terms, you'll see that $$x_{n} = 0.75^{n}\, x_{0} + \sum_{i = 0}^{n - 1}0.75^{i} \times 0.5$$
2. My second question is, am I done here, or do I need to prove that the simplified $$x_{n}$$ that depends only on $$x_{0}$$ holds by induction ?. I found this formula by writing out a few items, and eyeballing/inducing things because there's a very clear pattern, so I feel like that's enough proof ?.

Your idea is correct. To justify it, you can appeal to the tower rule, since the conditional distribution of $$X_n$$ given $$X_{n-1}$$ is given to you. $$E[X_n] = E[E[X_n \mid X_{n-1}]] = E[0.5(X_{n-1}/2 + X_{n-1} + 1)] = \frac{3}{4} E[X_{n-1}] + \frac{1}{2}.$$
• This is the same as writing $E[X_n] = E[X_n | X_n = X_{n-1} / 2] Pr(X_n = X_{n-1} / 2) + E[X_n | X_n = X_{n - 1} + 1] Pr(X_n = X_{n - 1} + 1)$ right? Aug 18, 2020 at 6:38