Alexander Burstein
email: burstein@math.iastate.edu

Toufik Mansour
email: toufik@labri.fr

Counting occurrences of some subword patterns

Keywords:

We find generating functions for the number of strings (words) containing a specified number of occurrences of certain types of order-isomorphic classes of substrings called subword patterns. In particular, we find generating functions for the number of strings containing a specified number of occurrences of a given 3-letter subword pattern.

Introduction

Counting the number of words which contain a set of given strings as substrings a certain number of times is a classical problem in combinatorics. This problem can, for example, be attacked using the transfer matrix method (see [START_REF] Stanley | Enumerative Combinatrics[END_REF]Section 4.7]). In particular, it is a well-known fact that the generating function of such words is always rational. For example, in [START_REF] Stanley | Enumerative Combinatrics[END_REF]Example 4.7.5] it is shown that the generating function for the number of words in [START_REF] Bona | Permutations with one or two 132-subsequences[END_REF] n where neither 11 nor 23 appear as two consecutive digits is given by 3 + xx 2 1 -2xx 2 + x 3 . In this paper, we present, in several cases, a complete solution for the problem of the enumeration of words containing a subword pattern (see below for the precise definition) of length l exactly r times. For example, we find the number of words in [START_REF] Bona | Permutations with one or two 132-subsequences[END_REF] n containing the subword pattern 111 exactly r times, that is, the number of words which contain 111, 222, and 333 as substrings a total of r times.

Régnier and Szpankowski [START_REF] Régnier | On the approximate pattern occurrences in a text[END_REF] used a combinatorial approach to study the frequency of occurrences of strings (which they also called a "pattern") from a given set in a random word, when overlapping copies of the "patterns" are counted separately (see [START_REF] Régnier | On the approximate pattern occurrences in a text[END_REF]Theorem 2.1]). We note that the term "pattern" in [START_REF] Régnier | On the approximate pattern occurrences in a text[END_REF] is used to denote an exact string rather than its type with respect to order isomorphism. For example, the "pattern" 112 in [START_REF] Régnier | On the approximate pattern occurrences in a text[END_REF] is the actual string 112, whereas in our setting an occurrence of the subword pattern 112 is any substring aab of the ambient string with a < b. Although, in principle, it is possible to deduce our results from the result by Régnier and Szpankowski, our direct derivations are much simpler.

Goulden and Jackson [START_REF] Goulden | Combinatorial enumeration[END_REF] also consider sequences with distinguished substrings and use the term "pattern of a sequence". However, their "pattern" is more locally defined than in this paper in that only order relations between adjacent elements of a string are considered, rather than order relations between any pair of elements of a string, as is done in this paper. For example, the pattern "rise, non-rise" (or (<, ≥), or π 1 π 2 ) as defined in [START_REF] Goulden | Combinatorial enumeration[END_REF] includes the subword patterns 121, 122, 132, 231 as defined in this paper. However, we show that each of the subword patterns 121, 122, 132 is avoided by a different number of words (of a given length on a given alphabet) than the other two patterns.

In what follows, we use analytical and combinatorial means to find a complete answer for several cases of counting strings with a specified number of occurrences of certain patterns.

Classical patterns in permutations

Let π ∈ S n and τ ∈ S m be two permutations. An occurrence of τ in π is a subsequence

1 ≤ i 1 < i 2 < • • • < i m ≤ n such that (π(i 1 ), . . . , π(i m )
) is order-isomorphic to τ. In this context, τ is usually called a pattern. We denote the number of occurrences of τ in π by π(τ).

Recently, much attention has been paid to the problem of counting the number of permutations of length n containing a given number r ≥ 0 of occurrences of a certain pattern τ. Most of the authors consider only the case r = 0, thus studying permutations avoiding a given pattern. Only a few papers consider the case r > 0, usually restricting themselves to the patterns of length 3. In fact, simple algebraic considerations show that there are only two essentially different cases for τ ∈ S 3 , namely, τ = 123 and τ = 132. Noonan [START_REF] Noonan | The number of permutations containing exactly one increasing subsequence of length three[END_REF] has proved that the number of permutations in S n containing 123 exactly once is given by 3 n 2n n-3 . A general approach to the problem was suggested by Noonan and Zeilberger [START_REF] Noonan | The enumeration of permutations with a prescribed number of "forbidden" patterns[END_REF]; they gave another proof of Noonan's result, and conjectured that the number of permutations in S n containing 123 exactly twice is given by 59n 2 +117n+100 2n(2n-1)(n+5) 2n n-4 and the number of permutations in S n containing 132 exactly once is given by 2n-3 n-3 . The first conjecture was proved by Fulmek [START_REF] Fulmek | Enumeration of permutations containing a prescribed number of occurrences of a length-3-pattern[END_REF] and the second conjecture was proved by Bóna in [START_REF] Bona | Permutations with one or two 132-subsequences[END_REF]. A general conjecture of Noonan and Zeilberger states that the number of permutations in S n containing τ exactly r times is P-recursive in n for any r and τ. It was proved by Bóna [START_REF] Bona | The number of permutations with exactly r 132-subsequences is P-recursive in the size![END_REF] for τ = 132. However, as stated in [START_REF] Bona | The number of permutations with exactly r 132-subsequences is P-recursive in the size![END_REF], a challenging question is to describe the number of permutations in S n containing τ ∈ S 3 exactly r times, explicitly for any given r. Later, Mansour and Vainshtein [START_REF] Mansour | Counting occurrences of 132 in a permutation[END_REF] suggested a new approach to this problem in the case τ = 132, which allows one to get an explicit expression for the number of permutations in S n containing 132 exactly r times for any given r.

Generalized patterns in permutations

In [START_REF] Babson | Generalized permutation patterns and a classification of the Mahonian statistics[END_REF], Babson and Steingrímsson introduced generalized permutation patterns that allow the requirement that two adjacent letters in a pattern must be adjacent in the permutation. For example, an occurrence of a generalized pattern 12-3 in a permutation π = a 1 a 2 • • • a n is a subword a i a i+1 a j of π such that a i < a i+1 < a j . Notation 1.1 Unfortunately, there is a bit of confusion in denoting classical and generalized patterns. Before generalized patterns were introduced, the hyphens were unnecessary, hence classical patterns (those with all possible hyphens) are often written with no hyphens when generalized patterns are not considered, and with all hyphens when they are. For example, a classical pattern 123 is now denoted by 1-2-3 when considered as a generalized pattern (using the notation of [START_REF] Babson | Generalized permutation patterns and a classification of the Mahonian statistics[END_REF][START_REF] Claesson | Generalized pattern avoidance[END_REF]). Unless otherwise stated, all patterns under consideration from now on are generalized patterns.

In [START_REF] Elizalde | Enumeration of subwords in permutations[END_REF] Elizalde and Noy presented the following theorem regarding the distribution of the number of occurrences of any generalized pattern of length 3 without hyphens. Theorem 1.2 (Elizalde and Noy [START_REF] Elizalde | Enumeration of subwords in permutations[END_REF]

) Let h(x) = (x -1)(x + 3). Then ∑ n≥0 ∑ π∈S n x π(123) t n n! = 2h(x)e 1 2 (h(x)-x+1)t h(x) + x + 1 + (h(x) -x -1)e h(x)t , ∑ n≥0 ∑ π∈S n x π(213) t n n! = 1 1 -t 0 e (x-1)z 2 /2 dz
, where π(123) (respectively, π(213)) is the number of occurrences of the generalized pattern 123 (respectively, 213) without hyphens in π.

On the other hand, Claesson [START_REF] Claesson | Generalized pattern avoidance[END_REF] gave a complete answer for the number of permutations avoiding a generalized pattern of the form xy-z where xyz ∈ S 3 . Later, Claesson and Mansour [START_REF] Claesson | Permutations avoiding a pair of generalized patterns of the form x-yz or xy-z[END_REF] presented an algorithm to count the number of permutations containing a generalized pattern of the form xy-z exactly r times for any given r ≥ 0, where xyz ∈ S 3 .

Theorem 1.3 (Claesson and Mansour [8]) The ordinary generating function for the number of permutations of length n avoiding the generalized pattern 12-3 (or

23-1) is ∑ k≥0 x k (1 -x)(1 -2x) • • • (1 -kx)
.

The ordinary generating function for the number of permutations of length n avoiding the generalized pattern 2-13 is

C(x) = 1 - √ 1 -4x 2x .
The ordinary generating function for the number of permutations of length n containing exactly one occurrence of the generalized pattern 12-3 is

∑ n≥1 x 1 -nx ∑ k≥0 kx k+n (1 -x)(1 -2x) • • • (1 -(k + n)x)
.

The ordinary generating function for the number of permutations of length n containing exactly one occurrence of the generalized pattern

23-1 is ∑ n≥1 x 1 -(n -1)x ∑ k≥0 kx k+n (1 -x)(1 -2x) • • • (1 -(k + n)x)
.

The ordinary generating function for the number of permutations of length n containing exactly one occurrence of the generalized pattern 2-13 is

x 3 C(x) 7 1 -tC(x) 2 .

Generalized patterns in words

A generalized pattern τ is a (possibly hyphenated) string in [ℓ] m which contains all letters from [ℓ] = {1, . . . , ℓ}. We say that the string σ ∈ [k] n contains a generalized pattern τ exactly r times (denoted by r = σ(τ)) if σ contains r different subsequences isomorphic to τ in which the entries corresponding to consecutive entries of τ not separated by a hyphen must be adjacent. We call the generalized patterns without hyphens subword patterns. If r = 0, we say that σ avoids τ and write σ ∈ [k] n (τ). Thus, [k] n (τ) denotes the set of strings in [k] n (i.e., n-long k-ary strings) which avoid τ. For example, a string π = a 1 a 2 . . . a n avoids the generalized pattern 12-1 if π has no subsequence a i a i+1 a j with j > i + 1 and a i = a j < a i+1 .

Example 1. [START_REF] Burstein | Enumeration of words with forbidden patterns[END_REF] Davenport-Schinzel sequences [START_REF] Davenport | A combinatorial problem connected with differential equations[END_REF] can be defined in terms of subword pattern avoidance as follows. For any d ≥ 1, let T d be the set of all the subword patterns π

= a 1 a 2 • • • a d+1 ∈ [d + 1] d+1
such that either a 2 j < a 2 j+1 > a 2 j+2 for all j, or a 2 j-1 < a 2 j > a 2 j+1 for all j. For example, T 2 = {121, 132, 231, 212, 213, 312}. An k-ary n-long sequence avoiding the subword pattern 11 (i.e., with no equal consecutive letters) and avoiding all the subword patterns in T d (there are no alternating subwords of length greater than d + 1) is called a Davenport-Schinzel sequence if n is maximal.

Let f τ;r (n, k) be the number of words σ ∈ [k] n such that σ(τ) = r. Denote the corresponding bivariate generating function by F τ (x, y; k), in other words,

F τ (x, y; k) = ∑ n≥0 ∑ r≥0 f τ;r (n, k)x n y r .
Burstein [START_REF] Burstein | Enumeration of words with forbidden patterns[END_REF] gave a complete answer for the numbers f τ;0 (n, k) where τ is a 3-letter classical pattern. Later, Burstein and Mansour [START_REF] Burstein | Words restricted by patterns with at most 2 distinct letters[END_REF][START_REF] Burstein | Words restricted by 3-letter generalized multipermutation patterns[END_REF] presented a complete answer for the number f τ;0 (n, k) where τ is a generalized pattern of length 3 (a word of length 3).

In this paper, we present a complete answer for several cases of f τ;r (n, k) where τ is a subword pattern of length l (which is the analogue of the results by Elizalde and Noy in [START_REF] Elizalde | Enumeration of subwords in permutations[END_REF]). In particular, we find a complete answer for the case l = 3.

Counting a subword pattern of length l

In this section we find F τ (x, y; k) for several cases of τ. Burstein and Mansour [START_REF] Burstein | Words restricted by 3-letter generalized multipermutation patterns[END_REF] found F τ (x, y; k) for the subword pattern τ = 11 . . . 1 ∈ [1] l and proved the following theorem.

