We present a large deviation property for pattern statistics representing the number of occurrences of a symbol in words of given length generated at random according to a rational stochastic model. This result is proved assuming that the transition matrix of the model is primitive. We show how the rate function of the large deviation property depends on the main eigenvalues and eigenvectors of the transition matrices associated with the different symbols of the alphabet. We also yield general conditions to guarantee that the range of validity of the large deviation estimate coincides with the whole interval $(0,1)$, which represents in our context the largest possible open interval where the property may hold. The case of smaller intervals of validity is finally examined by means of examples.

Large deviation properties for pattern statistics in primitive rational models / M. Goldwurm, M. Vignati. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - 1030:(2025 Mar), pp. 115055.1-115055.13. [10.1016/j.tcs.2024.115055]

Large deviation properties for pattern statistics in primitive rational models

M. Goldwurm
;
M. Vignati
2025

Abstract

We present a large deviation property for pattern statistics representing the number of occurrences of a symbol in words of given length generated at random according to a rational stochastic model. This result is proved assuming that the transition matrix of the model is primitive. We show how the rate function of the large deviation property depends on the main eigenvalues and eigenvectors of the transition matrices associated with the different symbols of the alphabet. We also yield general conditions to guarantee that the range of validity of the large deviation estimate coincides with the whole interval $(0,1)$, which represents in our context the largest possible open interval where the property may hold. The case of smaller intervals of validity is finally examined by means of examples.
automata and formal languages; large deviations; limit distributions; pattern statistics; rational series; regular languages
Settore INFO-01/A - Informatica
Settore MATH-03/A - Analisi matematica
Settore MATH-03/B - Probabilità e statistica matematica
mar-2025
7-gen-2025
Article (author)
File in questo prodotto:
File Dimensione Formato  
1-s2.0-S0304397524006728-main.pdf

accesso aperto

Tipologia: Publisher's version/PDF
Licenza: Creative commons
Dimensione 901.32 kB
Formato Adobe PDF
901.32 kB Adobe PDF Visualizza/Apri
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/1151577
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
  • OpenAlex ND
social impact