A friend of mine taught me the following question:
You have a coin. When you toss it up, heads you note $1$, tails you note $0$. Then, tossing it up repeatedly, let's find the average waiting time to get each $111, 011, 101101$.
Let $E(L)$ be the average waiting time to get a sequence $L$.
This question can be solved by drawing tree diagram. For example, you get $$x=\frac12(1+x)+\frac14(2+x)+\frac18(3+x)+\frac18\times3$$ where $E(111)=x$. Then, you get $E(111)=x=14$.
By the same way as above, you get $E(011)=8, E(101101)=74$.
However, this way is not so good for larger sequences. My friend taught me a great way to solve this without any proof.
Suppose that a pattern $L$ has $k$ numbers. Let us say there exists 'a length-$r$-overlap' if the last $r$ numbers of $L$ is equal to the first $r$ numbers of $L$. Then, for $r=1,2,\cdots,k$, a leading number is defined as the following:
$\epsilon_r=1$ if there exists a length-$r$-overlap.
$\epsilon_r=0$ if there doesnt't exist a length-$r$-overlap.
Note that $\epsilon_k=1, E(L)=\sum_{r=1}^k\epsilon_r2^r.$
By using this way, we can get $E(111), E(011), E(101101)$ very easily.
1. Noting $\epsilon_1=\epsilon_2=\epsilon_3=1$, $E(111)=2^1+2^2+2^3=14.$
2. Noting $\epsilon_1=\epsilon_2=0, \epsilon_3=1$, $E(011)=2^3=8.$
3. Noting $\epsilon_1=\epsilon_3=\epsilon_6=1, \epsilon_2=\epsilon_4=\epsilon_5=0$, $E(101101)=2^1+2^3+2^6=74.$
Then, here are my questions.
Question 1 : What is the name of this way? (Is this way famous?)
Question 2 : Could you show me how to prove that the average waiting time can be found by this way?