Solving a difference equation for coin toss sequence probabilities

Question

I want to solve the following difference equation:

$$b_n-b_{n-1} = \frac{1}{8}(1-b_{n-3})$$

I tried to solve it similar to the solution of Fibonacci sequence here, but when I try to assume the solution will be of the form $l^n$, I end up with the following polynomial:

$$l^{n-3}(l^3-l^2+\frac{1}{8}) = \frac{1}{8}$$

Unlike in the Fibonacci sequence, we don't get a polynomial equation that can be easily solved and independent of $n$.

Any other strategy to solve this?

---

The reason I care about this difference equation is that it describes the probability I will get two consecutive heads on the $n$th toss of a fair coin.

Let $a_n$ be the probability that I'll reach two consecutive heads on the $n$th toss.

We know that at the time when I reach my goal on the $n$th toss, the last two tosses I saw would have both been heads.

Also, the third-from-final toss would have had to be a tails (otherwise, I would have won one toss earlier). The probability of this sequence of THH is $\frac{1}{2}\times \frac{1}{2} \times \frac{1}{2} = \frac{1}{8}$.

Before these three tosses, my probability of winning would have been by definition, $a_{n-3}$. But if I am to win in the $n$th toss, I need to exclude that event. And similarly $a_{n-4}$ and so on. This means:

$$a_n=\frac{1}{8}\left(1-\sum_{i=1}^{n-3} a_i\right)$$

Now let's define:

$$b_n = \sum_{i=1}^{n} a_i$$

which represents the probability you would have won by the $n$th toss.

Plugging this equation into the previous one we get:

$$b_n-b_{n-1} = \frac{1}{8}(1-b_{n-3})$$

Answer 1

The homogeneous part of $b_{n}−b_{n−1}=\frac{1}{8}(1−b_{n−3})$ is given by: $$8b_{n}-8b_{n-1}+b_{n-3}=0$$

So the characteristic equation is given by:

$$8l^3-8l^2+1=0$$

The roots are given by $l=\frac{1-\sqrt{5}}{4}, \frac{1+\sqrt{5}}{4},\frac{1}{2}$

And the answer can be taken as a constant: $b_n=c$. Substituting in $$8b_n+8b_{n-1}-b_{n-3}=1$$ We have $c=\frac{1}{15}$

Therefore the general solution can be written as:

$$b_n=\sigma_1\left(\frac{\sqrt{5}+1}{4}\right)^n+ \sigma_2\left(\frac{1-\sqrt{5}}{4}\right)^n+\sigma_3\left(\frac{1}{2}\right)^n+\frac{\sigma_4}{15}.$$

And for the two consecutive heads problem, we can use the first few values in the sequence $b_n$ in particular, $b_0=0$, $b_1=0$, $b_2=0.25$ and $b_3=0.375$ to get $\sigma_1 = -1.1708$, $\sigma_2=1.708$, $\sigma_3=0$, $\sigma_4=15$

Answer 2

I have another approach to this I just worked out. Here, we try to use express the recurrence as a system of linear equations. Then, we leverage the eigen values of the matrix associated with the matrix of this linear system.

So far, we have only one equation. This is:

$$b_n -b_{n-1} + \frac{1}{8}b_{n-3} = \frac{1}{8}$$ To form a linear system, we need two more equations. Let's take some dummy equations. $$b_{n-1}=b_{n-1}$$

$$b_{n-2}=b_{n-2}$$

Now, we can express this system in matrix form.

$$\left( \begin{array}{c} b_n \\ b_{n-1}\\ b_{n-2}\\ \end{array} \right) = \left( \begin{array}{ccc} 1 & 0 & -\frac{1}{8} & \\ 1 & 0 & 0\\ 0 & 1 & 0\\ \end{array} \right) \left( \begin{array}{c} b_{n-1} \\ b_{n-2}\\ b_{n-3}\\ \end{array} \right) + \left( \begin{array}{c} \frac{1}{8} \\ 0\\ 0\\ \end{array} \right)$$

Now let: $\beta_n = \left(\begin{array}{c} b_n \\ b_{n-1}\\ b_{n-2}\\ \end{array} \right)$, $\gamma = \left(\begin{array}{c} \frac{1}{8} \\ 0\\ 0\\ \end{array} \right)$ and $M = \left( \begin{array}{ccc} 1 & 0 & -\frac{1}{8} & \\ 1 & 0 & 0\\ 0 & 1 & 0\\ \end{array} \right)$.

We then get:

$$\beta_n = M \beta_{n-1} + \gamma$$ $$=M(M \beta_{n-2}+\gamma) + \gamma$$

$$=M^2 \beta_{n-2} + (I+M)\gamma$$

Extending this all the way we get:

$$\beta_n = M^{n-2}\beta_{2} + (I+M+M^2+ \dots + M^{n-3})\gamma$$

Now, assuming $M$ is diagonalizable (which it is) we can say:

$$M=E\Lambda E^{-1}$$ And this would imply: $$M^n = E \Lambda^n E^{-1}$$

So we get: $$\beta^n = E\Lambda^{n-2}E^{-1}\beta_2 + E(I+\Lambda+\Lambda^2+\dots+\Lambda^{n-3})E^{-1}\gamma$$

Now, if $\lambda_1$, $\lambda_2$ and $\lambda_3$ happen to be the eigen values of $M$ then, $$\Lambda = \left( \begin{array}{ccc} \lambda_1 & 0 & 0 & \\ 0 & \lambda_2 & 0\\ 0 & 0 & \lambda_3\\ \end{array} \right)$$

and,

$$(I+\Lambda+\Lambda^2 + \dots + \Lambda^{n-3}) = \left( \begin{array}{ccc} \frac{1-\lambda_1^{n-2}}{1-\lambda_1} & 0 & 0 & \\ 0 & \frac{1-\lambda_2^{n-2}}{1-\lambda_2} & 0\\ 0 & 0 & \frac{1-\lambda_3^{n-2}}{1-\lambda_3}\\ \end{array} \right)$$

Using these, it is easy to see that:

$$\beta_n = c_0 + c_1 \lambda_1^{n-2} + c_2 \lambda_2^{n-2} + c_3 \lambda_3^{n-2}$$

And the eigen values happen to be: $\lambda_1, \lambda_2, \lambda_3 = \frac{\phi}{2}$, $\frac{1-\phi}{2}$, $0.5$.