We are playing a game. You start with $£100$. I shall flip a fair coin. If the coin comes up heads, you add $£1$ to your previous sum of money. If it comes tails the sum you have gets inverted, i.e. if you have $£x$, your sum becomes $£(1/x)$ (£100 goes to $£0.01$, $£0.5$ to $£2$ and so on).
What is the expected amount of money you will end up with after 10 consecutive coin flips?
My attempt:
I have no idea how to solve it analytically. The answer is somehow related to Fibonacci sequence.
Best Answer
I got asked this question during an interview once, a super difficult question. I won't be able to give you the perfect answer, just something very close.
Firstly notice that your bankroll is going to be basically one of three things: something very close to $100$, something very close to $1$ or something very close to $0.01$.
We can kind of set up a markovian transition system.
If we are very close to $100$ then we either stay very close to $100$,(by tossing heads) or go to $0.01$. (by tossing tails)
If we are very close to $0.01$ then we either stay very close to $0.01$,(by tossing heads) or go to $100$. (by tossing tails)
We can think of values close to $1$ as absorbing states, as adding $1$ and taking the recipricol does nothing to stop us being close to $1$.
Let us build up from small cases, imagine we have only $1$ toss.
It should be clear that one outcome leaves us close $100$ and one outcome leaves us close to $0.01$.
Imagine we have $2$ tosses instead.
$HH$ and $TT$ leave us close to $100$
$HT$ leaves us close to $0.01$
$TH$ leaves us close to $1$
Imagine now we have $3$ tosses, we can take any toss that left us close to $100$ in $2$ tosses and just add another head, or we can take any toss that left us close to $100$ in $1$ toss and add $TT$.
Let $g(n)$ denote how many "good" tosses we have for $n$ coins (tosses that end us close to $100$ ) we see then that $g(n) = g(n-1) + g(n-2) $
Just using this alone we see that $g(n)$ denotes the $n^{th}$ fib number and so $g(10) = 89$. This gives us a decent lower bound of the expectation if we only really bother about our winnings when its $100$, we see that $\mathbb{E}[W] \approx \frac{89}{2^{10}} \cdot 100 \approx 8.69$
We are definitely going to want to consider how many "fine" states there are, tosses that end in us close to $1$, naturally because this is an absorbing like state it will account for many of the tosses.
It is hard to calculate this directly instead we will find $b(n)$ that denotes the number of bad tosses, values that are close to $0.01$.
We again see a fib series, any good toss in $n-1$ coins plus a tails, or any bad toss in $n-1$ coins plus two tails results in a bad toss in $n$ coins, this gives us a slightly shifted fib series and $b(n) = (n-1)^{th}$ fib number.
Putting it together we have $g(10) = 89 , b(10) = 55, f(10) = 2^{10} - (89+55) = 880 $
And so $\mathbb{E}[W] \approx \frac{89}{2^{10}} \cdot 100 + \frac{880}{2^{10}} \cdot 1 \approx 9.5$
Polishing up the approximation:
It should be clear that this is a strictly lower bound, as when we are "close to $100$ " we always have any even number from $100$ to $108$ , a decent guess would be to take the average, $104$.
When we end "close" to $1$ we can loosely speaking end near $\frac{1}{2}, \frac{1}{3}, ... , 1,2,3 ... , 9$ it is very hard to end near higher numbers like $7,8$ and $9$. A decent guess at the average "fine" end is 2.
Using these values instead we get about $10.75$ which is pretty close to the actual value of about $10.8$