# Consecutive letters

• Feb 9th 2010, 02:43 AM
nahduma
Consecutive letters
There is a sequence of ten letters, consisting of two letters A and T, with equal probabilities for both.

What is the probability that there will be atleast two As consecutively?
• Feb 9th 2010, 04:07 AM
awkward
Quote:

Originally Posted by nahduma
There is a sequence of ten letters, consisting of two letters A and T, with equal probabilities for both.

What is the probability that there will be atleast two As consecutively?

Hi Nahduma,

It's probably easier to find the probability that the sequence does not contain two consecutive A's, then subtract from 1.

There are $\displaystyle 2^{10}$ sequences of 10 letters each of which is an A or a T, and all the sequences are equally likely.

Let's see if we can count the number of sequences which do not contain two consecutive A's. More generally, let's see if we can count the number of sequences of length n which do not contain two consecutive A's; call this number $\displaystyle a_n$. For brevity, let's say a sequence is "acceptable" if it does not contain two consecutive As.

It's easy to see that
$\displaystyle a_1 = 2$ and
$\displaystyle a_2 =3$.

Now suppose we have an acceptable sequence of length n+1 where n > 2. Break the possible sequences into two classes depending on whether the last letter is an A or a T. If the last letter is a T, then the preceding n letters can be any acceptable sequence; there are $\displaystyle a_n$ of these. If the last letter is an A, then the nth letter must be an T, but the first n-1 letters can be any acceptable sequence; so there are $\displaystyle a_{n-1}$ of these. Consequently,

$\displaystyle a_{n+1} = a_{n-1} + a_n$

Using this equation and what we already know about $\displaystyle a_1$ and $\displaystyle a_2$, you should be able to compute $\displaystyle a_{10}$. Then the probability that a sequence of length 10 does not contain two consecutive As is

$\displaystyle a_{10} / 2^{10}$,

and the probability that it contains at least two consecutive As is

$\displaystyle 1 - \frac{a_{10}}{2^{10}}$.

P.S.: Here's something for you to think about: What has all this got to do with the Fibonacci numbers?