The non-central limit theorem for the auto-correlation function
ABSTRACT
We consider a stochastic process over a finite or countable alphabet.
We introduce the auto-correlation function that makes
occurrences of a given observable (in space or time), appear in clusters or
isolated.
When the observables are “words”,
we compute the exact distribution and the limiting distribution of this
function when the sequence is generated by iid random variables.
We also give a point-wise upper bound for the velocity of this convergence.
Further, we show how this function gives a measure of the complexity of the
process and can be used to determine the complexity of graphs.
We illustrate with some examples.