Autocorrelation (words)

In combinatorics, a branch of mathematics, the autocorrelation of a word is the set of periods of this word. More precisely, it is a sequence of values which indicate how much the end of a word looks likes the beginning of a word. This value can be used to compute, for example, the average value of the first occurrence of this word in a random string.

In this article, A is an alphabet, and ${\displaystyle w=w_{1}\dots w_{n}}$ a word on A of length n. The autocorrelation of ${\displaystyle w}$ can be defined as the correlation of ${\displaystyle w}$ with itself. However, we redefine this notion below.

The autocorrelation vector of ${\displaystyle w}$ is ${\displaystyle c=(c_{0},\dots ,c_{n-1})}$, with ${\displaystyle c_{i}}$ being 1 if the prefix of length ${\displaystyle n-i}$ equals the suffix of length ${\displaystyle n-i}$, and with ${\displaystyle c_{i}}$ being 0 otherwise. That is ${\displaystyle c_{i}}$ indicates whether ${\displaystyle w_{i+1}\dots w_{n}=w_{1}\dots w_{n-i}}$.

For example, the autocorrelation vector of ${\displaystyle aaa}$ is ${\displaystyle (1,1,1)}$ since, clearly, for ${\displaystyle i}$ being 0, 1 or 2, the prefix of length ${\displaystyle n-i}$ is equal to the suffix of length ${\displaystyle n-i}$. The autocorrelation vector of ${\displaystyle abb}$ is ${\displaystyle (1,0,0)}$ since no strict prefix is equal to a strict suffix. Finally, the autocorrelation vector of ${\displaystyle aabbaa}$ is 100011, as shown in the following table:

Note that ${\displaystyle c_{0}}$ is always equal to 1, since the prefix and the suffix of length ${\displaystyle n}$ are both equal to the word ${\displaystyle w}$. Similarly, ${\displaystyle c_{n-1}}$ is 1 if and only if the first and the last letters are the same.

The autocorrelation polynomial of ${\displaystyle w}$ is defined as ${\displaystyle c(z)=c_{0}z^{0}+\dots +c_{n-1}z^{n-1}}$. It is a polynomial of degree at most ${\displaystyle n-1}$.

For example, the autocorrelation polynomial of ${\displaystyle aaa}$ is ${\displaystyle 1+z+z^{2}}$ and the autocorrelation polynomial of ${\displaystyle abb}$ is ${\displaystyle 1}$. Finally, the autocorrelation polynomial of ${\displaystyle aabbaa}$ is ${\displaystyle 1+z^{4}+z^{5}}$.

We now indicate some properties which can be computed using the autocorrelation polynomial.

Suppose that you choose an infinite sequence ${\displaystyle s}$ of letters of ${\displaystyle A}$, randomly, each letter with probability ${\displaystyle {\frac {1}{|A|}}}$, where ${\displaystyle |A|}$ is the number of letters of ${\displaystyle A}$. Let us call ${\displaystyle E}$ the expectation of the first occurrence of ?${\displaystyle m}$ in ${\displaystyle s}$? . Then ${\displaystyle E}$ equals ${\displaystyle |A|^{n}c\left({\frac {1}{|A|}}\right)}$. That is, each subword ${\displaystyle v}$ of ${\displaystyle w}$ which is both a prefix and a suffix causes the average value of the first occurrence of ${\displaystyle w}$ to occur ${\displaystyle |A|^{|v|}}$ letters later. Here ${\displaystyle |v|}$ is the length of v.

For example, over the binary alphabet ${\displaystyle A=\{a,b\}}$, the first occurrence of ${\displaystyle aa}$ is at position ${\displaystyle 2^{2}(1+{\frac {1}{2}})=6}$ while the average first occurrence of ${\displaystyle ab}$ is at position ${\displaystyle 2^{2}(1)=4}$. Intuitively, the fact that the first occurrence of ${\displaystyle aa}$ is later than the first occurrence of ${\displaystyle ab}$ can be explained in two ways:

• We can consider, for each position ${\displaystyle p}$, what are the requirement for ${\displaystyle w}$'s first occurrence to be at ${\displaystyle p}$.
  • The first occurrence of ${\displaystyle ab}$ can be at position 1 in only one way in both case. If ${\displaystyle s}$ starts with ${\displaystyle w}$. This has probability ${\displaystyle {\frac {1}{4}}}$ for both considered values of ${\displaystyle w}$.
  • The first occurrence of ${\displaystyle ab}$ is at position 2 if the prefix of ${\displaystyle s}$ of length 3 is ${\displaystyle aab}$ or is ${\displaystyle bab}$. However, the first occurrence of ${\displaystyle aa}$ is at position 2 if and only if the prefix of ${\displaystyle s}$ of length 3 is ${\displaystyle baa}$. (Note that the first occurrence of ${\displaystyle aa}$ in ${\displaystyle aaa}$ is at position 1.).
  • In general, the number of prefixes of length ${\displaystyle n+1}$ such that the first occurrence of ${\displaystyle aa}$ is at position ${\displaystyle n}$ is smaller for ${\displaystyle aa}$ than for ${\displaystyle ba}$. This explain why, on average, the first ${\displaystyle aa}$ arrive later than the first ${\displaystyle ab}$.
• We can also consider the fact that the average number of occurrences of ${\displaystyle w}$ in a random string of length ${\displaystyle l}$ is ${\displaystyle |A|^{l-n}}$. This number is independent of the autocorrelation polynomial. An occurrence of ${\displaystyle w}$ may overlap another occurrence in different ways. More precisely, each 1 in its autocorrelation vector correspond to a way for occurrence to overlap. Since many occurrences of ${\displaystyle w}$ can be packed together, using overlapping, but the average number of occurrences does not change, it follows that the distance between two non-overlapping occurrences is greater when the autocorrelation vector contains many 1's.

Autocorrelation polynomials allows to give simple equations for the ordinary generating functions (OGF) of many natural questions.

• The OGF of the languages of words not containing ${\displaystyle w}$ is ${\displaystyle {\frac {c(z)}{z^{n}+(1-|A|z)c(z)}}}$.
• The OGF of the languages of words containing ${\displaystyle w}$ is ${\displaystyle {\frac {z^{n}}{(1-|A|z)(z^{n}+(1-|A|z)c(z))}}}$.
• The OGF of the languages of words containing a single occurrence of ${\displaystyle w}$, at the end of the word is ${\displaystyle {\frac {z^{n}}{z^{n}+(1-|A|z)c(z)}}}$.

• Flajolet and Sedgewick (2010). Analytic Combinatorics. New York: Cambridge University Press. pp. 60-61. ISBN 978-0-521-89806-5.
• Rosen, Ned. "Expected waiting times for strings of coin flips" (PDF). Retrieved 3 December 2017.
• Odlyzko, A. M.; Guibas, L. J. (1981). "String overlaps, pattern matching, and nontransitive games". Journal of Combinatorial Theory. Series A 30 (2): 183–208. doi:10.1016/0097-3165(81)90005-4.