Advanced Topics · Lesson 10

Autocorrelation and the Guibas–Odlyzko Formula

The autocorrelation word

The avoidance automaton keeps track of every partial match. A second approach records only the ways in which the whole pattern can overlap itself.

For a nonempty pattern $P = P [1 .. m]$ , define its autocorrelation word $α_{P} [1] \dots α_{P} [m]$ by

α_{P} [r] = \begin{matrix} 1 & P [1 .. r] = P [m - r + 1 .. m] \\ 0 & otherwise \end{matrix}

So $α_{P} [r] = 1$ exactly when the length- $r$ prefix and suffix agree. We include $r = m$ , so $α_{P} [m] = 1$ . Write

B (P) = {r : 1 \leq r \leq m, α_{P} [r] = 1}

The autocorrelation word records where a prefix and suffix of 01001 of the same length agree. A 1 marks an overlap; a 0 marks a mismatch.

r	prefix	suffix	α[r]
1	0	1	0
2	01	01	1
3	010	001	0
4	0100	1001	0
5	01001	01001	1

α_P = 01001 B(P) = {2, 5} R_P(X) = X + X⁴

For 01001, the only proper border is 01, so $α_{P} = 01001$ and $B (P) = {2, 5}$ . Two copies of 010 can overlap in a single 0, but not in two positions, because 01 ≠ 10 — that is $α_{010} = 101$ .

The autocorrelation polynomial, indexed by overlap length, is

R_{P} (X) = \sum_{r = 1}^{m} α_{P} [r] X^{r - 1}

For 01001, $R_{P} (X) = X + X^{4}$ .

Two counting identities

Recall that $a_{P} (n)$ counts the length- $n$ words avoiding $P$ . Let $h_{P} (n)$ count the length- $n$ words containing exactly one occurrence of $P$ , which must appear at the end (the first occurrence ends at position $n$ ).

For the first identity, take a word $x$ of length $n$ that avoids $P$ . Appending any of the $k$ letters either keeps the result avoiding $P$ or creates exactly one occurrence, ending at the new final position. Deleting the last letter inverts this, proving $k \cdot a_{P} (n) = a_{P} (n + 1) + h_{P} (n + 1)$ .

For the second, append the whole pattern to $x$ . In $x P$ , look at the shortest prefix ending in $P$ , say $x P^{'}$ . The word $P^{'}$ is a nonempty prefix of the appended $P$ and also a suffix of the occurrence at the end, so $P^{'}$ is both a prefix and a suffix of $P$ . If $r = | P^{'} |$ , then $α_{P} [r] = 1$ and $x P^{'}$ is counted by $h_{P} (n + r)$ . Summing over all such $r$ gives the identity.

For 01001, since $B (P) = {2, 5}$ , the second identity reads

a_{P} (n) = h_{P} (n + 2) + h_{P} (n + 5)

With $x = 010$ , $x P = 01001001$ , whose shortest prefix ending in $P$ is 01001 = x01. Thus $P^{'} = 01$ and $r = 2$ .

Practice

Find the autocorrelation word

What is the autocorrelation word of 0011? Write a 0/1 string.

What is the autocorrelation word of 1110101011? Write a 0/1 string.

Practice this topic →Every quiz from this lesson, at four difficulties.