We present some results concerning the rate functions of large deviations for symbol statistics define d in primitive rational models. In our context these functions are always define d over an open interval (, ) ⊆ (0, 1). We first prove certain properties of symmetry for such rate functions that allow us to simplify subsequent investigation. Then we show that the limits of these functions at the endpoints and are always finite and we prove that, under rather mild conditions, the same and are rational numbers of the form / such that , ∈ {0, 1, . . . , }, where is the number of states of the generalized automaton defining the rational model. Under the same hypotheses we yield a precise value for the corresponding limits.
In this work we study the properties of large deviations for symbol statistics in rational models. Such statistics represent the number of occurrences of a letter in a word generated at random among all strings of length , over a binary alphabet, with a probability proportional to the values of a given rational formal power series in non-commutative variables [2, 9, 3, 17]. These probabilistic models can be completely define d by a generalized automaton equipped with positive weights [27]. The study of symbol statistics in rational models is related to classical research topics in the areas of formal languages, descriptional complexity, random generation and analysis of combinatorial structures [13, 4, 6, 20, 8, 15]. Moreover, they are naturally related to the analysis of pattern statistics. Symbol statistics in rational models can represent a large variety of pattern statistics on words in several probabilistic contexts, this occurs for instance when the set of patterns is given by a regular language and the random text is generated by a Markovian source [2, 23, 18]. Typical results on pattern statistics concern the asymptotic evaluation of the moments, the limit distributions and also the properties of large deviations [24, 16, 15, 22]. In particular large deviations estimates are studied in order to evaluate the probability of rare events, when one or more patterns are over- or under-represented in a random text [5, 12, 22].
In the present contribution we continue the investigation started in [19], where we proved a
property of large deviations for any symbol statistics defined in a rational model assuming that
the overall matrix of the weights of transitions is primitive. Here, we first prove as an auxiliary
tool some properties of symmetry of the rate functions occurring in these large deviations
estimates. It is known that these functions are well defined in an open interval (, ) included
in (
The large deviations are typical properties of a sequence of random variables, say {}, that have increasing mean values. They consist of a bound exponentially decreasing to 0 over the probability that deviates from () by an amount greater or equal to (), for any > 0. The main situations occur when () ∼ for a constant > 0, and since this occurs in the contexts considered in this work, here we refer to the following formal definition, inspired by [11, 15], which is rather restrictive with respect to the usual general setting [10]. Definition 1. Consider a sequence of random variables {} such that () = + () for a constant > 0, and let (0, 1) be a real interval including . Assume () is a function defined over (0, 1) taking values in R, such that () > 0 for ̸= . We say that {} satisfies a large deviation property in the interval (0, 1) with rate function () if the following limits hold:
1 lim →∞
1 lim →∞ log Pr( ≤ ) = − () log Pr( ≥ ) = − () for 0 < ≤ for ≤ < 1 This property is equivalent to require that Pr( ≤ ) = − ()+(), for 0 < ≤ , and Pr( ≥ ) = − ()+(), for ≤ < 1. Such a property holds for several quantities of interest in the analysis of various combinatorial structures [14, 7, 15, 21].
The rate functions we encounter in this work are convex over their interval of definition and enjoy the following property, which often occurs in the study of large deviations [10]. For any open interval (, ) ⊆ R, we say that a convex function : (, ) →− R is essentially smooth if is diferentiable in (, ), lim→+ ′() = −∞ and lim→− ′() = +∞.
In order to define the rational stochastic models, consider a formal series in the non-commutative variables , , that is a function : {, }* → R+, where R+ = [0, +∞) and {, }* is the free monoid of all words in the alphabet {, }. As usual, we denote by (, ) the value of at a word ∈ {, }* . Such a series is said to be rational if for some integer > 0 there exists a monoid morphism : {, }* → R+× and two (column) arrays , ∈ R+, such that (, ) = ′ () , for every ∈ {, }* [1, 25] 1. Note that in this case, if = 12 · · · with ∈ {, } for every = 1, 2, . . . , , then () = (1) (2) · · · (). Thus, as is generated by the matrices = () and = (), we say that the 4-tuple (, , , ) is a linear representation of of size . Such a 4-tuple can be considered as a generalized automaton over the alphabet {, } as defined in [ 27], where {1, 2 . . . , } is the set of states and the weights of the transitions are positive real, as well as the weights of the initial and final states. In particular, the matrix (resp. ) represents the weights of the transitions labelled by (resp. ), while (resp. ) represents the weights of the initial (resp. final) states.
To avoid trivial situations, denoting by {, } the family of all words of length in {, }* , we assume that the set { ∈ {, } : (, ) > 0} contains at least two elements, for every ∈ N+. As a consequence, since ∑︀∈{,} (, ) = ′ ( + ) , we have ̸= 0 ̸= and both and are non-null matrices (i.e., each of them has at least one positive entry). Moreover, we can consider the probability measure Pr over the set {, } given by
Pr() = ∑︀
(, ) ∈{,} (, )
′ ()
= ′ ( + ) ,
∀ ∈ {, }
(
Then, under the previous hypotheses, we can define the integer random variable (r.v.) = ||, where is chosen at random in {, } with probability Pr() and || denotes the number of occurrences of in . By our assumptions, is a non-degenerate random variable. One can easily prove [2] that the probability function of is given by () := Pr( = ) = [] ′( + ) ′( + ) ∈ {0, 1, . . . , } where []() denotes as usual the coeficient of the monomial of degree in an arbitrary polynomial () ∈ R[]. For sake of brevity we say that is defined by the linear representation (, , , ). As shown in [2, 9, 3, 17], its traditional properties, as mean value, variance, limit distributions and local limit properties, can be studied by using its moment generating function =0 () = ′(′(++)) ( ∈ C). Ψ () = ∑︀
In this section we summarize the large deviation properties of when the matrix + is primitive [19]. Here and in the subsequent sections we denote by , and the entries of 1As usual, we denote by ′ the transpose of an array ∈ R, i.e. a row array. defined by the equation
Now (still assuming ̸= 0 ̸= ) let + be primitive and let be its Perron-Frobenius eigenvalue. In this case it is known that the sequence {} has a Gaussian limit distribution [2] it satisfies a large deviation property [ 19] and also has several local limit properties [3, 17]. These results are maily obtained by studying the function = (), where ∈ R, implicitly det( − − ) = 0 with initial condition (0) = . Clearly () is analytic and well defined all over R. Since also + is primitive for every ∈ R, () is its Perron-Frobenius eigenvalue; thus, () is a positive real function, strictly increasing all over R (by statement (i) above), which implies ′() > 0 for any ∈ R. which enjoy the following properties [2, 19]:
Moreover, we can define the constant = ′(0) and the function () = ′(()) , for ∈ R,
indices , of the matrices , and , respectively. Recall that a square matrix ∈ R+×
is primitive if there exists a positive integer such that > 0, i.e. all entries of are
strictly positive. It is well-known that is primitive if and only it is irreducible and aperiodic
[26]. Its main properties are established by the well-known Perron-Frobenius Theorem (see for
>
instance [26, Sec 1.1]) stating that every primitive matrix ∈ R+× admits a real eigevalue
0 (called the Perron-Frobenius eigenvalue of ) such that | | < for any eigenvalue of
diferent from , is a simple root of the characteristic equation of and the following
property holds:
(i) If a matrix =∈ R+× satisfies ≤ (i.e. ≤
then | | ≤ . Moreover, | | = implies = .
, ∀, ) and is an eigenvalue of
(
whenever < , = 0 and > 0 when > . (a) 0 < < 1 and E() = + + (), for some || < 1 and some constant ∈ R; (b) For every ∈ R we have 0 < () < 1, ′() > 0, and hence the following limits exist and = lim (), →−∞ = lim () →+∞ (c) For every ∈ (, ) there exists a unique ∈ R such that ( ) = . Moreover, < 0 By using the properties above the following result can be proved [19].
Then {} satisfies a large deviation property in the interval (, ) with rate function Theorem 1. Let {} be defined by a linear representation (, , , ) where + is primitive. () = − log ︂( ( ) )︂ where is defined by sentence (c) above. Moreover, is analytic in the whole interval (, ), where it is also convex and essentially smooth with a unique minimal value ( ) = 0.
A natural question arising from the previous result is whether the interval (, ) of definition
of () coincides with interval (
Theorem 2. Under the hypotheses of Theorem 1 the following properties hold: 1) If > 0 then = 0 and lim→0+ () = log(/ ) (whatever is); 2) If > 0 then = 1 and lim→1− () = log(/ ) (whatever is).
This result leaves open the problem of finding the values of and , respectively when = 0 and = 0. In these cases, also the limits lim→+ () and lim→ − () are not established. We only know, by Theorem 1, that 0 ≤ < ≤ 1 and that |′()| → +∞ as approaches or .
In this section we present a natural property of symmetry between rate functions in our context. Let , ∈ R+× be two non-null matrices (i.e. ̸= [0] ̸= ). Clearly, for every pair of values ∈ C and ∈ R, we have det( − − ) = 0 if and only if det(− − − − ) = 0. As a consequence, if = () and = () are functions defined, respectively, by the equations det( − − ) = 0 and det( − − ) = 0, with the same initial condition (0) = = (0), then () = (− ) for every ∈ R.
Theorem 3. Given two non-null matrices , ∈ R+× , assume that + is primitive. Let () and () be the rate functions of the symbol statistics defined, respectively, by (, , , ) and (, , , ), and suppose () defined over the interval (, ), for some 0 ≤ < ≤ 1. Then the following properties hold: 1. () is defined over the interval ( ′, ′) such that ′ = 1 − and ′ = 1 − . 2. For every ∈ ( ′, ′), () = (1 − ).
3. lim→′+ () = lim→ − () and lim→ ′− () = lim→+ ().
Proof. Clearly the third property is consequence of the other two. To prove the first one, let
() and () be defined as above. According with the notation of Section 4, set () = ′(())
and () = ′(()) . As stated above, we know that () = (− ) for every ∈ R, and hence
′() = [(− ) − ′(− )], which implies () = 1 − (− ). Thus, by relations (
To prove Property 2, let ∈ ( ′, ′) and set = 1 − . By sentence (c) of Section 4, there
exists a unique value ∈ R such that ( ) = . Analogously, there is a unique ∈ R such
that () = and, since () = 1 − (− ), we get = − . Thus, by relation (
In this section we study the behaviour of () for tending to or under the assumptions of Theorem 1, without restrictions on the matrices and , so including the case = 0 and = 0. Here we show that under these hypotheses such limits are always finite. In the next section, under more restrictive assumptions, we yield a precise expression of their values.
To present the result in detail, consider the family of real coeficients {ℎ : ℎ ∈ {1, 2 . . . , }, ∈ {0, 1, . . . , ℎ}} defined by the equality det( − − ) = −
ℎ ∑︁ ∑︁ ℎ − ℎ Since some of these coeficients may be null, we define the following sets: ℒ :=
= ℒ := {(ℎ, ) : ℎ ∈ {1, 2 . . . , }, ∈ {0, 1, . . . , ℎ}, ℎ ̸= 0} ; ( ) := { ∈ R : ∃(ℎ, ) ∈ ℒ such that = − ℎ} ; {(ℎ, ) ∈ ℒ : − ℎ = } , for every ∈ .
Clearly ℒ and are not empty, and the family {ℒ : ∈ } is a partition of ℒ. Moreover, we
can also define := max{ ∈ } and := min{ ∈ }. Thus, up to a division by , equation
(
∑︁ ℎ − ℎ
(ℎ,)∈ℒ
Now, let us study the properties of the previous equation when tends to +∞ in order to
determine and the limit lim→ − (). Consider the function () = ′()/() introduced
in Section 4, where ∈ R. From the second relation of (
() = − ()
∫︁
where () = ∫︀ (). Note that (0) = 0 and () > 0 for any > 0; more than that, () is
strictly increasing in R+ and one easily sees that () = () for → +∞. As a consequence,
() = +∞ or lim→+∞ () = − for some > 0. Moreover, from the last
Replacing this expression in equation (
( ())
∑︁
∈∖{}
1 = [︁
( ()) + O(− )]︁
(
() = − for some > 0, and hence () is
() = o(− 1)
for → +∞
Moreover, setting the constant ∈ (
− ()
→+∞
() = ( + ())
for some positive function () such that lim→+∞ () = 0+. Thus, relation (
However, these equalities allow us to evaluate the limit of () for → − . Recall that
() = − () and, by property c of Section 4, = ( ) and lim→ − = +∞. Thus,
() = − log ( ) + log + = − log( ( + ( ))) + log + ( ) =
= − log − log (︀ 1 + − 1 ( ) − ( ) = − log + o(
︀) As a consequence lim→ − () is always finite. By applying Theorem 3 it is easy to verify an analogous property for . Therefore we have proved the following result, which extends to the cases = 0 and = 0 the properties presented in Theorem 2.
Theorem 4. Under the hypotheses of Theorem 1 both limits of () for → + and for → − are finite.
The previous result is not taken for granted since, from Theorem 2, in case = 0 one might expect that the limit of () at − is +∞, while we have just proved it is finite. The same holds for the limit at + in case = 0.
In order to continue the analysis of the extremes and of the domain of (), we present some
properties of the coeficients ℎ introduced in (
For every matrix ∈ R+× , let ( ) be the weighted oriented graph with set of nodes = {1, 2, . . . , }, set of edges = {(, ) ∈ × | > 0} and weight for every (, ) ∈ . Further, for any cycle in ( ), the weight of is defined as the product of the weights of its edges and is denoted by (), while the length of is just the number of its edges. A cycle is said to be simple if it does not cross any node twice. We denote by the family of all simple cycles of length in ( ). Note that det( − ) = if and only if ( ) has no cycles.
A further key property is that the determinant of is a sum of products (with sign) of weights of simple cycles in ( ). More precisely, let us denote by ♯ the cardinality of a set ⊆ . For every ℎ ∈ {1, 2, . . . , }, define ℎ := { ⊆ : ♯ = ℎ}. Moreover, for every ∈ ℎ, set the submatrix := [ ],∈ and denote by the family of all permutations of . Note that any cyclic permutation of a subset ⊆ can be interpreted as a simple cycle that crosses every node in once. In general, any arbitrary permutation of a subset ⊆ can be represented by a family ( ) of disjoint simple cycles over , where every vertex in just belongs to one cycle of ( ). Also observe that the sign of a permutation turns out to be sgn( ) = (− 1), where is the number of (simple) cycles of even length in ( ). Thus, for every ∈ ℎ, if ∈ is a cyclic permutation then sgn( ) = (− 1)ℎ− 1. Moreover, for every permutation ∈ , the value ∏︀∈ () is diferent from 0 if and only if all cycles in ( ) are subgraphs of ( ) and, in this case, ∏︀∈ () = ∏︀∈( ) (). Thus, for every ℎ ∈ {1, 2, . . . , } and ∈ ℎ, we may write det() = ∑︁ sgn( ) ∏︁ () = ∑︁ sgn( ) ∈ ∈ ∈
∏︁ ∈( ) () Then, from the same definition of determinant, one can deduce the following property: Proposition 1. Given a matrix ∈ R+× having a non-null eigenvalue, define the coeficients 1, 2, . . . , by the equality Then, for every ℎ ∈ {1, 2, . . . , }, we have det( − ) = −
∑︁ ℎ− ℎ ℎ=1 ℎ = (− 1)ℎ− 1 ∑︁ det() Moreover, setting ℎ˘ := min{ℎ ∈ {1, 2, . . . , } : ℎ ̸= 0}, it turns out that ℎ˘ is the smallest length of a cycle in ( ), ℎ˘ > 0 and ℎ˘ = ∑︀∈ℎ˘ ().
Note in particular that 1 = tr( ), i.e. the trace of , and = (− 1)− 1 det( ).
The previous correspondence between matrices and graphs can be extended to pairs of non-negative matrices. Given two arbitrary matrices , ∈ R+× , let (, ) be the labelled oriented graph having set of vertices = {1, 2, . . . , } and, for every pair , ∈ , an edge from to of weight , labelled by , whenever > 0, and an edge from to of weight , labelled by , whenever > 0. Any path (or cycle) in (, ) consists of consecutive edges, each of them labelled by either or . The weight of a cycle in (, ) is the product of the weights of its edges.
By applying Proposition 1 to the matrix + , for an arbitrary variable , we obtain det( − − ) = −
∑︁(− 1)ℎ− 1 ∑︁ det( + ) − ℎ
ℎ=1
∈ℎ
(
ℎ ⎛ ⎞
∑︁ sgn( ) ∑︁ ⎝ ∑︁ ∏︁ () ∏︁ ()⎠
∈ =0 ∈() ∈ ∈∖
∈ℎ ∈
ℎ = (− 1)ℎ− 1 ∑︁ ∑︁ sgn( )
Note that, for = 0, the sum included in round brackets of the last expression reduces to
∏︀∈ (), while for = ℎ it becomes ∏︀∈ (). Thus, from equalities (
(
For our purposes it is relevant here to show that ℎ > 0 for certain pairs of indices (ℎ, ) ∈ ℒ that have maximum or minimum ratio /ℎ. To prove a property of this kind we introduce a (possibly) diferent partition of the coeficients set ℒ, i.e. let us define ℛ := ℒ := := { ∈ Q : ∃(ℎ, ) ∈ ℒ such that = /ℎ} , {(ℎ, ) ∈ ℒ : /ℎ = } , for every ∈ ℛ , max{ ∈ ℛ} , := min{ ∈ ℛ} .
Observe that, if + has a non-null eigenvalue then ℒ is not empty, 0 ≤ ≤ 1 for every ∈ ℛ, the family of sets {ℒ : ∈ ℛ} forms a partition of ℒ, and also ℒ and ℒ are not empty. As in the previous sections, we denote by and the largest real non-negative eigenvalue of and , respectively. Then, we can prove the following property.
Proposition 2. Given two matrices , ∈ R+× such that + has a non-null eigenvalue,
assume = 0 and let (ℎ¯, ¯) be the element in ℒ with smallest value ℎ¯. Then < 1 and ℎ¯¯ > 0.
Proof. First observe that, since = 0, by relation (
ℎ is given by the weights of permutations of sets of ℎ nodes whose cycles in (, ) have many edges labelled by and ℎ − edges labelled by . Since is the maximum value in ℛ
, all (possible) simple cycles in (, ) of length
sgn( ) = (− 1)ℎ¯− 1, which implies ℎ¯¯ > 0 by the same identity (
An analogous symmetric reasoning (exchanging and , and ) allows us to state a similar result for ℒ. Note that, also in this case, if (ℎ˘, ˘) is the element of ℒ with smallest value ℎ˘ then all permutations that contribute to ℎ˘˘ are cyclic, and hence reasoning as above ℎ˘˘ > 0. Proposition 3. Given two matrices , ∈ R+× such that + has a non-null eigenvalue, assume = 0 and let (ℎ˘, ˘) be the element in ℒ with smallest value ℎ˘. Then > 0 and ℎ˘˘ > 0.
The results of Section 6 are obtained under the assumptions of Theorem 1, i.e. + primitive and both and non-null. Now we introduce further hypotheses in our analysis. Our goal is to prove that, under a mild condition, the endpoints of the domain of () are of the form /ℎ for some integers , ℎ ∈ {0, 1, . . . , } such that ≤ ℎ (ℎ ̸= 0) and, under the same hypothesis, we determine a precise value for the limits of () at these extremes when = 0 or = 0. The proofs are based on the properties of characteristic polynomials presented in Section 7, and here we use the notions introduced therein. defined by ℒ = {(ℎ¯, ¯)} for a given (ℎ¯, ¯) ∈ ℒ. Then = < 1, ℎ¯¯ > 0 and Theorem 5. Under the hypotheses of Theorem 1, let = 0 and assume that ℒ is a singleton → − lim () = log √ℎ¯ ℎ¯¯ from and every (ℎ, ) ∈ ℒ, one has − ℎ < 0. Now, let us define the function Proof. First note that, by Proposition 2, < 1 and ℎ¯¯ > 0. Moreover, for every ∈ ℛ diferent (, ) := 1 − ℎ¯¯ ¯ − ℎ¯ −
∑︁
(ℎ,)∈ℒ∖{(ℎ¯,¯)}
ℎ
− ℎ
Under our hypotheses, equation (
ℎ ℎ(− ℎ) = 1 − ℎ¯¯ − ℎ¯ + o(
+ o(
√ℎ¯ ℎ¯¯
)︃
□
Then, for large enough, (, ) is greater or smaller than 0 according to whether is
greater or smaller than √ℎ¯ ℎ¯¯ . Since = () is solution of equation (, ) = 0, this implies
the following relation for every > 0 and every large enough:
︁( √ℎ¯︀ ℎ¯¯ − ≤ () ≤
︁)
︁( √ℎ¯︀ ℎ¯¯ +
︁)
Since () has the form (
At last, let us consider the behaviour of () for tending to − . Since = we have
= 0 and equality (
Again, applying Theorem 3 to the previous result, a similar property can be proved for . defined by ℒ = {(ℎ˘, ˘)} for a given (ℎ˘, ˘) ∈ ℒ. Then = > 0, ℎ˘˘ > 0 and Theorem 6. Under the hypotheses of Theorem 1, let = 0 and assume that ℒ is a singleton →+ lim () = log
√ℎ˘︀ ℎ˘˘ Clearly, under the hypotheses of the last two theorems, both and turn out to be of the form /ℎ for some (ℎ, ) ∈ ℒ
. Moreover, it is easy to verify that if the size of the linear Theorems 6 and 5 apply in case = 0 and = 0, respectively. representation of the rational model belongs to {2, 3} then all sets ℒ are singleton, and hence Example 1. Consider the linear representation defined by the finite automaton of Figure 1, where all transitions have weight 1. In this case = 2, = 2/3, = 1 while = 0, 2 det( − (︀ 1 + √ − ) = 3 − 2 −
2 and () can be computed explicitly as () = 1 + 8− )︀ . Moreover, the non-null coeficients ℎ are 11 = 1 and 21 = 2, and graphic of which is plotted at the right hand side of the figure. hence = 1/2, which implies = 1/2 by Theorem 6. By the same theorem we have lim→1/2+ () = (1/2) log 2. Since > 0 the behaviour of () near is established by Theorem 2: = 1 and lim→1− () = log 2. These evaluations are confirmed by analysis of the rate function () = log 2 + − log (), where satisfies the relation ′() = (), the similar way, it is easy to produce examples with 4 states where also ℒ is not singleton.
Here is an example of size = 4 where a set ℒ is not singleton, but ℒ is. However, in a Example 2. Consider the linear representation defined by the automaton in the left hand side of Figure 2. Clearly + is primitive and a direct computation shows that its Perron-Frobenius eigenvalue is a constant = 3.38.... Moreover, here we have = 0, = 2 and det( − − ) = 4 − 33 − 52 + 22 + 7 − 63 + 22 and lim→3/4− () = log(/
√46). showing the values of non-null coeficients
ℎ ’s. Note that here ℒ1/2 = {(
3
A natural goal for possible subsequent investigations concerns the extension of the results presented in Theorems 5 and 6 to all rational models (, , , ) having primitive matrix + (with both and not null). In fact, we think that analogous results can be obtained also when ℒ and ℒ are not singleton. In these cases, the limits of () at and should be related to the roots of the polynomials () and () (defined as in Section 6) which can be studied by using the properties of the primitive matrices.
This work has been supported by Università degli Studi di Milano, under project PSR 2023. [21] H.-K. Hwang. Large deviations for combinatorial distributions. I: Central limit theorems.
The Annal of Applied Probability, 6(
University Press, 2015.
[23] P. Nicodeme, B. Salvy, and P. Flajolet. Motif statistics. Theoret. Comput. Sci., 287(
Verlag, 1978. [26] E. Seneta. Non-negative matrices and Markov chains. Springer–Verlag, New York Heidelberg
Berlin, 1981. [27] P. Turakainen. Generalized automata and stochastic languages. Proc. Amer. Math. Soc., 21: 303–309, 1969.