F τ (x, y; k) = 1 + (1 -y)x ∑ l-2 j=0 (kx) j -(1 -y)(k -1) ∑ l-1 d=2 x d ∑ l-1-d j=0 (kx) j 1 -(k -1 + y)x -(k -1)(1 -y)(1 -x l-2 ) x 2 1-x .
2.1 The subword pattern τ = 11 . . . 12 Let τ = 11 . . . 12 ∈ [2] l be a subword pattern. Define d τ;r (n, k) to be the number of words β ∈ [k] n such that (β, k + 1) contains τ exactly r times, and denote the corresponding generating function by

D τ (x, y; k) = ∑ n,r≥0 d τ;r (n, k)x n y r .
Let us find a recurrence for

F τ . Let σ ∈ [k] n (k ≥ 2), with σ(τ) = r, contain exactly d copies of the letter k. If d = 0, then σ ∈ [k -1] n and σ(τ) = r. If d ≥ 1, then σ = σ 1 kσ 2 , where σ 1 ∈ [k -1] n 1 , σ 2 ∈ [k] n 2 , n 1 + n 2 + 1 = n and (σ 1 , k)(τ) + σ 2 (τ) = r.
Taking generating functions, we see that the above translates into

F τ (x, y; k) = F τ (x, y; k -1) + xD τ (x, y; k -1)F τ (x, y; k),
or, equivalently,

F τ (x, y; k) = F τ (x, y; k -1) 1 -xD τ (x, y; k -1)
.

Let us now find the recurrence for D τ . Let σ ∈ [k] n be such that (σ, k + 1) contains τ exactly r times, and has exactly d letters k. Then σ = σ 1 kσ 2 k . . . kσ d kσ d+1 for some

σ i ∈ [k -1] n i , 1 ≤ i ≤ d + 1, where n 1 + • • • + n d+1 = n -d and (σ 1 , k)(τ) + • • • + (σ d , k)(τ) + (σ d+1 , k + 1)(τ) + δ(σ ends on l -1 k's) = r.
Taking generating functions, we obtain

D τ (x, y; k) = l-2 ∑ d=0 x d D d+1 τ (x, y; k -1) + ∞ ∑ d=l-1 x d D d+1 τ (x, y; k -1) -D (d+1)-(l-1) τ (x, y; k -1) + yD (d+1)-(l-1) τ (x, y; k -1) ,
which, after summing over d, yields

D τ (x, y; k -1) = (1 -x l-1 (1 -y))D τ (x, y; k -1) 1 -xD τ (x, y; k -1)
.

These two recurrences, together with D τ (x, y; 0) = F τ (x, y; 0) = 1 and induction on k, yield the following theorem.

Theorem 2.2 Let τ = 11 . . . 12 ∈ [2] l be a subword pattern such that l ≥ 1; then

F τ (x, y; k) = 1 -y 1 -x 2-l -y + x 2-l (1 -x l-1 (1 -y)) k .
1 -1 x + 1 x (1 -x 2 ) k .
In the special case of l = 3, we get from Theorem 2.2 the following result.

Corollary 2.4

The generating function for the number of words in [START_REF] Bona | The number of permutations with exactly r 132-subsequences is P-recursive in the size![END_REF] n containing the subword pattern 112 exactly r times is given by x 3r (1x) r+1 (1xx 2 ) r+1 .

Proof: Let τ = 112 be a subword pattern. It is easy to see that a word σ ∈ [2] n with σ(τ) = r must have the form σ = σ 1 τσ 2 τ . . . τσ r+1 , for some σ 1 , . . . ,

σ r+1 ∈ [2] n (τ). Now, from Example 2.3 with k = 2, we have that F τ (x; 2) = 1 (1-x)(1-x-x 2 ) ,
σ i ∈ [k -1] n i , ∑ n i = n -d, and σ(τ) = σ 0 (τ) + (k, σ 1 , k)(τ) + • • • + (k, σ d-1 , k)(τ) + σ d (τ)).
Hence, if we sum over all d ≥ 0, we get

F τ (x, y; k) = F τ (x, y; k -1) + xF 2 τ (x, y; k -1) 1 -xD τ (x, y; k -1)
.

On the other hand, the word (k + 1, β, k + 1), with β as above, contains an occurrence of τ involving the two letters k + 1 if and only if β is a constant string of length l -2, otherwise,

(k + 1, β, k + 1)(τ) = β(τ).
Taking generating functions, we obtain

D τ (x, y; k) = kx l-2 y + F τ (x, y; k) -kx l-2 .
Therefore, using the initial conditions F τ (x, y; 0) = D τ (x, y; 0) = 1 and induction on k, we get the following theorem.

Theorem 2.5 Let τ = 211 . . . 112 ∈ [2] l be a subword pattern and l ≥ 2, then

F τ (x, y; k) = 1 1 -x -x ∑ k j=0 1 1+ jx l-1 (1-y) .
Example 2.6 (Burstein and Mansour [6,Th. 3.12]) Letting l = 3 and y = 0 in Theorem 2.5, we get that the generating function for the number of words in [k] n avoiding the subword pattern 212 is given by (1-y) . Proof: Let σ ∈ [k] n . The generating function for the number of words σ which do not contain m and contain τ exactly r times is given by F τ (x, y; k -1). Now assume that the leftmost m in σ is at position i. Then σ = σ 1 mσ 2 and σ(τ) = σ 1 (τ) + (m, σ 2 )(τ), so the generating function for the number of such words σ is given by xF τ (x, y; k -1)D τ (x, y; k), where D τ (x, y; k) is the generating function for the number of words σ ∈ [k] n such that (m, σ) contains τ exactly r times. Therefore,

1 1 -x -x ∑ k-1 j=0 1 1+ jx 2 .

The subword pattern

τ = mτ ′ m Theorem 2.7 Let τ = mτ ′ m ∈ [m] l be a subword pattern, where τ ′ does not contain m. Then for k ≥ m, F τ (x, y; k) = 1 1 -(m -1)x -x ∑ k-1 j=m-1 1 1+( j m-1 )x l-1
F τ (x, y; k) = F τ (x, y; k -1) + xF τ (x, y; k -1)D τ (x, y; k).
On the other hand, let σ ′ = (m, σ) ∈ [k] n+1 . If σ does not contain m, then the generating function for the number of such σ is given by F τ (x, y; k -1). Otherwise, let i be the position of the leftmost letter m and let σ| i be the left prefix of σ of length i, then the generating function for these words is given by

x F τ (x, y; k -1) -x l-2 k -1 m -1 D τ (x, y; k) if (m, σ| i ) is not order-isomorphic to τ, or by xyx l-2 k -1 m -1 D τ (x, y; k) if (m, σ| i ) is order-isomorphic to τ. Therefore, D τ (x, y; k) = F τ (x, y; k -1) + x F τ (x, y; k -1) -x l-2 k -1 m -1 D τ (x, y; k) + yx l-1 k -1 m -1 D τ (x, y; k).
Hence, from the above two equations, we obtain

F τ (x, y; k) = 1 + x l-1 k-1 m-1 (1 -y) F τ (x, y; k -1) 1 + x l-1 k-1 m-1 (1 -y) -xF τ (x, y; k -1)
, so, by induction on k with the initial condition F τ (x, y; m -1) =

F 2112 (x, y; k) = 1 1 -x -x ∑ k-1 j=0 1 1+ jx 3 (1-y) , F 3123 (x, y; k) = 1 1 -2x -x ∑ k-1 j=2 1 1+ j( j-1)x 3 (1-y)/2
. Definition 2.9 We say that the patterns β and γ are strongly Wilf-equivalent, or are in the same strong Wilf class, if the number of words in [k] n containing β exactly r times is the same as the number of words in [k] n containing γ exactly r times, for any r ≥ 0. By Theorem 2.7 and the symmetry operations "reversal" and "complement," we immediately get the following corollary.

Corollary 2.10

The subword patterns 1121 and 1221 are in the same strong Wilf class.

2.4

The subword pattern τ = mτ ′ (m + 1) Let τ = mτ ′ (m + 1) be a subword pattern, where τ ′ does not contain m or m + 1. Note that τ is in the same symmetry class as r(c(τ)) = 1r(c(τ ′ ))2. This case is treated in a similarl manner as the case of τ = mτ ′ m. As a result, we obtain the theorem below.

Theorem 2.11 Let τ = mτ ′ (m + 1) ∈ [m + 1] l be a subword pattern, where τ ′ does not contain m or m + 1.

Then for k ≥ m, F τ (x, y; k) = 1 1 -(m -1)x -x ∑ k-2 i=m-2 ∏ i j=m-2 1 -j m-1 x l-1 (1 -y)
.

3 Subword patterns of length 3

The symmetry class representatives of 3-letter subword patterns are 111, 112, 212, 123, 213. In the current subsection, we find explicit formulas for F τ (x, y; k) for each of these representatives τ. Theorem 2.1 yields the answer for the first class.

Theorem 3.1 Let τ = 111 be a subword pattern. Then, for all k ≥ 0, we have

F τ (x, y; k) = 1 + x(1 + x)(1 -y) 1 -(k -1 + y)x -(k -1)(1 -y)x 2 .
Theorems 2.2 and 2.5 contain already the answers for the second and the third classes, respectively. Let us summarize the corresponding results in the theorem below. Theorem 3.2 Let 112 and 212 be subword patterns. For k ≥ 0,

F 112 (x, y; k) = 1 -y 1 -1 x -y + 1 x (1 -x 2 (1 -y)) k , F 212 (x, y; k) = 1 1 -x -x ∑ k j=0 1 1-jx 2 (1-y)
. Now let us find the generating function for the fourth class, F τ (x, y; k) where τ = 123 is a subword pattern. Let D τ (x, y; k) be the generating function for the number of words σ ∈ [k] n such that (σ, k + 1) contains the subword pattern 123 exactly r times. Suppose a word σ ∈ [k] n (τ) has exactly d letters k. Then σ = σ 0 kσ 1 k . . . kσ d , where all σ i ∈ [k -1] n , and any occurrence of τ in σ must be either in (σ i , k) for some i = 0, 1, . . . , d -1, or in σ d . Therefore, the generating function for the number of such words σ is (xD τ (x, y; k -1)) d F τ (x, y; k -1), so

F τ (x, y; k) = ∑ d≥0 (xD τ (x, y; k -1)) d F τ (x, y; k -1).
+ ∑ d≥1 x d D d-1 τ (x, y; k -1)) + ∑ d≥1 x d yD d-1 τ (x, y; k -1)(D τ (x, y; k -1) -1).
Hence,

F τ (x, y; k) = F τ (x, y; k -1) 1 -xD τ (x, y; k -1)
,

D τ (x, y; k) = (1 -x + xy)D τ (x, y; k -1) + x(1 -y) 1 -xD τ (x, y; k -1)
.

Together with F τ (x, y; 0) = D τ (x, y; 0) = 1, F τ (x, y; 1) = D τ (x, y; 1) = 1/(1x) and induction on k, this yields the following result.

Theorem 3.3 Let τ = 123 be a subword pattern. For all k ≥ 2, we have

F τ (x, y; k) = 1 1 -kx -∑ k j=3 (-x) j k j (1 -y) ⌊ j/2⌋ U j-3 (y)
, where U 0 (y) = U 1 (y) = 1, U 2n (y) = (1y)U 2n-1 (y) -U 2n-2 (y), and U 2n+1 (y) = U 2n (y) -U 2n-1 (y). Furthermore, the generating function for U n (y) is given by

∑ n≥0 U n (y)z n = 1 + z + z 2 1 + (1 + y)z 2 + z 4 .
Finally, Theorem 2.11 for l = 3 and m = 2 provides already the answer for the last class. The corresponding result is summarized below. Theorem 3.4 Let τ = 213 be a subword pattern. Then for all k ≥ 2, we have

F τ (x, y; k) = 1 1 -x -x ∑ k-2 i=0 ∏ i j=0 (1 -jx 2 (1 -y))
.

Further results

We say that a subword pattern τ ∈ [m] l is primitive if any two distinct occurrences of τ may overlap by at most one letter. For example, the subword patterns 112, 121, 122, 132, 211, 212, 213, 221, 231, and 312 are all the primitive patterns of length three. Proof: Let σ ∈ [k] n contain τ exactly r times. Since τ is a primitive subword pattern, we can define a function f which changes any occurrence of τ in σ to an occurrence of τ ′ . It is easy to see from the definition of primitive patterns that f is a bijection, hence the theorem follows. ✷ An immediate corollary is the following. Hence, by induction on p and k, using F τ (x, y; m -1) = 1/(1 -(m -1)x) and D τ (x, y; k; h) = 0 for h > k, we get the desired result. ✷ Using the proof of the above theorem, we get the following generalization.

