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. BertoniPrimo
;M. GoldwurmPenultimo
;V. LonatiUltimo
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.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.