Motivated by problems of pattern statistics, we study the limit distribution of the random variable counting the number of occurrences of the symbol a in a word of length n chosen at random in {a,b}*, according to a probability distribution defined via a rational formal series s with positive real coefficients. Our main result is a local limit theorem of Gaussian type for these statistics under the hypothesis that s is a power of a primitive series. This result is obtained by showing a general criterion for (Gaussian) local limi t laws of sequences of integer random variables. To prove our result we also introduce and analyze a notion of symbol-periodicity for irreducible matrices, whose entries are polynomials over positive semirings; the properties we prove on this topic extend the classical Perron-Frobenius theory of non-negative real matrices. As a further application we obtain some asymptotic evaluations of the maximum coefficient of monomials of given size for rational series in two commutative variables.

Local limit properties for pattern statistics and rational models / A. Bertoni, C. Choffrut, M. Goldwurm, V. Lonati. - In: THEORY OF COMPUTING SYSTEMS. - ISSN 1432-4350. - 39:1(2006), pp. 209-235. ((Intervento presentato al 21. convegno Annual Symposium on Theoretical Aspects of Computer Science tenutosi a Montpellier nel 2004.

Local limit properties for pattern statistics and rational models

A. Bertoni
Primo
;
M. Goldwurm
Penultimo
;
V. Lonati
Ultimo
2006

Abstract

Motivated by problems of pattern statistics, we study the limit distribution of the random variable counting the number of occurrences of the symbol a in a word of length n chosen at random in {a,b}*, according to a probability distribution defined via a rational formal series s with positive real coefficients. Our main result is a local limit theorem of Gaussian type for these statistics under the hypothesis that s is a power of a primitive series. This result is obtained by showing a general criterion for (Gaussian) local limi t laws of sequences of integer random variables. To prove our result we also introduce and analyze a notion of symbol-periodicity for irreducible matrices, whose entries are polynomials over positive semirings; the properties we prove on this topic extend the classical Perron-Frobenius theory of non-negative real matrices. As a further application we obtain some asymptotic evaluations of the maximum coefficient of monomials of given size for rational series in two commutative variables.
occurrences; automata; symbol; words
Settore INF/01 - Informatica
2006
Article (author)
File in questo prodotto:
File Dimensione Formato  
tocs_lonati.pdf

accesso aperto

Tipologia: Pre-print (manoscritto inviato all'editore)
Dimensione 451.38 kB
Formato Adobe PDF
451.38 kB Adobe PDF Visualizza/Apri
Bertoni2006_Article_LocalLimitPropertiesForPattern.pdf

accesso riservato

Tipologia: Publisher's version/PDF
Dimensione 341.89 kB
Formato Adobe PDF
341.89 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2434/4784
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 8
  • ???jsp.display-item.citation.isi??? 4
social impact