Average number of moves to have a specific 3-bit pattern

Question

I would like to know how to have the average number of moves to have a specific 3-bit pattern.
It is a random test where the chance of having 0 or 1 is the same: 0.5 (like having a coin toss).
We drag 0 or 1 several times in a row until we have the pattern we are looking for.

The purpose of my problem is to know which pattern has the lowest average number of moves.
So in 3-bit all the patterns are
001, 110,
100, 011,
101, 010,
111, 000.
I maked a program in python to know approximately the average number of moves of each patterns: (here 100)

def jump(p) :
    x=random.random()
    if x<=p :
        s=1
    else:
        s=0
    return s

summi = 0

for j in range(100):

    i = 0

    tab = []

    while True:
        nb = jump(0.5)
        print("Random number", nb)
        tab.append(nb)
        if i > 2 :
            if ( tab[i-2]== 1 ) and ( tab[i-1]== 0 ) and ( tab[i]== 0 ):
                break
        i += 1

    summi += i

print("Average : ", summi/100)

For example for 111: this is ~14 and for 100: this is ~8.

I tried to make probability trees. So I have infinite trees: for example for a pattern of "111" if I have "11" and I add a "0" it is not good and I continue in my tree (this looks more like a graph than a tree).
But I noticed that more simply I could go back to a previous state: if I add a "0" after an "11" then I go back to the root of my tree.
My calculation to have the average number for "111" is then Ex = 1/8*3 + 1/8*(3 + Ex) + 1/4*(2 + Ex) + 1/2*(1 + Ex).
1/8*3 is the path for "111", 1/8*(3 + Ex) is the path to start again after "110", 1/4*(2 + Ex) is the path to start again after "10" and 1/2*(1 + Ex) after "0".

For "111" this is easy but for others such as "100" I don't start from the beginning of my tree. For example for the pattern "100", if I have "10" and I add a "1" I go back to the node where I added a "1" in the "10" : not at the root of the tree.

Here is a drawing of my trees with "P" and "F" (same as "0" and "1"). trees

in high quality: https://ibb.co/T2WdYT1

Answer 1

Your method is generally applicable; you just need to introduce more variables if you have more than one state to fall back to.

For instance, for $100$: Let $E_1$ be the expected number of moves after you've seen a $1$; let $E_{10}$ be the expected number of moves after you've seen a $10$; and let $E$ be the expected number of moves otherwise. Then the expected number of moves when starting from scratch is $E$.

Similarly to how you proceeded, we can set up the following equations:

\begin{eqnarray*} E&=&1+\frac12E+\frac12E_1\;,\\ E_1&=&1+\frac12E_1+\frac12E_{10}\;,\\ E_{10}&=&1+\frac12E_1\;. \end{eqnarray*}

Using the third equation to eliminate $E_{10}$ in the second yields

$$ E_1=1+\frac12E_1+\frac12+\frac14E_1 $$

and thus $E_1=6$. Substituting that into the first equation then yields $E=8$.