4
$\begingroup$

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 ?.
$\endgroup$

1 Answer 1

3
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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? $\endgroup$ Aug 18, 2020 at 6:38

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .