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.

Definition

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.

Autocorrelation vector

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:

a	a	b	b	a	a
a	a	b	b	a	a						1
	a	a	b	b	a	a					0
		a	a	b	b	a	a				0
			a	a	b	b	a	a			0
				a	a	b	b	a	a		1
					a	a	b	b	a	a	1

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.

Autocorrelation polynomial

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

Property

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

First occurrence of a word in a random string

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.

Ordinary generating functions

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)}}}$.

References

• 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.