Renyi Entropies and Large Deviations for the First Match Function

Author(s)

Abadi, Miguel Natalio ^[1] ; Cardeno, Liliam ^[2]

Affiliation

^[1] Univ Sao Paulo, Inst Matemat & Estat, BR-05508070 Sao Paulo - Brazil

^[2] Univ Antioquia, Inst Matemat, Medellin 51922 - Colombia

• Document type: Journal article
• Source: IEEE TRANSACTIONS ON INFORMATION THEORY; v. 61, n. 4, p. 1629-1639, APR 2015.
• Web of Science Citations: 4

Abstract

We define the first match function T-n : C-n -> [1, ... , n] where C is a finite alphabet. For two copies of x(1)(n) is an element of C-n, this function gives the minimum number of steps one has to slide one copy of x(1)(n) to get a match with the other one. For ergodic positive entropy processes, Saussol and coauthors proved the almost sure convergence of T-n/n. We compute the large deviation properties of this function. We prove that this limit is related to the Renyi 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. (AU)

• FAPESP's process: 13/07699-0 - Research, Innovation and Dissemination Center for Neuromathematics - NeuroMat
• Grantee: Oswaldo Baffa Filho
• Support Opportunities: Research Grants - Research, Innovation and Dissemination Centers - RIDC