%0 Journal Article
%T A characterization of eventually periodicity
%A Teturo Kamae
%A Dong Han Kim
%J Computer Science
%D 2014
%I arXiv
%X In this article, we show that the Kamae-Xue complexity function for an infinite sequence classifies eventual periodicity completely. We prove that an infinite binary word $x_1x_2 \cdots $ is eventually periodic if and only if $\Sigma(x_1x_2\cdots x_n)/n^3$ has a positive limit, where $\Sigma(x_1x_2\cdots x_n)$ is the sum of the squares of all the numbers of appearance of finite words in $x_1 x_2 \cdots x_n$, which was introduced by Kamae-Xue as a criterion of randomness in the sense that $x_1x_2\cdots x_n$ is more random if $\Sigma(x_1x_2\cdots x_n)$ is smaller. In fact, it is known that the lower limit of $\Sigma(x_1x_2\cdots x_n) /n^2 $ is at least 3/2 for any sequence $x_1x_2 \cdots$, while the limit exists as 3/2 almost surely for the $(1/2,1/2)$ product measure. For the other extreme, the upper limit of $\Sigma(x_1x_2\cdots x_n)/n^3$ is bounded by 1/3. There are sequences which are not eventually periodic but the lower limit of $\Sigma(x_1x_2\cdots x_n)/n^3$ is positive, while the limit does not exist.
%U http://arxiv.org/abs/1404.4416v1