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.| 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.




