Given a random sequence (say $15$) of numbers I want to find the odds of finding '$90$' and '$09$' in the sequence. Looking at just two numbers in the sequence you have a $\dfrac{2}{10}$ chance of getting a '$9$' or '$0$' as the first digit, followed by $\dfrac{1}{10}$ chance of getting specifically the opposite digit that you need to complete the pair. $\dfrac{1}{10}*\dfrac{2}{10} = \dfrac{1}{50}$. Simple right?
But then I think of the repercussions of a failure case on the next adjacent pair examined in the sequence. If analyzing the first two numbers in the set has failed, it is very likely sequences adjacent to it have failed too because adjacent digits 'share' numbers.
if you have the set $4 \; 5 \; 9 \; 1 \;0 \; 5$, my steps for solving the problem fall apart when you consider that in checking '$4$' '$5$' leads into checking '$5$' '$9$', the $5$ mathematically has been accounted for as a failure and is leading towards this next pair to fail as well.
I haven't taken a probability class so maybe I'm failing to express my logic and perhaps I have some crazy misunderstanding of probability. What is this dependency that I acknowledge and how do I account for it when solving these kind of problems?
Best Answer
Let's call a string of digits "good" (as in good to go) if it ends in a digit between $1$ and $8$, and "bad" if it ends in a $0$ or $9$. Let's let $g(n)$ and $b(n)$ count the number of good and bad strings of $n$ digits that don't have any adjacent pairs $09$ or $90$. It's easy to see that
$$\begin{align} g(n+1)&=8g(n)+8b(n)\\ b(n+1)&=2g(n)+b(n)\\ \end{align}$$
It follows that
$$\pmatrix{g(n)\\b(n)}=\pmatrix{8&8\\2&1}^n\pmatrix{1\\0}$$
The probability that the OP seeks is $p(n)=(g(n)+b(n))/10^n$, or
$$p(n)={1\over10^n}\pmatrix{1&1}\pmatrix{8&8\\2&1}^n\pmatrix{1\\0}$$
An exact formula analogous to the Binet formula for Fibonacci numbers can be obtained by diagonalizing the $2\times2$ matrix. However, the eigenvalues here are
$$\lambda={9\pm\sqrt{113}\over2}$$
so the analogous result is likely to look a little ugly.