Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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
add comment

2 Answers

up vote 2 down vote accepted

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

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.