Theorem 2 . 1 (

 21 Burstein and Mansour [6, Th. 2.1]) Let τ = 11 . . . 1 ∈ [1] l be a subword pattern. Then

Example 2 . 3 (

 23 seeBurstein and Mansour [6, Th. 3.10]) Letting l = 3 and y = 0 in Theorem 2.2, we get that the generating function for the number of words in [k] n avoiding the subword pattern 112 is given by

1

 1

  On the other hand, suppose σ ∈ [k] n is counted by D τ (x, y; k).Then (σ, k + 1) = σ 0 kσ 1 k . . . kσ d k + 1 (where σ i ∈ [k -1] n for all i) contains the pattern τ exactly r times. If d = 0, then σ ∈ [k -1] n . If d ≥ 1,there are several possibilities. If σ d = / 0 or σ d = σ d-1 = / 0, then all occurrences of the pattern τ in (σ, k +1) are in (σ i , k) for some i = 0, 1, . . . , d -1, or in (σ d , k + 1). If σ d = / 0 and σ d-1 = / 0, then there is one extra occurrence of τ since (σ, k + 1) ends by (a, k, k + 1) for some a < k. Taking generating functions, we obtain D τ (x, y; k) =D τ (x, y; k -1) + ∑ d≥1 x d D d τ (x, y; k -1)(D τ (x, y; k -1) -1)

Theorem 4 . 1

 41 Let τ, τ ′ ∈ [m] l be two primitive subword patterns such that there exists a permutation Φ ∈ S l with Φ(1) = 1, Φ(l) = l and τ ′ = Φ • τ. In other words, τ and τ ′ have the same supply of each letter, the same first letter and the same last letter. Then τ and τ ′ are in the same strong Wilf class.

Corollary 4 . 2 Theorem 4 . 3

 4243 The subword patterns 1232 and 1322 are in the same strong Wilf class. All primitive subword patterns τ ∈ [m] l such that τ(1) = a and τ(l) = b, where a < b, are in the same strong Wilf class.Proof: Similarly as in the proof of Theorem 2.7, we getF τ (x, y; k) = F τ (x, y; k -1) + xF τ (x, y; k -1)D τ (x, y; k; a),where D τ (x, y; k; h) is the generating function for the number of words σ ∈ [k] n such that (h, σ) contains τ exactly r times.Now let us consider the caseh = a + p(ba). Let σ = (σ ′ , h + ba, σ ′′ ), where σ ′ is a word on the letters in [k] which does not contain h + ba. Using the fact that τ is a primitive subword pattern, we getD τ (x, y; k; h) = D τ (x, y; k -1; h) + x l-1 y h -1 a -1 k -(h + ba) mb D τ (x, y; k; h + ba) + x F τ (x, y; k -1)x l-2 h -1 a -1 k -(h + ba) mb D τ (x, y; k; h + ba).

Corollary 4 . 4 Corollary 4 . 5 1.Theorem 4 . 6 Corollary 4 . 7

 44454647 Let τ, τ ′ ∈ [m] l be two primitive subword patterns such that τ(1) = τ ′ (1) = a and τ(l) = τ ′ (l) = b, where a < b. Then the subword patterns aa . . . a p τ b . . . bb p and aa . . . a p τ ′ b . . . bb p are in the same strong Wilf class. Theorem 4.3 implies as well the following corollary. The subword patterns 1132, 1232, 1322, and 1332 are in the same strong Wilf class. 2. The subword patterns 1432 and 1342 are in the same strong Wilf class. Let 12τ1 ∈ [m] l+3 be a primitive subword pattern, and let τ ′ be the same pattern τ with 1 replaced by 2. Then the subword patterns 12τ13 and 12τ ′ 23 are in the same strong Wilf class.Proof: If σ ∈ [k] n contains 12τ13 exactly r times, then we define σ ′ as follows. If (σ i , . . . , σ i+l+3 ) is an occurrence of 12τ13, then we define σ ′ i+ j = σ i + 1 for all j such that σ i+ j = σ i . The function f defined by f (σ) = σ ′ is a bijection since 12τ1 is a primitive subword pattern.✷ The subword patterns 1213 and 1223 are in the same strong Wilf class.

  hence the result follows. ✷ 2.2 The subword pattern τ = 211 . . . 112 Let τ = 211 . . . 112 ∈ [2] l be a subword pattern. We define d τ (n, r; k) to be the number of words β ∈ [k] n such that (k + 1, β, k + 1) contains τ exactly r times, and denote the corresponding generating function by D τ (x, y; k). Let σ ∈ [k] n such that σ(τ) = r, and such that σ contains d occurrences of the letter k. For d = 0, the generating function for the number of such words σ is given by F

τ (x, y; k -1), and for d ≥ 1, by x d F 2 τ (x, y; k -1)D d-1 τ (x, y; k -1) (since in that case σ = σ 0 kσ 1 k . . . kσ d-1 kσ d , where all

Acknowledgement

The authors would like to thank the anonymous referee for bringing several references, particularly [18], to their attention. The final version of this paper was written while the second author (T.M.) was visiting University of Haifa, Israel in January 2003. He thanks the HIACS Research Center and the Caesarea Edmond Benjamin de Rothschild Foundation Institute for Interdisciplinary Applications of Computer Science for financial support, and professor Alek Vainshtein for his generosity.


F Chazal
email: fchazal@u-bourgogne.fr

V Maume-Deschamps

Statistical properties of Markov dynamical sources: applications to information theory

Keywords: dynamical sources, information theory, transfer operator, markov sources

In (V1), the author studies statistical properties of words generated by dynamical sources. This is done using generalized Ruelle operators. The aim of this article is to generalize the notion of sources for which the results hold. First, we avoid the use of Grothendieck theory and Fredholm determinants, this allows dynamical sources that cannot be extended to a complex disk or that are not analytic. Second, we consider Markov sources: the language generated by the source over an alphabet M is not necessarily M * .

Introduction

Statistical properties of words describe the asymptotic behavior (or laws) of parameters such as "most probable prefixes," "coincidence probability" etc. These analyses have many applications in analysis of algorithms, pattern matching, study of tries, optimization of algorithms... Of course, statistical properties of words heavily depend on the way the words are produced.

In information theory contexts, a source is a mechanism which emits symbols from an alphabet M (finite or infinite countable) to produce (infinite) words. The two "classical" simpler models are memoryless sources where each symbol is emitted independently of the previous ones and Markov chains where the probability for a symbol to be emitted depends on a bounded part of the past. Sources encountered in practical situations are usually complex mechanisms, and one needs general models to study the statistical properties of emitted words (e.g. the distribution of the prefixes of the same fixed length) and the parameters of the sources (e.g. entropy). In (V1), B. Vallée introduces a model of probabilistic dynamical source which is based upon dynamical systems theory. It covers classical sources models (that is memoryless, some Markov chains) and some other processes with unbounded dependency on past history. A probabilistic dynamical source consists of two parts: a dynamical system on the unit interval [0, 1] representing the mechanism which produces words and a probability measure. More precisely, a dynamical source is defined by: Let f be a probability density on I. Words on the alphabet M are produced in the following way: first, x ∈ I is chosen at random with respect to the probability of density f , second, the infinite word M(x) = (σ(x), σ(T x),

• • • , σ(T k x), • • • ) is associated to x.
The main tool in the analysis of such sources is a "generating operator," the generalized Ruelle operator depending on a complex parameter s and acting on a suitable Banach space. To derive results about the source, this operator must have a simple dominant eigenvalue λ(s) defined for s in a neighborhood of the real axis. Thus some additional hypotheses on the mapping T are needed. For example, in the context of (V1), branches T |I m need to be real analytic with a holomorphic extension to a complex neighborhood of [0, 1], complete (i.e. T (I m ) = I) and they need to satisfy a bounded distortion property (see (C,M,V)).

Such sources produce the set M * of all the words on the alphabet M . The analyticity of T allows to use the powerful Grothendieck theory and Fredholm theory on operators on spaces of holomorphic functions. The aim of this work is to prove that the hypothesis of analyticity and completeness may be relaxed. We extend the results of (V1) to a larger class of P-Markov sources (see Definition 1). Our class contain various classes of examples of interest such as Markov sources on a finite alphabet, Markov sources with finitely many images or Markov sources with large images (see Section 2.1 and Figure 1).

The dominant eigenvalue function s → λ(s) is involved in all the results of the paper. First of all, Secondly, statistical properties of word emitted by the source depend on λ(s):

• the number B(x) of finite words whose probability is at least x, satisfies B(x) ≃ 1 λ ′ (1)x if the source is not conjugate to some source with affine branches.

• let ℓ k (x) be the probability of words having the same prefix of length k as x. This random variable follows asymptotically a log-normal law provided that the function s → log λ(s) is not affine.

• the random variable C(x, y) which is the length of the longest common prefix of the two words associated to x, y ∈ [0, 1] follow asymptotically a geometric law with ratio equal to λ(2) if the x and y are drawn independently.

These results, proven by B. Vallée for holomorphic dynamical sources, remain valid in our setting and are explicitly stated in the following main theorem. Before stating the main theorem, let us recall that two dynamical systems T , T : I → I are conjugate if there exists an homeomorphism g of I such that T = g • T • g -1 . Roughly speaking, from a measurable dynamical point of view, if g is piecewise C 1 the systems are the same.

Theorem Consider a P-Markov source and f a density of probability, which is bounded, Lipschitz on each I m with uniformly bounded Lipschitz constant. Then there exists an analytic function s → λ(s) on a complex neighborhood of R (s) ≥ 1 such that:

• Either there exist α > 1 and a sequence of integers (k m ) m∈M such that the map T is conjugated to a piecewise affine map with slopes α k m on I m , with the conjugacy C 1+Lip on each I m . In that case, there exists A, B such that

A x ≤ B(x) ≤ B x , or B(x) ≃ -1 λ ′ (1)
x .

• If λ ′′ (1) -λ ′ (1) 2 = 0 then the variable log ℓ k follows asymptotically a normal law. Moreover λ ′′ (1) -λ ′ (1) 2 = 0 if and only if the map T is conjugated to a piecewise affine map with slopes all equal, the conjugacy is C 1+Lip on each I m .

• The variable C follows asymptotically a geometric law with ratio equal to λ(2) if the x and y are drawn independently.

As an immediate corollary we can give an answer to Conjecture 2 of (V1).

Corollary Exceptional sources are those for which there exist α > 1 and a sequence of integers (k m ) m∈M such that the map T is conjugated to a piecewise affine map (not necessarily complete) with slopes α k m on I m , with the conjugacy C 1+Lip on each I m .

As a consequence of the proof of main theorem, we solve Conjecture 1 of (V1) (see Remark 4).

Let us quickly present the strategy underlying the proof of the previous theorem. Important objects involved in the analysis of the sources are fundamental intervals: given a prefix h of length k ∈ N, the set of words starting with this prefix is an interval in [0, 1], the fundamental interval associated to h. Its measure (with respect to the probability density f ) is denoted by u h . It is not difficult to prove that all the studied quantities can be expressed in terms of the Dirichlet series of the fundamental measures:

Λ k (F, s) = ∑ h∈L k u s h and Λ(F, s) = ∑ k≥0 Λ k (F, s)
where L k is the set of prefixes of length k (lemma 2.1). For P-Markov sources, these series define holomorphic functions of the variable s which admit a meromorphic extension to a half plane. Next we prove that these series can be expressed in terms of the generalized Ruelle operator. A careful study of spectral properties of Ruelle operators is then used to describe the singularities of Dirichlet series. Finally, parameters of the source are derived by mean of "classical" techniques: Tauberian theorem and Mellin transforms. This last part being exactly the same as in (V1 analysis of trie (or digital tree) structure. Tries are tree data structures widely used in order to implement a search in a dictionary. They are constructed from a finite set X = {w 1 , • • • , w n } of words independently generated by a source. The nodes of the trie are used to manage the search in the dictionary, and each leaf contains a single word of the dictionary. Formally, given a finite alphabet M = {a 1 , . . . , a r }, the trie associated to X is defined recursively by trie(X) = trie(X \ a 1 ), . . . , trie(X \ a r ) , where X \ a i is the subset of X consisting of words which begin with a i with their first symbol a i removed. The recursion is halted as soon as X contains less than 2 elements (see figure 2). We are concerned with the standard parameters of trees: for example, size, path length, height. The structure of tries have been intensively studied in the setting of independent sources (see (Sz) for example). The analysis of trie structures has been done recently in the setting of complete holomorphic sources by J. Clément, P. Flajolet and B. Vallée (C,F,V), (C) : roughly speaking, the expected values of size, path-length and height of tries can be expressed in terms of fundamental measures of the source and of Dirichlet series of fundamental measures. Thus the asymptotic behavior of these parameters is deduced from the spectral properties of some generalized Ruelle operators related to the source: some of these operators are defined over Banach spaces of functions of 4 variables. The definitions and spectral properties of these operators immediately extend to our setting.

Theorem Let S be a P-Markov source. Denote by S [n] , P [n] , H [n] the size, the path-length and the height of a trie constructed over n independently drawn words of S. The asymptotic expected value (when n → ∞) of these parameters is given by E[S [n] ] ≃ n h(S ) E[P [n] ] ≃ n log n h(S ) E[H [n] ] ≃ log n 2| log c(S )| where h(S ) is the entropy of the source and c(S ) is the coincidence probability of S.

The paper is organized as follows. In section 2, we give precise definitions and statement of results.

In section 3, we analyze the parameters of the source assuming some spectral properties of generalized Ruelle operators associated to our sources. In section 2.1 we consider some general classes of systems that satisfy our hypothesis and give some specific examples (in particular we exhibit a source that satisfy our hypothesis but that does not admit a complex extension). Finally, section 4 contains the proof of the spectral properties. Acknowledgments: We are grateful to B. Vallée, P. Flajolet and J. Clément for interesting us in the theory of dynamical sources and for fruitful discussions. Many of these discussions were made possible thanks to a partial financial support of ALEA project.

Dynamical sources, intrinsic parameters and transfer operators

The following definition of dynamical sources extend B. Vallée's one. We try to give the minimal conditions ensuring that the generalized Ruelle operator associated to such a source is quasi compact on a "natural" Banach space. We call these sources P-Markov dynamical sources (for positive Markov dynamical sources).

Definition 1 A dynamical P-Markov source is defined by the four following elements : Remark 1 (see the definition of operators G s in section 2.2) The first part of condition ( d2) is sufficient to have that the sum defining G s Id converges uniformly. Because the source is not necessarily complete, it does not imply the second part of condition (d2).

Condition (d5) is a bit stronger than (d2), it implies that for all m ∈ M , there exists N ∈ N such that:

inf x∈I G N s [1 I m ](x) > 0.
Remark 2 If the alphabet M is infinite then Condition (d2) is equivalent to:

lim |Q |→∞ Q ⊂M Q f inite sup x∈I ∑ m∈M m ∈Q δ s m 1 J m (x) = 0. (2.1)
If the alphabet is finite then Condition (d2) is always satisfied.

A Markov source A non Markov source Such a source produces words on the alphabet M , to each x ∈ I we associate the infinite word

I c I b I a J b J a = J c
M(x) = (σ(x), σ(T x), • • • , σ(T k x), • • • ). For k ∈ N, the kth prefix of M(x) is P k (x) = (σ(x), σ(T x), • • • , σ(T k-1 x)).
We denote by L k the subset of M k of prefixes of length k that may be produced by the dynamical source. Remark that in our setting, L k may be a strict subset of M k . For example in Figure 3, the word bc does not belong to L 2 . In the following, each element of L k will be identified with an inverse branch of

T k of the form h = h m 1 • • • • • h m k , m i ∈ M . Let J h be the definition interval of h ∈ L k and I h = h(J h ) = [a h , b h ] the fundamental interval of h. If h = h i k • • • • • h i 1 ∈ L k then because of the Markov property, J h = J i 1 . Define also η h = inf x∈J h |h ′ (x)|, and δ h = sup x∈J h |h ′ (x)|.
Remark that P-Markov sources are a generalization of memoryless and classical Markov sources. Indeed, if the inverse branches h m are affine (or equivalently if h ′ m is constant) and complete (i.e. J m = I) then the symbols emitted σ(x), σ(T x) ... are independent (i.e. the source is memoryless). If the inverse branches are affine but not complete then the symbols emitted σ(x), σ(T x) ... form a Markov chain (see Figure 4). We are now in position to express the positivity condition (d5).

Condition 1 For all m ∈ M , for all s > γ, there exists N ∈ N such that

inf x∈I ∑ h∈L N η s h 1 I m (h(x))1 J h (x) > 0. (2.2)
This condition is related to the aperiodicity condition of classical Markov chains. Indeed in the context of Markov (infinite) chains on an alphabet M , let P be the (infinite) transition matrix. Then for s = 1, Condition (2.2) is equivalent to the following:

For all m ∈ M , there exists N ∈ N such that the infimum of the coefficients of the mth column of the matrix P N is strictly positive. If the alphabet M is finite this is equivalent to: there exists N ∈ N such that all the coefficients of the matrix P N are strictly positive (i.e. the Markov chain is aperiodic). This point of view is developed in section 2.1.1 below.

Let us give some examples of sources satisfying our hypothesis.

Examples of P-Markov sources.

It is straightforward that complete holomorphic sources with bounded distortion ((V1), (C,M,V)) are P-Markov dynamical sources.

Some examples.

Let us give some large classes of sources satisfying our hypothesis. The simplest class is given by finite aperiodic Markov maps. Let us recall that a Markov map (i.e. a dynamical system satisfying (d4) is strongly aperiodic if there exists M ∈ N such that for any i, j ∈ M , for any n ≥ M,

T -n I j ∩ I i = / 0.
The strong aperiodicity condition is natural in the context of Markov maps (in some sense it means that the systems is not decomposable). It may be rewritten in terms of inverse branches as: there exists M ∈ N such that for n ≥ M, for any i, j ∈ M , there exists h ∈ L n with I i ⊂ J h and h(J h ) ⊂ I j . Let us show that it suffices to ensure (d5) if the alphabet is finite, if the number of images is finite or if the system has large branches.

Example 1 If M is finite and the system is strongly aperiodic then it defines a P-Markov.

Indeed, the only point to verify is (d5). The aperiodicity condition implies that for all n ≥ M, all x ∈ I and m ∈ M , there exists h ∈ L n with x ∈ J h and I h ⊂ I m . Thus we have:

for m ∈ M , x ∈ I, n ≥ M, ∑ h∈Ln x∈J h η s h 1 I m (hx) ≥ inf h∈L n η s h .
Remark that Markov chains on a finite alphabet may always be obtained from an affine dynamical source. Thus, aperiodic Markov chains are P-Markov sources.

Example 2 If the set {J m / m ∈ M } is finite and the system is strongly aperiodic then it defines a P-Markov source provided ( d2) and ( d3) are satisfied. Indeed, let J i 1 , . . ., J i k be the images of the system. The strong aperiodicity condition implies that for all n ≥ M, all m ∈ M and all j = 1, . . . , k, there exits h i j ∈ L n such that h i j (J i j ) ⊂ I m . Now,

∑ h∈Ln x∈J h η s h 1 I m (hx) ≥ inf j=1,...,k η s h i j
.

We would say that a source has large images if

inf m∈M {|J m |} > 0.
Example 3 If the source has large images and is strongly aperiodic then it defines a P-Markov source provided ( d2) and ( d3) are satisfied.

It suffices to remark that if the source has large branches and is strongly aperiodic then there exists finitely many J m whose union is I. Then the same argument has above shows that (d5) is satisfied.

A P-Markov source with small branches.

For

0 < θ < 1, let C = 1 1-θ . Consider a partition of I into intervals I m with |I m | = Cθ m , m ≥ 0. Consider the piecewise affine map T such that T (I 2m ) = I m , m ≥ 1, and T (I 2m+1 ) = I, m ≥ 0. We have for all m, η m = δ m and δ 2m = θ m , δ 2m+1 = θ 2m+1 . Condition (d2) is satisfied. Let us show that (d5) is also satisfied. If m = 2 k (2p + 1), k ≥ 0 then for all x ∈ I, ∑ h∈L k+1 x∈J h η s h 1 I m (h(x)) ≥ θ 2p+1 θ 2(2p+1) • • • θ 2 k (2p+1) .
This source is represented in Figure 5.

I 1 I 2 I 3 I 4 I 5 • • •

Fig. 5: A source with small branches

From now on, we have emphasized that our hypothesis allow various geometric behavior of the branches, let us now give an example showing that relaxing the holomorphic extension hypothesis of (V1) is a substantial gain.

A P-Markov source with no extension on a complex neighborhood.

Consider the source whose alphabet is N * and inverse branches are given by

h n (x) = 1 n + 1 +C n ( f n (x) -f n (0))
where

f n : [0, 1] → R is defined by f n (x) = x - 1 x √ n + 1 - 1 √ n(x √ n + 1) -2 log(x √ n + 1) √ n
and C n is a constant defined by

C n = ( 1 n - 1 n + 1 ) 1 f n (1) -f n (0) = 1 2(n + 1) √ n( √ n -log( √ n + 1)) .
For all n ∈ N, the branch

h n maps I = [0, 1] onto interval [ 1 n+1 , 1 n ]. The derivative of h n is h ′ n (x) = C n f ′ n (x) = C n x 2 + 1 √ n (x + 1 √ n ) 2 and h ′ n (x) = 0 if and only if x = i/ 4 √ n or x = -i/ 4 √ n.
Hence this source does not satisfy condition (d2) in (V1): there is no complex neighborhood of [0, 1] on which all the h ′ n extend to a non vanishing function. Note that for any n,

C n 4n < h ′ n (x) < δ n for all x ∈ [0, 1] with δ n = C n √
n and for n sufficiently large,

δ n < 1 4n √ n for all x ∈ [0, 1].
It follows that there exists γ < 1 such that the series

∑ n∈N * δ s n converges on R (s) > γ. Now for any y ∈ [0, 1], |h ′′ n (y)| = C n √ n 2|y -1| (y + 1 √ n ) 3 ≤ 2C n √ n 1 √ n 3 2C n n 2 .
From previous inequalities, it results that for any x, y ∈ [0, 1],

|h ′′ n (y)| |h ′ n (x)| ≤ 8 n 2 √ n ≤ 8
so that the source is a P-Markov dynamical source.

Intrinsic parameters and transfer operators.

Recall that a function f on a metric space X is Lipschitz if there exists L ≥ 0 such that for all x, y ∈ X,

| f (x) -f (y)| ≤ Ld(x, y).
The smallest constant L satisfying this property is called the Lipschitz constant of f . The following definition introduces the notion of fundamental measures and the main parameters of the source ((V1)).

Definition 2 Fundamental measures and parameters of the source

Let f > 0 be a bounded, Lipschitz on each I m with bounded Lipschitz constants, probability density on I and F its associated distribution function. The fundamental measures are:

u h = |F(a h ) -F(b h )|, h ∈ [ k∈N * L k . For b > γ, denote by c b (F) the b-coincidence probability: c b (F) = lim k→∞ ∑ h∈L k u b h 1 k .
Let B(x) be the number of fundamental intervals whose measure is at least equal to x.

For k ∈ N * , ℓ k is the random variable defined by

ℓ k (x) = u h if x ∈ I h , h ∈ L k .
Finally, C is the random variable on I × I, defined by

C(x, y) = max{k ∈ N / P k (x) = P k (y)}.
The Dirichlet series of fundamental measures are:

Λ k (F, s) = ∑ h∈L k u s h and Λ(F, s) = ∑ k≥0 Λ k (F, s).
Lemma 2.1 (V1) The parameters of the source may be expressed in terms of Dirichlet series of fundamental measures:

c b (F) = lim k→∞ (Λ k (F, b)) 1 k . Λ(F, s) = s ∞ Z 0 B(x)x s-1 dx. E(ℓ s k ) = Λ k (F, s + 1). P(C ≥ k) = Λ k (F, 2) and E(C) = Λ(F, 2).
In (V1), the asymptotic behavior of Dirichlet series is obtained from spectral properties of generalized Ruelle operators associated to some analytic sources satisfying L k = M k for all k. In this paper, we prove that generalized Ruelle operators associated to P-Markov sources have the same dominant spectral properties. We relate Dirichlet series to these operators in our setting. So the analysis on the parameters of the source remain valid. Generalized Ruelle operators G s involve secants of inverse branches

H m (u, v) := h m (u) -h m (v) u -v
and are defined by

G s [Φ](u, v) := ∑ m∈M H s m (u, v)Φ(h m (u), h m (v))1 J m ×J m (u, v).
We are going to prove that these operators are quasi compact with unique and simple dominant eigenvalue λ(s) that coincide with the dominant eigenvalue of the "classical" Ruelle operator:

G s φ(u) := G s [Φ](u, u) with Φ(u, v) = φ(u).
Recall that the spectrum Sp(P) of a linear operator P acting on a Banach space B is the set of complex numbers λ such that Id -λP in not invertible. Such a spectral value λ may be either an eigenvalue (i.e. Id -λP is not injective) or Id -λP is not surjective.The spectral radius R(P) is the largest modulus of an element of Sp(P). An operator P is compact if the elements of Sp(P) \ {0} are eigenvalues of finite multiplicity. An operator P is quasi-compact if there exists 0 < ε < R(P) such that the elements of Sp(P) \ B(0, ε) are eigenvalues of finite multiplicity. The smallest such ε is called essential spectral radius Remark that condition (d2) ensures that the operator G s is well defined for R (s) > γ on bounded functions. Condition (d2) together with Taylor formula ensure that operators G s are well defined for R (s) > γ on bounded functions. Also, it is easy to see that:

✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✂ ✁✂
G k s Φ(x, x ′ ) = ∑ h∈L k H s h (x, x ′ )Φ(h(x), h(x ′ ))1 J h ×J h (x, x ′ ),
where H h is the secant function associated to h. In our setting, the relation between Dirichlet series and Ruelle operators is given by the following proposition.

Proposition 2.2 For all R (s) > γ, k ≥ 0, Λ k+1 (F, s) = ∑ m∈M |a m -b m | s G k s L s (a m , b m ), with L(x, x ′ ) = |F(x) -F(x ′ )| |x -x ′ | .
Proof. -For any m ∈ M , we have:

G k s L s (a m , b m ) = ∑ h∈L k (am,bm)∈J h ×J h H s h (a m , b m )L s (h(a m ), h(b m )) = ∑ h∈L k am∈J h |F(h(a m )) -F(h(b m ))| s |a m -b m | s = ∑ h∈L k am∈J h u s h•h m |a m -b m | s (remark that {h(a m ), h(b m )} = {a h•h m , b h•h m }). Now, any h ∈ L k+1 may be uniquely written as h = h • h m for some h ∈ L k and m ∈ M .
Our main theorem extends B. Vallée results to P-Markov dynamical sources.

Theorem 2.3 Consider a dynamical P-Markov source. There exist λ(s) > 0, Φ(s) > 0 and 0 ≤ ρ(s) < 1 three analytic functions on a complex neighborhood of the half line {s ∈ R / s > γ} such that for any k ≥ 1,

Λ k (F, s) = λ k (s) Φ(s) + O(ρ k (s)) . (2.3) λ(s)
is the dominant eigenvalue of G s on a suitable functional space.

Λ(F, s) is analytic on R (s) > 1 and has a simple pole at s = 1.

The variable C follows asymptotically a geometric law. If λ ′′ (1) -λ ′ (1) 2 = 0 then the variable log ℓ k follows asymptotically a normal law. Moreover, λ ′′ (1)λ ′ (1) 2 = 0 if and only if the map T is conjugated to a piecewise affine map with equal slopes, the conjugacy is C 1+Lip on each I m .

Either 1 is the only pole of Λ(F, s) on R (s) = 1, in that case

B(x) ≃ -1 λ ′ (1)x ,
or the map T is conjugated to a piecewise affine map with slopes of the form α k , α > 1, k ∈ Z, with conjugacy C 1+Lip on each I m . In that case, there exist A, B,

A x ≤ B(x) ≤ B x .
Theorem 2.3 is derived from dominant spectral properties of generalized real Ruelle operators. We will prove that these operators admit a unique maximal eigenvalue. To this aim, we use Birkhoff cones and projective metrics (( Bi1), ( Bi2)). These techniques have been introduced in dynamical systems by P. Ferrero and B. Schmitt ((F,S)) and have been widely used by dynamicians to study Ruelle operators in many different situations. Here, we will use these techniques to prove that both operators G s and G s are quasi-compact and have a unique and simple dominant eigenvalue, for real s > γ. We will give the proofs for G s , the proofs for G s may be obtained in the same way. Even for the operators G s , our setting is not covered by previous works (see for example (Bre), (M), (Sa)).

Of course the spectral properties of the operators G s and G s depend on the space on which they act.

Because the system is not assumed to be complete (i.e. we do not assume J m = I for all m ∈ M ), the operators G s and G s do not act on continuous functions. A function f is Lipschitz continuous on I m if there exists a constant K m > 0 such that for all x, y ∈ I m ,

| f (x) -f (y)| ≤ K m |x -y|.
The smallest number K m such that the above is satisfied is called the Lipchitz constant of f on I m . Let

f = f ∞ + Lip( f ).
It is easy to see (and will in fact follow from Lemma 3.2) that G s (resp. G s ) acts on L pw (I) (resp. L pw (J )). We postpone the proof of Theorem 2.4 to the end of the paper (see section 4). Let us show how to use it to get Theorem 2.3.

3 Analysis of the parameters of the source

Preliminary results

The following lemma is an easy application of the derivation chain rule, (d3) and the fact that all h m ,

m ∈ M are δ contractions with δ = sup m∈M δ m < 1. Lemma 3.1 For all k ∈ N * , for all h ∈ L k , x, y ∈ J h , h ′′ (x) h ′ (y) ≤ A(1 + A) 1 -δ := B.
Applying the integral Taylor formula at order 1 to h, the Taylor formula at order 1 to h ′ and Lemma 3.1

gives: for all k ∈ N * , for all h ∈ L k , X = (x, x ′ ), Y = (y, y ′ ) ∈ J h × J h , H h (X) H h (Y ) ≤ 1 + d(X,Y )B, (3.1) where d(X,Y ) = |x -y| + |x ′ -y ′ |. (3.2)
The following lemma proves that the operators G s , R (s) > γ satisfy a "Doblin-Fortet" or "Lasota-Yorke" inequality. We are going to use a result by H. Hénnion ((H)) to conclude that they are quasi-compact for some complex s, R (s) > γ. We could also use it to conclude that G s are quasi-compact for real s > γ then it would remain to prove that the dominant eigenvalue is unique and simple. This can be done "by hand" but we have preferred to give a self contained argument proving in the same time the quasi compactness and the dominant spectral property (see section 4).

Lemma 3.2 For all s, R (s) = σ > γ, there exists K > 0 such that for all f ∈ L pw (J ), for all n ∈ N,

Lip(G n s f ) ≤ δ n G n σ 1 ∞ Lip( f ) + K G n σ | f | ∞ (3.3) ≤ δ n G n σ 1 ∞ Lip( f ) + K G n σ 1 ∞ f ∞ .
Proof.

-Let X = (x, x ′ ), Y = (y, y ′ ) belong to the same I m × I m . In that case, the sets {h / |h| = n and X ∈ J h × J h } and {h / |h| = n and Y ∈ J h × J h } are the same. We compute:

|G n s f (X) -G n s f (Y )| ≤ ∑ h∈Ln X∈J h ×J h |H h (X)| σ | f (h(x), h(x ′ )) -f (h(y), h(y ′ ))| + ∑ h∈Ln X∈J h ×J h | f (h(Y ))|H h (Y ) σ H h (X) H h (Y ) s -1 ≤ δ n Lip( f )d(X,Y )G n σ (1)(X) +σBd(X,Y )(1 + Be σ )G n σ (| f |)(Y ),
(we have used (3.1)). This gives the result with K = σB(1 + Be σ ).

Let us state Hénnion's theorem and show that we can apply it.

Theorem 3.3 ((H)) Let (B,

• ) be a Banach space, let | • | be another norm on B and Q be an operator on (B, • ), with spectral radius R(Q). If Q satisfies:

1. Q is compact from (B, • ) into (B, | • |),
2. for all n ∈ N, there exist positive numbers R n and r n such that r = lim inf(r n )

1 n < R(Q) and for all f ∈ B, Q n f ≤ R n | f | + r n f
then Q is quasi-compact and the essential spectral radius is less than r.

We will use this theorem with B = L pw (J ) and |•| the sup norm. According to Lemma 3.2, in order to apply Theorem 3.3, we have to prove that the operators G s are compact from (L pw (J ), • ) into (L pw (J ), • ∞ ).

In other words, consider a sequence ( f n ) n∈N , f n ∈ L pw (J ) with f n ≤ 1, we have to prove that there exists a subsequence n k such that the sequence (G s f n k ) converges for the sup norm • ∞ . This will follow from remark 2.

Lemma 3.4 For all s such that R (s) > γ, G s is compact from (L pw (J ), • ) into (L pw (J ), • ∞ ).

Proof. -Let ( f n ) n∈N , f n ∈ L pw (J ) with f n ≤ 1, restricted to each I m × I m the functions f n are uniformly equicontinuous. We may apply Ascoli's theorem on each I m × I m and use a diagonal principle to find a subsequence n k such that the sequence f n k converges to some function f . Let us prove that G s f n k converges uniformly to G s f . Denote s = σ + it, let X = (x, x ′ ) ∈ J and Q a finite subset of M ,

|G s f n k (X) -G s f (X)| = ∑ m∈M X∈Jm×Jm H s m (X)( f n k (h m (x), h m (x ′ )) -f (h m (x), h m (x ′ )) ≤ ∑ m∈Q x∈Jm H σ m (X) f n k (h m (x), h m (x ′ )) -f (h m (x), h m (x ′ )) + ∑ m ∈Q x∈Jm H σ m (X) f n k (h m (x), h m (x ′ )) -f (h m (x), h m (x ′ )) ≤ G σ 1 ∞ sup m∈Q X∈Im×Im | f n k (X) -f (X)| + 2 ∑ m∈M , x∈Jm m ∈Q δ σ m (we have used that f n ∞ ≤ 1 and Taylor equality). Fix ε > 0, choose Q ⊂ M , Q finite, such that ∑ m ∈Q x∈Jm δ σ m < ε, now choose k 0 such that for k > k 0 , sup m∈Q X∈Im×Im | f n k (X) -f (X)| < ε
(this can be done because the convergence is uniform on each I m × I m and Q is finite). We have:

|G s f n k (X) -G s f (X)| ≤ ε( G σ 1 ∞ + 2).
In other words, G s f n k goes to G s f uniformly. Now the following result is a simple consequence of Theorem 3.3. For any s, R(s) denotes the spectral radius of G s .

Proposition 3.5 Let R (s) = σ > γ, either R(s) ≤ δR(σ) or G s is quasi-compact. In particular, for σ > γ, G σ is quasi-compact. Proof. -We have that R(σ) = lim n→∞ G n σ 1 1 n ∞ . Thus lim inf (δ n G n σ 1 ∞ ) 1 n = δR(σ).
The result follows.

To conclude the proof of Theorem 2.4, it remains to prove that for real s > γ, G s admits a unique simple dominant eigenvalue. We postpone this proof to section 4. Let us use Theorem 2.4 and Proposition 3.5 to obtain spectral properties of G s for complex parameters s.

Spectral properties for complex parameters s and properties of Dirichlet series

For real s > γ, by Theorem 2.4, we have that for any k ∈ N, f ∈ L pw (J ),

G k s f = λ k (s)Π s ( f ) + S k s f ,
where Π s is the spectral projection on the maximal eigenvalue and S s is an operator on L pw (J ) whose spectral radius strictly less than λ(s) and such that S s • Π s = Π s • S s = 0. Now Proposition 2.2 gives:

Λ k+1 (F, s) = ∑ m∈M |a m -b m | s G k s L s (a m , b m ) = ∑ m∈M |a m -b m | s λ k (s)Π s (L s )(a m , b m ) + S k s L s (a m , b m ) = λ k+1 (s) Φ(s) λ(s) + O(ρ k (s)) , with Φ(s) = ∑ m∈M |a m -b m | s Π s (L s )(a m , b m
) and ρ(s) the spectral radius of S s over λ(s). Remark that we have used that

∑ m∈M |a m -b m | s
converges which follows from (d2). Thus we have proved (2.3) of Theorem 2.3 for real s. The fact that it holds on a complex neighborhood of s > γ follows from perturbation theory (see for example Kato (K)).

We now prove Proposition 8, Proposition 9 and Proposition 10 of (V1) in our context. Remark that her proofs are based upon Fredholm determinant theory thus we have to use others arguments. Also, some changes are due to the fact that we work with functions f that are continuous on each I m but not on I. In particular, in general there does not exist x ∈ I such that f (x) = sup I f . Proposition 3.6

1. The function s → λ(s) is strictly decreasing along the real axis s > γ.

2. On each vertical line R (s) = σ, we have R(s) ≤ λ(σ).

3. If R(s) = λ(σ) for s = σ + it then G s has an eigenvalue λ = e ia λ(σ), a ∈ R that belongs to the spectrum of G s .

Proof. -From (2.3), we deduce that:

λ(s) = lim k→∞ Λ k (1, s) 1 k .
Since for all m ∈ M , h m is a δ-contraction, we deduce:

Λ k (1, s + u) = ∑ h∈L k |I h | s+u ≤ ∑ h∈L k δ u h |I h | s ≤ δ ku ∑ h∈L k |I h | s .
Thus, λ(s + u) ≤ δ u λ(s) and we have proved item 1.

To prove item 2, it suffices to remark that for

f ∈ L pw (J ), G k s f ∞ ≤ G k σ f ∞ . This together with Lemma 3.2 gives R(s) ≤ R(σ) = λ(σ).
Finally, if R(s) = λ(σ) then by Proposition 3.5, the operator G s is quasi compact and thus admits a eigenvalue λ = e ia λ(σ) of modulus λ(σ). Let Ψ s be such that G s Ψ s = λΨ s and ψ s (x) = Ψ s (x, x). Then G s ψ s = λψ s .

Let us study the spectral properties of G s for R (s) = 1. Let us remark that for any distribution F, we have

(see also Proposition 5 in (V1)), Λ k (F, 1) = 1.
Thus λ(1) = 1. For further use, let us denote ϕ 1 ∈ L pw (I) the eigenfunction of G 1 corresponding to the maximal eigenvalue λ(1) = 1 and satisfying m(φ 1 ) = 1. Then the measure ν = φ 1 m is T invariant.

Proposition 3.7 Let R (s) = 1, the operator may behave in two different ways.

1. Either for all s = 1, R (s) = 1, R(s) < 1 (the aperiodic case), 2. or the set of t ∈ R such that 1 belongs to the spectrum of G 1+it is of the form t 0 Z for some t 0 (the periodic case). In that case, the map T is conjugated to a piecewise affine map with slopes of the form α k , α > 1, the conjugacy is C 1+Lip on each I m . Moreover, there exists σ 0 < 1 such that on the strip {σ 0 < R (s) < 1} the operator (I -G s ) -1 has no pole.

Proof.

-Let s = 1 + it and assume that 1 belongs to the spectrum of G 1+it . Then using Proposition 3.6 we have that there exists f ∈ L pw (I) such that G s f = f . Let us prove that | f | is an eigenfunction for G 1 with eigenvalue 1. We have

| f | = |G s f | ≤ G 1 | f |. (3.4)
Recall that the Lebesgue measure is invariant by G 1 so that

Z I G 1 | f |(x)dx = Z I | f |dx.
As a consequence, inequality (3.4) must be an equality. Now, because of Theorem 2.4, 1 is simple as an eigenvalue of G 1 . Thus, let x) , multiplying if necessary f 1 by some constant, we may assume that |µ| ≡ 1. Following B. Vallée's proof of Proposition 9, we obtain that for all m ∈ M , x ∈ J m ,

f 1 > 0 be a dominant eigenfunction of G 1 . Let µ(x) = f (x) f 1 (
h ′ m (x) it µ • h m (x) = µ(x).
(3.5)

Reciprocally, let t be such that there exists a function µ satisfying (3.5) for all m

∈ M then f = µ • f 1 satisfies G 1+it f = f .
In other words, we have proved that 1 belongs to the spectrum of G 1+it if and only if there exists a function µ satisfying (3.5) for all m ∈ M . This implies that the set of real t such that 1 belongs to the spectrum of

G 1+it is a subgroup of R: if h ′ m (x) it µ t • h m (x) = µ t (x) and h ′ m (x) it ′ µ t ′ • h m (x) = µ t ′ (x) then h ′ m (x) i(t-t ′ ) µ t µ t ′ • h m (x) = µ t µ t ′ (x).
It cannot accumulate 0 because of the analyticity of s → λ(s) near s = 1. Thus it is of the form t 0 Z. There exists a real function θ ∈ L pw (I) such that µ = e iθ (recall that µ = f f 1 ∈ L pw (I)), take φ = exp( θ t ) and α = exp( 2π t ). Equation (3.5) becomes:

log |T ′ (x)| = θ(x) t - θ(T x) t + 2k(x)π t
where k(x) ∈ Z and is constant on each I m , and finally, equation (3.5) may be rewritten as:

|T ′ (x)| = φ(x) φ • T (x) α k(x) ,
Now, we may find constants c m and d m , m ∈ M such that the function

g(x) = c m Z x a m φ(t)dt + d m x ∈ I m is continuous, maps I into I, is invertible, is derivable on each I m with Lipschitz derivative on each I m . Derivating T = g • T • g -1
we obtain that T is piecewise affine with slopes α k . Let us prove the existence of a strip free of poles. There exists γ < σ 1 < 1 such that for any σ ∈]σ 1 , 1[, the operator G σ has no eigenvalue of modulus 1. Let σ 1 < σ 0 < 1 being such that δλ(σ) < 1 for all σ > σ 0 . Let σ ∈]σ 0 , 1[ and s = σ + iτ. Proposition 3.5 implies that either G s is quasi-compact or R(s) < 1 (in this last case 1 does not belong to the spectrum of G s ). So assume that G s is quasi-compact. If 1 is in the spectrum of G s , then it is an eigenvalue of G s (Theorem 3.3) and of G s . There exists f ∈ L pw (I) such that G s ( f ) = f . Using that α ikt 0 = 1 for any integer k, one deduces that 1 is an eigenvalue of the operators G σ+i(τ+kt 0 ) for any k ∈ Z. It follows that if there is no strip free of poles, then some of the points of the line R (s) = 1 are accumulated by a sequence of poles of Λ(F, s). This is a contradiction since Λ(F, s) is a meromorphic function in a neighborhood of R (s) = 1.

We now prove the log-convexity of s → λ(s). Such a property is necessary to study the random variable log ℓ k .

Proposition 3.8 The function s → log λ(s) is convex. Either it is strictly convex or it is affine. In this last case, the map T is conjugated to a piecewise affine map with slopes all equal. The conjugacy is C 1+Lip on each I m .

Proof. -We have to prove that for t ∈ [0, 1] and s > γ,

s ′ > γ, λ(ts + (1 -t)s ′ ) ≤ λ(s) t • λ(s ′ ) 1-t . (3.6) Consider the function ψ = f ts+(1-t)s ′ ( f s ) -t ( f s ′ ) -(1-t)
where f σ denote a dominant eigenfunction of G σ . We may normalize ψ to have sup I ψ = 1. Consider a sequence x n ∈ I such that ψ(x n ) → 1.

λ(ts + (1 -t)s ′ ) f ts+(1-t)s ′ (x n ) = ∑ h∈M |h ′ |(x n ) ts+(1-t)s ′ f ts+(1-t)s ′ (h(x n )) (3.7) ≤ ∑ h∈M |h ′ |(x n ) ts f s (hx n ) t • |h ′ |(x n ) (1-t)s ′ f s ′ (hx n ) 1-t ≤ ∑ h∈M |h ′ |(x n ) s f s (hx n ) t • ∑ h∈M |h ′ |(x n ) s ′ f s ′ (hx n ) 1-t (3.8) = λ(s) t f s (x n ) t • λ(s ′ ) 1-t f s ′ (x n ) 1-t .
(3.8) follows from Hölder inequality. Taking the limit when n → ∞ gives (3.6). λ being analytic, if equality holds in (3.6) for some s, s ′ , t then log λ is affine. In this last case, it remains to prove that the map T is conjugated to a piecewise affine map with slopes all equal. Assume that log λ is affine then there exists a < 1 such that λ(s) = a s-1 . Choose s, s ′ , t such that ts

+ (1 - t)s ′ = 1, let us show that f t s • f 1-t s ′ is a dominant eigenfunction of G 1 . Hölder inequality implies that G 1 ( f t s • f 1-t s ′ ) ≤ f t s • f 1-t s ′ .
As in the proof of Proposition 3.7, we use that G 1 leaves Lebesgue measure invariant to conclude that

G 1 ( f t s • f 1-t s ′ ) = f t s • f 1-t s ′ .
As a consequence, ψ ≡ 1 and equality holds in (3.7) for all x ∈ I. This implies that there exists a function k :

I → R + such that for all h ∈ M , |h ′ (x)| s f s (hx) = k(x)|h ′ (x)| s ′ f s ′ (hx).
Summing over h ∈ M and noting φ(x) =

f s (x) f s ′ (x) we get that φ(x) = k(x) λ(s) λ(s ′ )
and then T satisfy a cocycle relation:

|h ′ (x)| s-s ′ φ • h(x) = λ(s) λ(s ′ ) φ(x) for all h ∈ M .
(3.9)

Following the end of the proof of Proposition 3.7, we conclude that T is conjugated to a piecewise affine map with slopes all equal to 1 a .

Remark 4 By the way, the cocycle argument used in the proofs of Proposition 3.7 and 3.8 resolve Conjecture 1 of B. Vallée: A source is similar to a source with affine branches if and only if it is conjugated to a source with affine branches. The conjugacy is C 1+Lip on each I m .

Sources similar to a source with affine branches Periodic sources Log-affine sources Figure 7 shows relations between sources conjugated to piecewise affine sources. Let U(s) = log λ(s). With propositions 3.6, 3.7, 3.8 the analysis of parameters of the source done in sections 7, 8, 9 of (V1) apply to our setting without any change. To conclude the proof Theorem 2.3, it remains to verify that if the source is not log-affine then U ′′ (1) = 0. This is necessary to apply Hwang's quasi powers theorem and obtain the central limit theorem.

Proposition 3.9 Let U(s) = log λ(s). The following assertions are equivalent :

1. U ′′ (1) = 0,
2. there exist a C 1 function φ whose derivative belongs to the space L pw (I) such that for all s > γ, for

all h ∈ M , |h ′ (x)| s φ • h(x) = λ(s)φ(x).
Proof. -We apply Proposition 6.10 and Theorem 6.8 of (Bro) with the function

f = -log |T ′ | + Z I log |T ′ |dν
where ν is the probability measure which is T -invariant and absolutely continuous with respect to m. It is classical that

Z I log |T ′ |dν = -λ ′ (1).
Clearly, f ∈ L pw (I), also L pw (I) is dense in L 1 (ν). With A. Broise's notations (the operators Φ f (θ) are defined in (Bro), pp 37), we have:

G s (g) = e -(s-1)λ ′ (1) Φ f (s -1)(g).
So that if λ(s -1) is the dominant eigenvalue of Φ f (s -1) then λ(s -1) = e (s-1)λ ′ (1) λ(s). Since

U ′′ (1) = λ ′′ (1) -λ ′ (1) 2 λ(1) 2 ,
we deduce that U ′′ (1) = 0 if and only if λ′′ (0) = 0 which is equivalent to item 1. by Proposition 6.10 and Theorem 6.8 of (Bro).

Spectral properties of real generalized Ruelle operators

The aim of this section is to prove Theorem 2.4. Let us recall definitions and properties of cones and projective metrics (see (L) or (L,S,V) for a complete presentation).

Cones and projective metrics

The theory of cones and projective metrics of G. Birkhoff ( Bi1) is a powerful tool to study linear operators. P. Ferrero and B. Schmitt (F,S) applied it to estimate the correlation decay for random compositions of dynamical systems.

Definition 3 Let V be a vector space. A subset C ⊂ V which enjoys the following four properties

(i) C ∩ -C = / 0 (ii) ∀λ > 0 λC = C (iii) C is a convex set (iv) ∀ f , g ∈ C , ∀α n ∈ R , (α n → α, g -α n f ∈ C ) ⇒ (g -α f ∈ C ∪ {0}).
is called a convex cone.

We now define the Hilbert metric on C : Definition 4 The distance d C ( f , g) between two points f , g in C is given by

d C ( f , g) = log β( f , g) α( f , g)
where α and β are defined as

α( f , g) = sup{λ > 0|g -λ f ∈ C } β( f , g) = inf{µ > 0|µ f -g ∈ C }
where we take α = 0 or β = ∞ when the corresponding sets are empty.

Remark 5 In the sequel we will use that β( f , g) = α(g, f ).

The distance d C is a pseudo-metric, because two elements can be at an infinite distance from each other, and it is a projective metric because any two proportional elements have a null distance.

Given two elements linearly independent f and g ∈ C , consider the intersection of C with the two dimensional vector space spanned by f and g. Its boundary is the union of two half lines ℓ 1 , ℓ 2 . The distance d C ( f , g) is the log of the cross-ratio of the four half lines ℓ 1 , ℓ 2 , f , g (see figure 8).

Remark 6 For example, if V is a space formed with real valued functions and C + the cone of positive functions then an easy computation gives:

d C + ( f , g) = sup f inf f sup g inf g . ℓ 2 C g f ℓ 1
Fig. 8: Projective metric Definition 5 Let V be a vector space, C ⊂ V a convex cone, a linear operator L :

V → V is called a positive operator if LC ⊂ C .
The next theorem, due to G. Birkhoff [START_REF]Birkhoff Lattice theory[END_REF], shows that every positive linear operator is a contraction, provided that the diameter of the image is finite.

Theorem 4.1 Let V be a vector space, C ⊂ V a convex cone (see definition above) and L : V → V a positive linear operator. Let d C be the Hilbert metric associated to the cone C . If we denote

∆ = sup f ,g∈L(C ) d C ( f , g) , then d C (L f , Lg) ≤ tanh ∆ 4 d C ( f , g) ∀ f , g ∈ C
(tanh(∞) = 1).

Remark 7 Theorem 4.1 implies that if C 1 and C 2 are two convex cones such that C 1 ⊂ C 2 then for any f

, g ∈ C 1 , d C 2 ( f , g) ≤ d C 1 ( f , g).
(apply Theorem 4.1 with L = Id). In particular, if

C ⊂ C + then for f , g ∈ C , d C ( f , g) ≥ sup f inf f sup g inf g .
Theorem 4.1 alone is not completely satisfactory: given a cone C and its metric d C , we need to relate the distance d C with a suitable norm on V . The following lemma provides such a relation. Lemma 4.2 (L,S,V) Let • be a norm on V such that

∀ f , g ∈ V f -g, f + g ∈ C ⇒ g ≤ f
and let ℓ : C → R + be a homogeneous and order preserving function, i.e.

∀ f ∈ C , ∀λ ∈ R + ℓ(λ f ) = λℓ( f ) ∀ f , g ∈ C g -f ∈ C ⇒ ℓ( f ) ≤ ℓ(g) , then ∀ f , g ∈ C ℓ( f ) = ℓ(g) > 0 ⇒ f -g ≤ (e d C ( f ,g) -1) min( f , g )

Proof of Theorem 2.4

We

d C (G k+n s f , G n s f ) ≤ tanh ∆ 4 n-1 ∆ = κ n-1 ∆. (4.1)
We deduce (using Lemma 4.2 with ∞ as homogenous form) that the sequence of lines generated by (G n s f ) n∈N is a Cauchy sequence and converges to a line generated by an eigenvector Ψ s . This eigenvector corresponds to an eigenvalue λ(s). On another hand, we construct an eigenvector ν s for the dual operator. Then Lemma 4.2 (applied with ν s as homogenous form) and equation (4.1) give that

G n s f λ(s) n -Ψ s ν s ( f ) ∞ (4.2)
goes to zero exponentially fast for any f ∈ C . Then we have to extend this result from the cone to the Banach space of piecewise Lipschitz functions (this is done using Lemma 4.9 below). The fact that (4.2) goes to zero exponentially fast implies that λ(s) is the unique dominant eigenvalue of G s .

The following lemma proves the existence of a real positive eigenvalue for the dual operator of G s .

The corresponding eigenvector is indeed a measure. Recall that is V is a topological Banach space, it topological dual V ′ is endowed with the weak topology that is: a sequence (ν n ) n∈N of elements of V ′ converges to ν ∈ V ′ if and only if for any f ∈ V , the sequence (ν n ( f )) n∈N converges to ν( f ). Also, if L is a continuous linear operator on V then it defines a continuous linear operator L ′ on V ′ by: for ν ∈ V ′ , for any f ∈ V ,

L ′ (ν)( f ) = ν(L( f )).
Lemma 4.3 There exists a measure ν s on J and a positive number λ(s) such that for f ∈ L pw (J ),

ν s (G s f ) = λ(s) • ν s ( f ).
Proof. -Let L pw (J ) * be the topological dual of L pw (J ) (i.e. L pw (J ) * is the set of continuous linear forms on L pw (J )). Recall that the weak topology on L pw (J ) * is defined by: Γ n weakly converges to Γ ∈ L pw (J ) * if and only if for all f ∈ L pw (J ), Γ n ( f ) converges to Γ( f ). Let K ⊂ L pw (J ) * be the positive forms Γ of L pw (J ) * such that Γ(1) = 1. Define P s which maps K into itself by:

P s Γ( f ) = Γ(G s f ) Γ(G s 1) ,
(remark that the positivity condition (d5) implies that inf(G s 1) > 0). K is non empty, convex and weakly compact (see (Sc) Theorem XIX.7.7), P s is continuous on it for the weak topology. Then the Schauder-Tychonoff theorem ((D,S)) implies that it admits a fixed point ν s . We know that ν s is additive, to prove that it is a measure, we need to prove that it is σ-additive.

Restricted to each I m × I m , ν s may be identified to a measure (by Riesz representation theorem on compact spaces), in particular, we may compute ν s (1 I m ×I m ). To conclude that it is a measure on the union J of the I m × I m , it suffices to prove that:

ν s ( ∑ m∈M 1 I m ×I m ) = ∑ m∈M ν s (1 I m ×I m ).
This will follow from: lim

|Q |→∞ Q ⊂M Q f inite ν s ( ∑ m ∈Q 1 I m ×I m ) = 0.
We have:

ν s ( ∑ m ∈Q 1 I m ×I m ) = ν s G s (∑ m ∈Q 1 I m ×I m ) λ(s) and ν s G s (∑ m ∈Q 1 I m ×I m ) ≤ sup G s (∑ m ∈Q 1 I m ×I m ) (because ν s ∈ K is a positive form). Now, for all X = (x, x ′ ) ∈ J , G s ( ∑ m ∈Q 1 I m ×I m )(X) = ∑ n∈M X∈Jn×Jn H s n (X) ∑ m ∈Q 1 I m ×I m (h n (x), h n (x ′ )) = ∑ m ∈Q X∈Jm×Jm H s m (X) ≤ ∑ m ∈Q x∈Jm δ s m .
The result follows from (2.1) which is equivalent to Condition (d2) (see Remark 2).

The starting point of the construction of cones is usually a Lasota-Yorke inequality. Looking at Lemma 3.2, on sees that the operators G s improve the Lipschitz constant of piecewise Lipschitz functions, this explains condition 3 in the definition of the cone below. If the alphabet M was finite, we could manage with this condition and the positivity condition 2 below. The idea is that condition 3 provides a good control of the functions on each I m × I m and if the alphabet is finite, we may obtain a uniform control on the union of the I m × I m , iterating by G k s if necessary. Since we want to deal with infinite alphabet, we add condition 4 below which controls the functions on the complementary of a well chosen finite part Q of M .

Let Q be a finite subset of M such that:

sup x∈I ∑ m ∈Q x∈Jm δ s m < λ(s)δ.
The existence of such a subset Q follows from (2.1).

For a > 0, b > 0, let C a,b (s) be the set of functions f on J such that:

1. f ∈ L pw (J ), 2. ∀(u, v) ∈ J , f (u, v) > 0, 3. ∀m ∈ M , ∀(u, u ′ ) = U, (v, v ′ ) = V ∈ I m × I m , f (u, u ′ ) ≤ e ad(U,V ) • f (v, v ′ ) (the distance d(U,V ) has been defined in (3.1)), 4. for all m ∈ Q , for (u, v) ∈ I m × I m , f (u, v) ≤ bν s ( f ). Remark that C a,b (s) ⊂ L pw (J ) is a cone.
Remark 8 As mentioned in Remark 3, if the source is complete, G s acts on the space C 1 (I ×I) of functions that are C 1 on I × I. To get the dominant eigenvalue result on this space, it suffices to replace item 1 in the definition of the cone above by " f ∈ C 1 (I × I)".

Lemma 4.4

1. For all m ∈ M , ν s (I m × I m ) > 0. 2. For f ∈ C a,b (s), m ∈ M , X ∈ I m × I m , f (X) ≤ e 2a ν s ( f ) ν s (I m × I m ) .
Proof. -To prove Item 1, remark that (2.2) and Taylor equality imply that for all m ∈ M , there exists

N ∈ N such that inf X∈J G N s 1 I m ×I m (X) > 0. Now, ν s (1 I m ×I m ) = λ(s) -N ν s (G N s 1 I m ×I m ) > 0. Item 2.
follows from the definition of the cone (condition 3.) by integrating with respect to ν s on I m × I m . Lemma 4.5 For any s > γ, for any δ < ξ < 1, there exists a 0 > 0, b 0 > 0 such that for all a ≥ a 0 , b ≥ b 0 and for any k

∈ N * , G k s maps C a,b (s) into C ξa,ξb (s). Proof. -Let f ∈ C a,b (s). Because C ξa,ξb (s) ⊂ C a,b (s), it suffices to proof the lemma for k = 1. Let f ∈ C a,b (s), for anym ∈ M , X = (x, x ′ ), Y = (y, y ′ ) ∈ I m × I m , we have to compare: f (h m (x), h m (x ′ ))H s m (x, x ′ ) with f (h m (y), h m (y ′ ))H s m (y, y ′ ). Because f belongs to C a,b (s), and for each m ∈ M , h m is a δ-contraction, we have: f (h m (x), h m (x ′ )) ≤ e aδd(X,Y ) f (h m (y), h m (y ′ )).
(3.1) implies that:

H s m (x, x ′ ) ≤ e sBd(X,Y ) H s m (y, y ′ ). So, G s f (X) ≤ e ξad(X,Y ) G s f (Y ) provided a ≥ sB ξ -δ . Now, let X ∈ I m × I m with m ∈ Q . Let c := inf m∈Q ν s (I m × I m )
, c > 0 because of Lemma 4.4 and the fact that Q is finite. We have:

G s f (X) = ∑ m∈Q X∈Jm×Jm H s m (X) f (h m (x), h m (x ′ )) + ∑ m ∈Q X∈Jm×Jm H s m (X) f (h m (x), h m (x ′ )) ≤ e 2a c ν s ( f ) G s 1 ∞ + bν s ( f ) sup x∈I ∑ m ∈Q x∈Jm δ s m . Now, we use that ν s ( f ) = ν s (G s f ) λ(s) and since sup x∈I ∑ m ∈Q x∈Jm δ s m < λ(s)δ, we get: G s f (X) ≤ ν s (G s f ) ( e 2a G s 1 cλ(s) + bδ) ≤ bξν s (G s f ) provided b ≥ e 2a G s 1 λ(s)c(ξ-δ) . Lemma 4.6 Let a ≥ a 0 , b ≥ b 0 , there exists M such that for k ≥ M, the projective diameter ∆ of G k s C a,b (s) into C a,b (s) is finite: ∆ = sup f ,g ∈ C a,b (s) d C a,b (s) (G k s f , G k s g) < ∞. Proof. -Let f , g ∈ C ξa,ξb (s), let β > 0, we have that β f -g ∈ C a,b (s) if and only if: 1. β > g(x, x ′ ) f (x, x ′ ) for all (x, x ′ ) ∈ J . 2. β > e ad(X,Y ) g(y, y ′ ) -g(x, x ′ ) e ad(X,Y ) f (y, y ′ ) -f (x, x ′ ) := u(X,Y ) for all (x, x ′ ), (y, y ′ ) ∈ J . 3. β > bν s (g) -g(x, x ′ ) bν s ( f ) -f (x, x ′ ) := v(X) for all (x, x ′ ) ∈ I m × I m , m ∈ Q .
The quantity u(X,Y ) may be rewritten as: -ξ) One sees that we have to control the quantities sup J f , inf J f with respect to ν s ( f ). This cannot be done for all functions in C ξa,ξb (s) but it can be done for G k s f for f ∈ For all f ∈ C a,b (s), there exists m ∈ Q such that for all X ∈ I m × I m , f (X) ≥ εν s ( f ).

u(X,Y ) = g(y, y ′ ) f (y, y ′ )   e ad(X,Y ) -g(x,x ′ ) g(y,y ′ ) e ad(X,Y ) -f (x,x ′ ) f (y,y ′ )   , using that f , g ∈ C ξa,ξb (s), we get: u(X,Y ) ≤ g(y, y ′ ) f (y, y ′ ) e ad(X,Y ) -e -aξd(X,Y ) e ad(X,Y ) -e aξd(X,Y ) ≤ g(y, y ′ ) f (y, y ′ ) e a(1+ξ) 1 + ξ 1 -ξ . Moreover, because for all X ∈ I m × I m , m ∈ Q , 0 < f (X) ≤ bξν s ( f ), we have that v(X) ≤ ν s (g) ν s ( f )(1
Proof. -If the sublemma was false then for all m ∈ Q , there would exist X m ∈ I m × I m such that f (X m ) < εν s ( f ). Then, we would have:

ν s ( f ) = ∑ m∈M ν s ( f 1 I m ×I m ) = ∑ m∈ Q ν s ( f 1 I m ×I m ) + ∑ m ∈ Q ν s ( f 1 I m ×I m ) ≤ ∑ m∈ Q f (X m )e 2a ν s (1 I m ×I m ) + bν s ( f ) ∑ m ∈ Q ν s (1 I m ×I m ) < e 2a εν s ( f ) + b ν s ( f ) 2b < ν s ( f ) a contradiction.
Choose M > 0 such that, inf 2) is satisfied for m ∈ Q and N then (2.2) is also satisfied for m and kN for all k ∈ N * . Since Q is finite, we may take M a common multiple.

Sublemma 4.8 Let M be given by (4.5). There exist constants K 1 , K 2 such that for any k ≥ M, for any f ∈ C a,b (s), for all X ∈ J ,

K 2 ν s (G k s f ) ≤ G k s f (X) ≤ K 1 ν s (G k s f ).
(G k s f , G k s g) ≤ log sup G k s f inf G k s f • sup G k s g inf G k s g • e 2(1+ξ) • 1 + ξ 1 -ξ 2 ≤ log K 1 K 2 2 • e 2(1+ξ) • 1 + ξ 1 -ξ 2 .
Let K = log K 1 K 2 , we conclude that the projective diameter ∆ of G k s C a,b (s) into C a,b (s) is finite :

∆ ≤ 2K + 2a(1 + ξ) + 2 log 1 + ξ 1 -ξ .
The following lemma shows that any function in L pw (J ) may be pushed into the cone C a,b (s).

Lemma 4.9 There exists K 3 > 0 satisfying: for any function f ∈ L pw (J ), there exists R( f ) > 0 such that R( f ) + f ∈ C a,b (s) and R( f

) ≤ K 3 • f .
Proof. -Take R( f ) satisfying:

R( f ) ≥ sup | f |, R( f ) ≥ Lip( f ) -a inf f a , R( f ) ≥ sup f -b inf f b -1 .
We are now in position to prove that G s has a unique simple dominant eigenvalue. Let κ = tanh Now, apply Lemma 4.2 using ∞ and ν s to get:

G n+m s 1 λ(s) n+m - G n s 1 λ(s) n ∞ ≤ ∆κ n-1 • G n s 1 λ(s) n ∞ .
Now use again Lemma 4.2 to prove that G n s 1 λ(s) n ∞ is bounded:

G n s 1 λ(s) n - G s 1 λ(s) ∞ ≤ ∆ • G s 1 λ(s) ∞ .
So, the sequence G n s 1 λ(s) n n∈N is a Cauchy sequence (for the sup norm), thus it converges to some function Ψ s . This function satisfy G s Ψ s = λ(s)Ψ s and for any f ∈ C a,b (s),

G n s f λ(s) n -Ψ s ν s ( f ) ∞ ≤ ∆κ n-1 Ψ s ∞ ν s ( f ).
Lemma 4.9 implies that for any f ∈ L pw (J ),

G n s f λ(s) n -Ψ s ν s ( f ) ∞ ≤ ∆κ n-1 Ψ s ∞ (2K 3 + 1) f . (4.6)
We already know that G s is quasi compact (recall section 3). Now, equation (4.6) proves that λ(s) is a maximal eigenvalue (i.e. λ(s) = R(s) and any other eigenvalue has modulus strictly smaller than λ(s). In other words, λ(s) is simple and the unique eigenvalue of maximal modulus. The proof is the same for G s .

Let us denote λ(s) the dominant eigenvalue and ψ s the dominant eigenvector of G s . We have and the operators G s and G s coincide on the diagonal, we conclude that λ(s) = λ(s). ✷

  (a) A finite or infinite countable alphabet M . (b) A topological partition of I := [0, 1] into disjoint open intervals I m , m ∈ M , i.e. I = S m∈M I m . (c) A mapping σ which is constant and equal to m on each I m . 1365-8050 c 2004 Discrete Mathematics and Theoretical Computer Science (DMTCS), Nancy, France (d) A mapping T whose restriction to each I m is a C 2 bijection from I m to T (I m ) = J m .

Fig. 1 :

 1 Fig. 1: Geometry of sources

Fig. 2 :

 2 Fig. 2: An example of trie

  (a) An alphabet M , finite or infinite countable. (b) A topological partition of I := [0, 1] with disjoint open intervals I m , m ∈ M , i.e. I = S m∈M I m , I m =]a m , b m [. (c) A mapping σ which is constant and equal to m on each I m . (d) A mapping T whose restriction to each I m is a C 2 bijection from I m to T (I m ) = J m . Let h m : J m → I m be the local inverse of T restricted to I m . The mappings h m satisfy the following conditions: (d1) Contracting. There exist 0 < η m ≤ δ m < 1 for which η m ≤ |h ′ m (x)| ≤ δ m for x ∈ J m . (d2) There exists γ < 1 such that for R (s) > γ, the series ∑ m∈M 1 J m (x)δ s m converge uniformly for x ∈ I and ∑ m∈M |I m | s converges. (d3) Bounded distortion. There exists a constant A < +∞ such that for all m ∈ M and all x, y ∈ J m , Markov property. Each interval J m is union of some of the I k 's. (d5) Positivity. See Condition 1 below.

Fig. 3 :

 3 Fig. 3: Markov and non Markov sources

Fig. 4 :

 4 Fig. 4: Memoryless and classical Markov sources

Fig. 6 :

 6 Fig. 6: Spectrum of a quasi compact operator

  L pw (I) be the space of functions that are bounded and Lipschitz continuous on each I m , with the supremum of the Lipschitz constants on the I m 's finite. Denote by J ⊂ I × I the union of all sets I m × I m and let L pw (J ) the space of functions on J , that are bounded and Lipschitz continuous on each I m × I m , with bounded Lipschitz constant. In both cases, Lip( f ) will denote the sup of the Lipschitz constants on the I m 's or on the I m × I m 's. These spaces are endowed with the norm:

Theorem 2. 4 Remark 3

 43 For real s > γ, the operators G s (resp. G s ) act on L pw (J ) (resp. L pw (I)), they are quasi compact and have a simple dominant eigenvalue. This dominant eigenvalue λ(s) is the same for G s and G s . The corresponding eigenvectors are strictly positive and belong to L pw (J ) (resp. L pw (I)). If the source were complete (i.e. J m = I for all m) and the density function f is C 1 on I, then we could work with spaces of C 1 functions. In that case, G s acts on the space C 1 (I × I) of functions that are C 1 on I × I and G s acts on the space C 1 (I) of functions that are C 1 on I, they are quasi compact and have a simple dominant eigenvalue. This dominant eigenvalue λ(s) is the same for G s and G s . The corresponding eigenvectors are strictly positive and belong to C 1 (I × I) (resp. C 1 (I)). The only change in our proof would be in the definition of the cone in section 2.4 (see Remark 8).

Fig. 7 :

 7 Fig. 7: Exceptional sources

  C a,b (s) and k ≥ M, M large enough. To this aim, we need two sublemmas. The first one (Sublemma 4.7) proves there exists a finite subset Q ⊂ M such that a function in C a,b (s) is bounded from below at least on one I m × I m , m ∈ Q . Then Sublemma 4.8 proves that if k is large enough, for f ∈ C a,b (s), G k s f is bounded from below on all the I m × I m . Sublemma 4.7 Let ε = 1 2e 2a . Let Q be a finite subset of M which contains Q and satisfies: ∑ m ∈ Q ν s (I m × I m ) < 1 2b .

  exists because if (2.

Proof. -

 - From Lemma 4.5, we have that if f ∈ C a,b (s) then G p s f ∈ C a,b (s) for all p ∈ N. So, it suffices to prove the inequality for k= M. Since G M s f ∈ C a,b (s), we have for all X ∈ J : G M s f (X) ≤ ν s (G M s f ) max[b, e 2a c ].Now, using Sublemma 4.7, we findm 0 ∈ Q such that for X ∈ I m 0 × I m 0 , f (X) ≥ εν s ( f ). Now, for all X ∈ J , G M s f (X) ≥ εν s ( f )G M s (1 I m 0 ×I m 0 )(X) ≥ ν s ( f )εD. So the sublemma is proved with K 1 = max[b,e 2a c ] and K 2 = εD λ(s) M . Let us conclude the proof of Lemma 4.6. Equations (4.3) and (4.4) together with Sublemma 4.8 gives that for all f , g ∈ C a,b (s) and k ≥ M, d C a,b (s)

∆ 4 .

 4 Lemmas 4.5 and 4.6 and Theorem 4.1 give: ∀n, m ∈ N * , d C a,b (s) (G n+m s 1, G n s 1) ≤ κ n-1 d C a,b (s) (G m+1 s 1, G s 1) ≤ ∆κ n-1 .

  ), is not done in this paper. The reader is referred to B. Vallée's paper.

Let us mention that previous strategy initially developed by B. Vallée also has various important applications in the area of analysis of algorithms (especially for arithmetic algorithms), see (

V2

), (

V3

), (

V4

) for example. At last, an important application of the asymptotic behavior of the parameters of P-Markov sources is the

  are now going to use Theorem 4.1 and Lemma 4.2 to prove Theorem 2.4. Recall that we already know from Section 3 that the operators G s are quasi-compact for real s > γ. It remains to prove that they have a unique dominant eigenvalue ; we prove it for G s and leave to the reader the proof for G s . Let us sketch how to use cones to obtain the dominant spectral properties. To obtain a unique dominant eigenvalue, it is sufficient to find a cone C and an integer k such that G k s maps C into itself and the diameter ∆ of G k s C into C is finite. Indeed, the idea is that if f ∈ C then Theorem 4.1 applied n -1 times gives

	(κ = tanh ∆ 4 < 1):

  we have proven that if f , g ∈ C ξa,ξb (s)β( f , g) ≤ max sup

								.
	Remarking that	sup (y,y ′ )∈J	g(y, y ′ ) f (y, y ′ )	e a(1+ξ) 1 + ξ 1 -ξ	≥ sup (y,y ′ )∈J	g(y, y ′ ) f (y, y ′ )	,
			(y,y ′ )∈J	g(y, y ′ ) f (y, y ′ )	e a(1+ξ) 1 + ξ 1 -ξ	,	ν s (g) ν s ( f )(1 -ξ)	.	(4.3)

The same computation (recall that α( f , g) = β(g, f )) gives:

α( f , g) ≥ min inf (y,y ′ )∈J g(y, y ′ ) f (y, y ′ ) e -a(1+ξ) 1 -ξ 1 + ξ , ν s (g)(1 -ξ) ν s ( f ) . (4.4)