We study the local limit distribution of the number of occurrences of a symbol in words of length n generated at random in a regular language according to a rational stochastic model. We present an analysis of the main local limits when the finite state automaton defining the stochastic model consists of two primitive components. The limit distributions depend on several parameters and conditions, such as the main constants of mean value and variance of our statistics associated with the two components, and the existence of communications from the first to the second component. The convergence rate of these results is always of order O(n^{-1/2}). For the same statistics we also prove an analogous O(n^{-1/2}) convergence rate of the Gaussian local limit law whenever the stochastic model consists of one primitive component.

Local limit laws for symbol statistics in bicomponent rational models / M. Goldwurm, J. Lin, M. Vignati. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - 970:(2023 Aug 29), pp. 114051.1-114051.18. [10.1016/j.tcs.2023.114051]

Local limit laws for symbol statistics in bicomponent rational models

M. Goldwurm
Primo
;
J. Lin
Penultimo
;
M. Vignati
Ultimo
2023

Abstract

We study the local limit distribution of the number of occurrences of a symbol in words of length n generated at random in a regular language according to a rational stochastic model. We present an analysis of the main local limits when the finite state automaton defining the stochastic model consists of two primitive components. The limit distributions depend on several parameters and conditions, such as the main constants of mean value and variance of our statistics associated with the two components, and the existence of communications from the first to the second component. The convergence rate of these results is always of order O(n^{-1/2}). For the same statistics we also prove an analogous O(n^{-1/2}) convergence rate of the Gaussian local limit law whenever the stochastic model consists of one primitive component.
Automata and formal languages; Limit distributions; Local limit laws; Pattern statistics; Rational series; Regular languages;
Settore INF/01 - Informatica
Settore MAT/05 - Analisi Matematica
Settore MAT/06 - Probabilita' e Statistica Matematica
   Piano di Sostegno alla Ricerca 2015-2017 - Linea 2 "Dotazione annuale per attività istituzionali" (anno 2020)
   UNIVERSITA' DEGLI STUDI DI MILANO
29-ago-2023
https://doi.org/10.1016/j.tcs.2023.114051
Article (author)
File in questo prodotto:
File Dimensione Formato  
versione_pre-proof_1-s2.0-S030439752300364X-main.pdf

embargo fino al 29/08/2025

Tipologia: Post-print, accepted manuscript ecc. (versione accettata dall'editore)
Dimensione 910.41 kB
Formato Adobe PDF
910.41 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
1-s2.0-S030439752300364X-main.pdf

accesso riservato

Tipologia: Publisher's version/PDF
Dimensione 498.05 kB
Formato Adobe PDF
498.05 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/983868
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 0
social impact