The well-known ABRACADABRA problem states (see D. Williams, "Probability with martingales", for example):
a monkey is typing letters A-Z randomly and independently of each other, each letter with probability $1/26$. What is the expected amount of time when the monkey first types ABRACADABRA ?
I am well aware (and there are tons of references on the internet) of the martingale approach to this problem, leading to the expected time of $26^{11} + 26^4 + 26$.
While the connection with martingales is undoubtedly elegant and provides a streamlined answer to this question, I'm still wondering, however, if there are other techniques one can use here ?
For instance, for a similar problem with coin tosses, such as waiting for a particular pattern with heads and tails, one can work out things just by hand (using simple conditioning), if the pattern is short. With longer patterns, that type of brute force approach does not work well.
Although I'm mainly interested in non-martingale based approaches to this type of problems, sharing your insights/intuition on the connection with martingales would also be very welcome.
One approach is through the theory of generating functions applied to finite automata, as described in section I.4.2 of Analytic Combinatorics by Philippe Flajolet and Robert Sedgewick. (The book is available for free in pdf format online.)
Given a pattern $p_1 p_2 \cdots p_k$, we are interested in the number of strings which do or do not contain the pattern. To this end, we define the "autocorrelation vector" of the pattern as the vector of bits $c=(c_0, c_1, \dots , c_k)$ with $c_i = [[p_{i+1} p_{i+2} \cdots p_k = p_1 p_2 \cdots p_{k-i}]]$, where the brackets are Iverson's brackets. Then we define the "autocorrelation polynomial" of the pattern as $$c(z) = \sum_{j=0}^{k-1} c_j z^j$$ For example, the autocorrelation polynomial of ABRACADABRA is $c(z) = 1 + z^7 + z^{10}$.
It can be shown that the ordinary generating function of words not containing the pattern is $$S(z) = \frac{c(z)}{z^k +(1-mz)c(z)}$$ where $m$ is the cardinality of the alphabet, so for the pattern ABRACADABRA the generating function is $$S(z) = \frac{1+z^7+z^{10}}{z^{11}+(1-26z)(1+z^7+z^{10})}$$
The average wait time to the first occurrence of the pattern in a random string is $S(1/m) = m^k \; c(1/m)$.
For the pattern ABRACADABRA, with an alphabet of $m=26$ letters, the average wait time to the first occurrence is $$S(1/m) = 26^{11}+26^4+26$$