# A game: Fibonacci sequences and probability.

Let's play a game. You have two biased coins: coin A has a $0.4$ and $0.6$ for H and T probability and coin B has the opposite ($0.6$ and $0.4$ for H and T). These coins must be flipped one at a time, regardless of previous result.

Now, start off with $1$ written on a piece of paper, and start flipping with A. Every time you flip one coin and get H, you add 1 to the previous number, w/e the previous number was (in this case, the first number is one. So if you get H on the first try on coin A, you add one to one and if you get T you subtract one and get zero, and so on). However, every time you get T, you not only subtract one, but you also divide by the nth Fibonacci corresponding to the $n$-th flip.

So, flipping one at a time, if this is your $15$-th throw and you get T, you subtract 1 from the number that you got after the $14$-th throw, and you divide this new number by the $15$-th Fibonacci. If you get H, you add one to the $14$-th throw number, and then continue to the $16$-th throw.

What is the probability that the 100th throw ends up with a number greater than 1?

-
What happened to coin B? – Did May 5 '12 at 21:25
@Didier: I suppose on even turns you use coin B and on odd turns you use coin A. – TMM May 5 '12 at 21:35
That's one way to say it. – Nico Bellic May 5 '12 at 22:07

Below is an analysis under the assumption that $100$ is "sufficiently large", to get an approximation of the probability.

Let $S_n$ be the score at time $n$, and $X_n$ be the result of throw $n$. Since the Fibonacci numbers grow exponentially, after many flips, the divisions will kill any growth made. So asymptotically, a tails $X_n = T$ sends a score $S_{n-1} > 1$ to $S_n \approx 0^{+}$ and $S_{n-1} < 1$ to $S_n \approx 0^{-}$, while a heads $X_n = H$ simply sends any number $S_{n-1}$ to $S_n = S_{n-1} + 1$. So the only way to get a score above $1$ at time $n$ is by getting a heads on the flip before that one:

$$P(S_n > 1) \approx P(X_n = H) \cdot P(S_{n-1} > 0).$$

Now to have had a score of at least $0$ on the previous turn, you either needed a heads, or you needed a tails with a score of at least $1$ before that:

$$P(S_n > 1) \approx P(X_n = H) \cdot [P(X_{n-1} = H) + P(X_{n-1} = T) \cdot P(S_{n-2} > 1)]$$

We want to know the probability for even $n = 2k = 100$, and since odd flips are with coin $A$ and even flips with coin $B$, we get

\begin{align} P(S_{2k} > 1) &\approx \underbrace{P(X_{2k} = H)}_{P_B(H)} \cdot [\underbrace{P(X_{2k-1} = H)}_{P_A(H)} + \underbrace{P(X_{2k-1} = T)}_{P_A(T)} \cdot P(S_{2k-2} > 1)] \\ &= 0.6 \cdot [0.4 + 0.6 \cdot P(S_{2(k-1)} > 1)].\end{align}

Assuming $P(S_{2k} > 1) \to p$ for some $p$ and for large $n$, we can write the above as

$$p = 0.6 \cdot (0.4 + 0.6p) = 0.24 + 0.36p.$$

Solving for $p$ gives us $p = 0.375$, so $\color{blue}{P(S_{100} > 1) \approx 0.375}$.

-

Let $x_n$ be the value of the number after the $n$-th throw, with $x_0=1$. Let $p_n$ and $q_n$ be the probabilities that $x_n>1$ and $x_n>0$, respectively. Then for $n>4$ we have:

\begin{align*}p_n&=\begin{cases}0.6q_{n-1},&\text{if }n\text{ is even}\\0.4q_{n-1},&\text{if }n\text{ is odd}\end{cases}\\\\ q_n&=\begin{cases}p_{n-1}+0.6(1-p_{n-1})=0.4p_{n-1}+0.6,&\text{if }n\text{ is even}\\p_{n-1}+0.4(1-p_{n-1})=0.6p_{n-1}+0.4,&\text{if }n\text{ is odd}\end{cases} \end{align*}

The result for $p_n$ follows from the observation that the maximum value of $x_n$ is $n$, and $\frac{n-1}{F_n}\le 1$. The result for $q_n$ follows from the observation that $x_4>-1$.

It follows that

$$p_n=\begin{cases}0.36p_{n-2}+0.24,&\text{if }n\text{ is even}\\ 0.16p_{n-2}+0.24,&\text{if }n\text{ is odd}\;. \end{cases}$$

By actual calculation the first few values of of $p_n$ are $p_0=0$, $p_1=\frac12$, $p_2=\frac14$, $p_3=\frac38$, $p_4=\frac14$, and $p_5=\frac5{16}$, so for $p_{100}$ we want to solve the recurrence $x_n=0.36x_{n-1}+0.24$ with $x_0=0.25$. This is straightforward, and we get $$x_n=\frac38(1-0.36^{n+1})\;.$$

In the present instance we want $$p_{100}=x_{48}=\frac38(1-0.36^{49})\;,$$ which differs from $0.375$ by a little over $6.8\times 10^{-23}$.

In general we have $$p_n=\begin{cases} \frac38\left(1-0.36^{\frac{n-2}2}\right),&\text{if }n\text{ is even}\\\\ \frac38\left(1-0.16^{\frac{n-3}2}\right),&\text{if }n\text{ is odd}\;. \end{cases}$$

-