Rényi Entropies and Large Deviations for the First Match Function
Jun 30, 2015
Miguel Natalio Abadi, Liliam Cardeño
We define the first match function Tn : C^n → {1, ... , n} where C is a finite alphabet. For two copies of x1^n ∈ C^n, this function gives the minimum number of steps one has to slide one copy of x1^n to get a match with the other one. For ergodic positive entropy processes, Saussol and coauthors proved the almost sure convergence of Tn/n. We compute the large deviation properties of this function. We prove that this limit is related to the Rényi entropy function, which is also proved to exist. Our results hold under a condition easy to check which defines a large class of processes. We provide some examples.
The whole paper is available here.
Share on Facebook
