3
$\begingroup$

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.

$\endgroup$

1 Answer 1

Reset to default
7
$\begingroup$

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$$

$\endgroup$
5
  • $\begingroup$ this is an exciting approach, thanks a lot indeed! I was thinking myself about a possible link to automata. My motivation was based on the use of regex where automata theory is working behind the scenes (say we want to build a regex matching the pattern) and partially on Markov chains (which kind of act like automata) and in case of shorter patterns the machinery of Markov chains can be used as the state space is still small. Now seeing automata in action is exciting! Just a minor comment, I couldn't locate the proof of $m^k c(1/m)$ in the book, although I.34 (p.61) used it in the example. $\endgroup$
    – Hayk
    Oct 20, 2018 at 6:33
  • $\begingroup$ @Hayk that the expected wait time is $S(1/m)$ follows from $E(X) = \sum_{n \ge 0} P(X>n)$, and then $S(1/m) = m^k c(1/m)$ follows by simple algebra from the formula for $S(z)$. $\endgroup$
    – awkward
    Oct 20, 2018 at 12:38
  • $\begingroup$ yes, that was my comment: why is the avg. waiting time equals $S(1/m)$ ? I'm not sure I see the connection of $S$ and $\mathbb{P}(X > n)$ . In any case, I should try to familiarize myself with the connection of the generating function and the pattern matching, and have a more careful look at the chapter of the book . $\endgroup$
    – Hayk
    Oct 20, 2018 at 13:27
  • 1
    $\begingroup$ @Hayk If $S(z) = \sum_n s_n z^n$, then $s_n$ is the number of strings of length $n$ without the pattern. So $s_n / m^n$ is the probability that a string of length $n$ does not contain the pattern, i.e. $s_n / m^n = P(X > n)$ where $X$ is the position of the first occurrence of the pattern. $\endgroup$
    – awkward
    Oct 20, 2018 at 14:13
  • $\begingroup$ ah, so this is how you define $S(z)$, then that makes perfect sense. Thanks a lot again! $\endgroup$
    – Hayk
    Oct 20, 2018 at 14:47

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .