Consider the following game. We start with the empty string and then repeatedly choose one of the following three actions uniformly at random with the same probability of occurrence(1/3 each) :
- Append an $\mathtt{A}$ to the end of the string.
- Append a $\mathtt{B}$ to the end of the string.
- Remove the last symbol from the string (or do nothing if the string is empty).
Main question. How many steps on average does it take until the string is exactly $\mathtt{ABBB}$?
Bonus question. How many steps on average does it take until the string contains $\mathtt{ABBB}$ as a substring? for instance: $\mathtt{BBAABBBA}$
P.S.I gave this problem a try and what I realized could be summed in this way: 1-the number of actions has got to be an even number greater or equal to 4. 2- Then try and add two actions(by adding and removing an undesired letter. 3-Count how many desired strings can be constructed after following steps 1 and two. 4-Then calculate the weighted average of the numbers above. but the problem is it is an infinite series and I'm not sure whether it's a convergent series or not. by the way, this is my initial thoughts which might be severely distorted!