Autocorrelation (words)

Short description: In combinatorics, the autocorrelation of a word is the set of periods of this word

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.

## Contents

* 1 Definition
* 1.1 Autocorrelation vector
* 1.2 Autocorrelation polynomial
* 2 Property
* 2.1 First occurrence of a word in a random string
* 2.2 Ordinary generating functions
* 3 References

## Definition

In this article, A is an alphabet, and w=w1…wn a word on A of length n. The autocorrelation of w can be defined as the correlation of w with itself. However, we redefine this notion below.

### Autocorrelation vector

The autocorrelation vector of w is c=(c0,…,cn−1), with ci being 1 if the prefix of length n−i equals the suffix of length n−i, and with ci being 0 otherwise. That is ci indicates whether wi+1…wn=w1…wn−i.

For example, the autocorrelation vector of aaa is (1,1,1) since, clearly, for i being 0, 1 or 2, the prefix of length n−i is equal to the suffix of length n−i. The autocorrelation vector of abb is (1,0,0) since no strict prefix is equal to a strict suffix. Finally, the autocorrelation vector of 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 c0 is always equal to 1, since the prefix and the suffix of length n are both equal to the word w. Similarly, cn−1 is 1 if and only if the first and the last letters are the same.

### Autocorrelation polynomial

The autocorrelation polynomial of w is defined as c(z)=c0z0+…+cn−1zn−1. It is a polynomial of degree at most n−1.

For example, the autocorrelation polynomial of aaa is 1+z+z2 and the autocorrelation polynomial of abb is 1. Finally, the autocorrelation polynomial of aabbaa is 1+z4+z5.

## 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 s of letters of A, randomly, each letter with probability 1|A|, where |A| is the number of letters of A. Let us call E the expectation of the first occurrence of ?m in s? . Then E equals |A|nc(1|A|). That is, each subword v of w which is both a prefix and a suffix causes the average value of the first occurrence of w to occur |A||v| letters later. Here |v| is the length of v.

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

* We can consider, for each position p, what are the requirement for w's first occurrence to be at p.
* The first occurrence of ab can be at position 1 in only one way in both case. If s starts with w. This has probability 14 for both considered values of w.
* The first occurrence of ab is at position 2 if the prefix of s of length 3 is aab or is bab. However, the first occurrence of aa is at position 2 if and only if the prefix of s of length 3 is baa. (Note that the first occurrence of aa in aaa is at position 1.).
* In general, the number of prefixes of length n+1 such that the first occurrence of aa is at position n is smaller for aa than for ba. This explain why, on average, the first aa arrive later than the first ab.
* We can also consider the fact that the average number of occurrences of w in a random string of length l is |A|l−n. This number is independent of the autocorrelation polynomial. An occurrence of 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 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 w is c(z)zn+(1−|A|z)c(z).
* The OGF of the languages of words containing w is zn(1−|A|z)(zn+(1−|A|z)c(z)).
* The OGF of the languages of words containing a single occurrence of w, at the end of the word is znzn+(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". https://www2.bc.edu/ned-rosen/public/CoinFlips.pdf.
* 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.

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Autocorrelation (words). Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Autocorrelation_(words)&oldid=312892"