We study the random variable Y-n representing the number of occurrences of a given symbol in a word of length n generated at random. The stochastic model we assume is a simple non-ergodic model defined by the product of two primitive rational formal series, which form two distinct ergodic components. We obtain asymptotic evaluations for the mean and the variance of Y-n and its limit distribution. It turns out that there are two main cases: if one component is dominant and non-degenerate we get a Gaussian limit distribution; if the two components are equipotent and have different leading terms of the mean, we get a uniform limit distribution. Other particular limit distributions are obtained in the case of a degenerate dominant component and in the equipotent case when the leading terms of the expectation values are equal.

Frequency of symbol occurrences in simple non-primitive stochastic models / D. DE FALCO, M. GOLDWURM, V. LONATI (LECTURE NOTES IN COMPUTER SCIENCE). - In: Developments in Language Theory / [a cura di] Z. Esik, Z. Fulop. - Berlin : Springer-Verlag, 2003. - ISBN 3540404341. - pp. 242-253 (( Intervento presentato al 7. convegno DLT tenutosi a Szeged nel 2003.

Frequency of symbol occurrences in simple non-primitive stochastic models

D. DE FALCO;M. GOLDWURM;V. LONATI
2003

Abstract

We study the random variable Y-n representing the number of occurrences of a given symbol in a word of length n generated at random. The stochastic model we assume is a simple non-ergodic model defined by the product of two primitive rational formal series, which form two distinct ergodic components. We obtain asymptotic evaluations for the mean and the variance of Y-n and its limit distribution. It turns out that there are two main cases: if one component is dominant and non-degenerate we get a Gaussian limit distribution; if the two components are equipotent and have different leading terms of the mean, we get a uniform limit distribution. Other particular limit distributions are obtained in the case of a degenerate dominant component and in the equipotent case when the leading terms of the expectation values are equal.
Stochastic Mode;l Limit Distribution; Nonnegative Matrix; Asymptotic Evaluation; Approximate String Match
Settore INF/01 - Informatica
Settore MAT/06 - Probabilita' e Statistica Matematica
2003
Book Part (author)
File in questo prodotto:
File Dimensione Formato  
dlt03cortodef.pdf

accesso aperto

Tipologia: Post-print, accepted manuscript ecc. (versione accettata dall'editore)
Dimensione 432.87 kB
Formato Adobe PDF
432.87 kB Adobe PDF Visualizza/Apri
Falco2003_Chapter_FrequencyOfSymbolOccurrencesIn.pdf

accesso riservato

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