The expected value of a special coin flips game

Question

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.

Answer 1

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.

1. 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)

2. 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)

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

Answer 2

An exact computation with Mathematica, averaging all possible $1024$ flip sequences, gives: $$ \approx10.8127. $$

Answer 3

This is a good simulation exercise! Below, I repeat a million simulations of this process:

import random
import pandas as pd

import seaborn as sns

def game():
    gains = 100.0
    for flip in range(10):
        if random.randint(0,1) == 0:
            gains += 1
        else:
            gains = 1/gains
    return gains

returns = [game() for i in range(int(1e+06))]

X = pd.Series(returns)

X.describe()

sns.histplot(X, binrange = (0,10), stat = 'probability')

The statistics of the distribution are:

count    1000000.000000
mean          10.808046
std           29.011454
min            0.009174
25%            0.600394
50%            1.600398
75%            3.250620
max          110.000000
dtype: float64

Indeed, the mean is close to $10.8$. And below is a graph of the distribution (higher values with low probability are omitted):