domain: info math

text:
Philippe Jacquet
email: philippe.jacquet@inria.fr

Dimitris Milioris
email: dimitrios.milioris@nokia-bell-labs.com

Wojciech Szpankowski

Joint String Complexity for Markov Sources: Small Data Matters *

Keywords: String complexity, joint string complexity, suffix trees, Markov sources, source discrimination, generating functions, Mellin transform, saddle point methods, analytic information theory

String complexity is defined as the cardinality of a set of all distinct words (factors) of a given string. For two strings, we introduce the joint string complexity as the cardinality of a set of words that are common to both strings. String complexity finds a number of applications from capturing the richness of a language to finding similarities between two genome sequences. In this paper we analyze the joint string complexity when both strings are generated by Markov sources. We prove that the joint string complexity grows linearly (in terms of the string lengths) when both sources are statistically indistinguishable and sublinearly when sources are statistically distinguishable. Precise analysis of the joint string complexity requires subtle singularity analysis and saddle point method over infinity many saddle points leading to novel oscillatory phenomena with single and double periodicities. To overcome these challenges, we apply analytic techniques such as multivariate generating functions, multivariate depoissonization and Mellin transform, spectral matrix analysis, and complex asymptotic methods.

Introduction

In the last decades, several attempts have been made to capture mathematically the concept of "complexity" of a sequence. The notion is connected with quite deep mathematical properties, including rather elusive concept of randomness in a string (see e.g., [START_REF] Ilie | Repetition Complexity of Words In Proc. COCOON[END_REF][START_REF] Li | Introduction to Kolmogorov Complexity and its Applications[END_REF][START_REF] Niederreiter | Some computable complexity measures for binary sequences[END_REF]), and the "richness of the language". The string complexity is defined as the number of distinct substrings of the underlying string. More precisely, if X is a sequence and I(X) is its set of factors (distinct subwords), then the cardinality |I(X)| is the complexity of the sequence. For example, if X = aabaa then I(X) = {ν, a, b, aa, ab, ba, aab, aba, baa, aaba, abaa, aabaa} and |I(X)| = 12 (ν denotes the empty string). Sometimes the complexity of a string is called the I-complexity [START_REF] Becher | A linearly computable measure of string complexity[END_REF]. This measure is simple but quite intuitive. Sequences with low complexity contain a large number of repeated substrings and they eventually become periodic.

In general, however, information contained in a string cannot be measured in absolute and a reference string is required. To this end we introduced in [START_REF] Jacquet | Common words between two random strings[END_REF] the concept of the joint string complexity, or Jcomplexity, of two strings. The J-complexity is the number of common distinct factors in two sequences. In other words, the J-complexity of sequences X and Y is equal to J(X, Y ) = |I(X) ∩ I(Y )|. We denote by J n,m the average value of J(X, Y ) when X is of length n and Y is of length m. In this paper, we study the joint string complexity for Markov sources when n = m.

The J-complexity is an efficient way of estimating similarity degree of two strings. For example, genome sequences of two dogs will contain more common words than genome sequences of a dog and a cat. Similarly, two texts written in the same language have more words in common than texts written in very different languages. Thus, the J-complexity is larger when languages are close (e.g. French and Italian), and smaller when languages are different (e.g. English and Polish); see Figures 12. In fact, texts in the same language but on different topics (e.g. law and cooking) have smaller J-complexity than texts on the same topic (e.g. medicine). Furthermore, string complexity has a variety of applications in detection of similarity degree of two sequences, for example "copy-paste" in texts or documents that will allow to detect plagiarism. It could also be used in analysis of social networks (e.g. tweets that are limited to 140 characters) and classification. Therefore it could be a pertinent tool for automated monitoring of social networks (see [START_REF] Burnside | One Day in Twitter: Topic Detection Via Joint Complexity[END_REF][START_REF] Milioris | Joint Sequence Complexity Analysis: Application to Social Networks Information Flow[END_REF] for some experimental results). However, real time search in blogs, tweets and other social media must balance quality and relevance of the content, which -due to short but frequent posts -is still an unsolved problem. For these short texts precise analysis is highly desirable. We call it the "small data" problem and we hope our rigorous asymptotic analysis of the joint string complexity will shed some light on this problem. In this paper we offer a precise analysis of the joint complexity together with some experimental results (cf. Figures 1 and2) confirming usefulness of the joint string complexity for text discrimination. To better model real texts, we assume that both sequences are generated by Markov sources making the analysis quite involved. To overcome these difficulties we shall use powerful analytic techniques such as multivariate generating functions, multivariate depoissonization and Mellin transform, spectral matrix analysis, and saddle point methods.

String complexity was studied extensively in the past. The literature is reviewed in [START_REF] Janson | On Average Sequence Complexity[END_REF] where precise analysis of string complexity is discussed for strings generated by unbiased memoryless sources. Another analysis of the same situation was also proposed in [START_REF] Jacquet | Common words between two random strings[END_REF] where for the first time the joint string complexity for memoryless sources was presented. It was evident from [START_REF] Jacquet | Common words between two random strings[END_REF] that precise analysis of the joint complexity is quite subtle requiring singularity analysis and infinite number of saddle points. In this paper we deal with the joint string complexity for Markov sources. To the best of our knowledge this problem was never tackled before except in our recent conference paper [START_REF] Jacquet | Joint String Complexity for Markov Sources, 23rd International Meeting on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms[END_REF]. As expected, its analysis is rather sophisticated but at the same time quite rewarding. It requires generalized (two-dimensional) dePoissonization and generalized (two-dimensional) Mellin transforms.

In [START_REF] Jacquet | Common words between two random strings[END_REF] it is proved that the J-complexity of two texts generated by two different binary memoryless sources grows as γ n κ √ α log n for some κ < 1 and γ, α > 0 depending on the parameters of the sources. When sources are statistically identical, then the J-complexity growth is O(n), hence κ = 1. When the texts are identical (i.e, X = Y ), then the J-complexity is identical to the I-complexity and it grows as n 2 2 [START_REF] Janson | On Average Sequence Complexity[END_REF]. Indeed, the presence of a common factor of length O(n) inflates the J-complexity to O(n 2 ), where n is the string length.

We should point out that our experiments indicate a very slow convergence of the complexity estimates for memoryless sources. Furthermore, memoryless sources are not appropriate for modeling many sources, e.g., natural languages. In this paper and [START_REF] Jacquet | Joint String Complexity for Markov Sources, 23rd International Meeting on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms[END_REF] we extend the J-complexity estimates to Markov sources of any order for a finite alphabet. Although Markov models are no more realistic in some applications than memoryless sources, they seem to be fairly good approximation for text generation.

Here, we derive a second order asymptotics for J-complexity for Markov sources of the following form γ n κ √ α log n + β for some β, γ > 0 with κ ≤ 1. This new estimate converges faster, although for small text lengths of order n ≈ 10 2 one needs to compute additional terms of the asymptotic expansion. In fact, for some Markov sources our analysis indicates that J-complexity oscillates with n. This is manifested by the appearance of a periodic function in the leading term of our asymptotics. Surprisingly, this additional term even further improves the convergence for small values of n.

Let us now summarize in full our main results Theorems 1-9. In our first main result Theorem 1 we observe that the joint string complexity J n,m can be asymptotically analyzed by considering a simpler quantity called the joint prefix complexity denoted as C n,m . To define it, let X be a set of infinite strings, and we define the prefix set I(X ) of X as the set of prefixes of X . Let X and Y be now two sets of strings and we define the joint prefix complexity as the number of common prefixes, i.e. |I(X ) ∩ I(Y)|. When Figure 1: Joint complexity of simulated texts (3rd Markov order) of English, vs French (top), Polish (bottom) languages, versus average theoretical (plain). The x-axis is the length of the text, while the y-axis shows the joint complexity.

X n is a set of n independently generated strings by Markov source 1 and Y m is a set of m independently generated strings by source 2, then C n,m is C n,m = E|I(X n ) ∩ I(Y m )|) -1 which represents the number of common prefixes between X n and Y m . In the remaining part of the paper we only deal with the joint prefix complexity C n,m . We show in Theorem 1 that |J n,m -C n,m | = O(n ǫ + m ǫ ) for some ǫ > 0, suggesting that may focus our attention on simpler to analyze quantity, namely C n,m .

First, in Theorem 2 we considered two statistically identical sources and prove that the joint string complexity grows linearly with n: For certain sources called noncommensurable there is a constant in front of n (that we determine) while for commensurable sources the factor in front of n is a fluctuating periodic function of small amplitude. We shall see these two cases permeate all our results. Then we deal in Theorem 3 with a special sources in which the underlying Markov matrices are nilpotent. After that we study general sources, however, we split our presentation and proofs into two parts. First, in Theorems 4-5 we assume that one of the source is uniform. Under this assumption we develop techniques to prove our results. Finally, in Theorem 7 -9 we study the general case.

Let us now compare our theoretical results with experimental results on real/simulated texts generated in different languages. In Figure 1 we compare the joint complexity of a simulated English text with the same length texts simulated in French and in Polish. In the simulation we use a Markov model of order 3. It is easy to see that even for texts of lengths smaller than a thousand one can discriminate between these languages. In fact, computations show that for English versus French we have κ = 0.18; and versus Polish: κ = 0.1, Furthermore, for a Markov model of order 3 we find that English text has entropy (per symbol): 0.944; French: 0.934; Polish: 0.665. The theoretical curves shown in Figure 1 are obtained through Theorem 8, however, for small values of the text length it is computed via the iterative resolution of functional equations ( 49) and (51). Figure 2 shows the continuation of our theoretical estimates up to n = 10 10 and compared with the theoretical estimate O(n κ ) as presented in Theorems 7 -8.

The joint string complexity can be used to discriminate Markov sources [START_REF] Ziv | On classification with empirically observed statistics and universal data compression[END_REF] since, as already observed, the growth of the joint string complexity is O(n κ ) with κ = 1 when sources are statistically indistinguishable and κ < 1 otherwise. For example, we can use the joint string complexity to verify authorship of an unknown manuscript by comparing it to a manuscript of known authorship and checking whether κ = 1 or not. More precisely, we propose to introduce the following discriminant function

d(X, Y ) = 1 - 1 log n log J(X, Y )
for two sequences X and Y of length n. This discriminant allows us to determine whether X and Y

= O(1/ log n) → 0 or d(X, Y ) = 1 -κ + O(log log n/ log n) > 0, respectively.
In fact, we used it with some success to classify tweets (see SNOW 2014 challenge of tweets classification and topic detection [START_REF] Burnside | One Day in Twitter: Topic Detection Via Joint Complexity[END_REF]). The paper is organized as follows. In the next section we present our main results Theorems 1-9. We prove Theorem 1 in Section 3. Then we present some preliminary results in Section 4. In particular, we derive the functional equation for the joint prefix complexity C n,m , establish some depoissonization results, and derive double Mellin transform. We first prove the nilpotent case in Section 5. The proofs of Theorems 4 -5 are presented in Section 6, and the proofs of Theorem 7 -9 are discussed in Section 7.

Main Results

In this section we define precisely our problem, introduce some important notation, and present our main results Theorem 1 -Theorem 9. The proofs are presented in the remaining parts of the paper and Appendix.

Models and notations

We begin by introducing some general notation. Let X and w be two strings over the alphabet A. We denote by |X| w the number of times w occurs in X (e.g., |abbba| bb = 2 when X = abbba and w = bb). By convention |X| ν = |X| + 1, where ν is the empty string.

Throughout we denote by X a string (text) whose complexity we plan to study. We also assume that its length |X| is equal to n. Then we define I(X) = {w : |X| w ≥ 1}, that is, I(X) contains all distinct subwords of X. Observe that the string complexity |I(X)| can be represented as

|I(X)| = w∈A * 1 |X|w≥1 ,
where 1 A is the indicator function of the event A. Notice that |I(X)| is equal to the number of nodes in the associated suffix tree of X [START_REF] Janson | On Average Sequence Complexity[END_REF][START_REF] Szpankowski | Analysis of Algorithms on Sequences[END_REF] (see also [START_REF] Jacquet | Autocorrelation on Words and Its Applications. Analysis of Suffix Trees by String-Ruler Approach[END_REF]). Now, let X and Y be two strings (not necessarily of the same length). We define the joint string complexity as the cardinality of the set J(X, Y ) = I(X) ∩ I(Y ), that is,

|J(X, Y )| = w∈A * 1 |X|w≥1 × 1 |Y |w≥1 .
In other words, J(X, Y ) represents the number of common and distinct subwords of both X and Y . For example, if X = aabaa and Y = abbba, then J(X, Y ) = {ν, a, b, ab, ba}.

In this paper we assume that both strings X and Y are generated by two independent Markov sources of order r (we will only deal here with Markov of order 1, but extension to arbitrary order is straightforward). We assume that source i, for i ∈ {1, 2} has the transition probabilities P i (a|b) from state b to state a, where a, b ∈ A r . We denote by P 1 (resp. P 2 ) the transition matrix of Markov source 1 (resp. source 2). The stationary distributions are respectively denoted by π 1 (a) and π 2 (a) for a ∈ A r . Throughout, we consider general Markov sources with transition matrices P i that may contain zero coefficients. This assumption leads to interesting embellishment of our results.

Let X n and Y m be two strings of respective lengths n and m, generated by Markov source 1 and Markov source 2, respectively. We write

J n,m = E(|J(X n , Y m )|) -1 = w∈A * \ν P (|X| w ≥ 1)P (|Y | w ≥ 1) (1)
for the joint complexity, i.e. omitting the empty string. In this paper we study J n,m for n = Θ(m). It turns out that analyzing J n,m is very challenging. It is related to the number of common nodes in two suffix trees, one built for X and the other built for Y . We know that analysis of a single suffix tree is quite challenging [START_REF] Jacquet | Autocorrelation on Words and Its Applications. Analysis of Suffix Trees by String-Ruler Approach[END_REF][START_REF] Fayolle | Analysis of the average depth in a suffix tree under a Markov model[END_REF]. Its analysis is reduced to study a simpler structure known as tries, a digital tree built from prefixes of a set of independent strings. We shall follow this approach here. Therefore, we introduce another concept. Let X be a set of infinite strings, and we define the prefix set I(X ) of X as the set of prefixes of X . Let X and Y be now two sets of strings and we define the joint prefix complexity as the number of common prefixes, i.e. |I(X ) ∩ I(Y)|. When X n is a set of n independent strings generated by source 1 and Y m is a set of m independent strings generated by source 2, then we define C n,m as

C n,m = E|I(X n ) ∩ I(Y m )|) -1
which represents the number of common prefixes between X n and Y m .

Observe that we can re-write C n,m in a different way. Define Ω i (w) for i = 1, 2 as the number of strings in X and Y, respectively, whose prefixes are equal to w provided that strings in X are generated by source 1 and strings in Y by source 2. Then, it is easy to notice that

C n,m = w∈A * \ν P (Ω 1 n (w) ≥ 1)P (Ω 2 m (w) ≥ 1) (2)
which should be compared to [START_REF] Burnside | One Day in Twitter: Topic Detection Via Joint Complexity[END_REF]. The idea is that C n,m is a good approximation of J n,m as we present in our first main result Theorem 1. We shall see in Sections 4 -7 that C n,m are easier to analyze, however, far from simple. In fact, C n,m has a nice interpretation. It corresponds to the number of common nodes in two tries built from X and Y. We know [START_REF] Jacquet | Average Profile of the Lempel-Ziv Parsing Scheme for a Markovian Source[END_REF][START_REF] Jacquet | Analytic Pattern Matching: From DNA to Twitter[END_REF][START_REF] Szpankowski | Analysis of Algorithms on Sequences[END_REF] that tries are easier to analyze than suffix trees.

Summary of Main Results

We now present our main theoretical results. In the first foundational result below we show that asymptotically we can analyze J n,m through the quantity C n,m defined above in [START_REF] Flajolet | Mellin Transforms and Asymptotics: Harmonic sums[END_REF]. The proof can be found in Section 3.

Theorem 1.

Let n and m be of the same order. Then there exists 1/2 ≤ ǫ < 1 such that

J n,m = C n,m + O(n ǫ + m ǫ ) (3)
as n → ∞.

In the rest of the paper we shall analyze C n,n . We should point out that the error term could be as large as the leading term, but for sources that are relatively close the error term will be negligible. Now we present a series of results each treating different cases of Markov sources. Moreover, our results depend on whether the underlying Markov sources are commensurable or not so we next define them.

Definition 1 (Rationally Related Matrix). We say that a matrix M = [m ab ] (a,b)∈A 2 is rationally related if ∀(a, b, c) ∈ A 3 we have m ab + m ca -m cb ∈ Z, where Z is the set of integers.

Definition 2 (Logarithmically rationally related matrix). We say that a matrix M = [m ab ] is logarithmically rationally related if there exists a non zero real number x such that the matrix x log * (M) is rationally related, where the matrix log * (M) is composed of log(m ab ) when m ab > 0 and zero otherwise. The smallest non negative value ω of the real x defined above is called the root of M.

The following matrix is an example of logarithmically rationally related matrix:

P =     1 4 1 8 1 2 1 4 1 4 1 8 1 8 1 2 1 4 1 4 1 4 1 8 1 4 1 2 1 8 1 8     .
Its root is 1/ log 2.

Definition 3 (Logarithmically commensurable pair). We say that a pair of two matrices

M = [m ab ] (a,b)∈A 2 and M ′ = [m ′
ab ] is logarithmically commensurable if there exists a pair of real numbers (x, y) such that x log * (M) + y log * (M ′ ) is not null and is logarithmically rationally related.

Notice that when M and M ′ are both rationally related, then the pair is logarithmically commensurable. Nevertheless it is possible to have logarithmically commensurable pairs with the individual matrices not logarithmically rationally related. For example when log * M ′ = 2πQ + log * M with Q an integer matrix.

We are now in the position to discuss our first main result for Markov sources that are statistically indistinguishable. Throughout we present results for m = n. Theorem 2. Consider the average joint complexity of two texts of length n generated by the same general stationary Markov source, that is, P := P 1 = P 2 . (i) [Noncommensurable Case.] Assume that P is not logarithmically rationally related. Then

J n,n = 2n log 2 h + o(n) ( 4
)
where h is the entropy rate of the source defined as h = a,b∈A π(a)P (a|b).

(ii) [Commensurable Case.] Assume that P is logarithmically rationally related. Then there is ǫ < 1 such that:

J n,n = 2n log 2 h (1 + Q 0 (log n)) + O(n ǫ ) ( 5
)
where Q 0 (.) is a periodic function of small amplitude. (In Section 4.3 we compute explicitly Q.)

Now we consider sources that are not the same and have respective transition matrices P 1 and P 2 . The transition matrices are on A r × A r , however, hereafter we deal mostly with r = 1. If (a, b) ∈ A × A, we denote by P i (a|b) the (a, b)-th coefficient of matrix P i . For a tuple of complex numbers (s 1 , s 2 ) we write P(s 1 , s 2 ) for the following matrix P(s 1 , s 2 ) = [(P 1 (a|b)) -s1 (P 2 (a|b)) -s2 ] a,b∈A .

In fact, we can write it as the Schur product, denoted as ⋆, of two matrices P 1 (s 1 ) = (P 1 (a|b)) -s1 and P 2 (s 2 ) = (P 2 (a|b)) -s2 , that is, P(s 1 , s 2 ) = P 1 (s 1 ) ⋆ P 2 (s 2 ).

To present succinctly our general results we need some more notation. Let x|y be the scalar product of vector x and vector y. By λ(s 1 , s 2 ) we denote the main eigenvalue of matrix P(s 1 , s 2 ), and u(s 1 , s 2 ) its corresponding right eigenvector (i.e, λ(s 1 , s 2 )u(s 1 , s 2 ) = P(s 1 , s 2 )u(s 1 , s 2 )), and ζ(s 1 , s 2 ) its left eigenvector (i.e., λ(s 1 , s 2 )ζ(s 1 , s 2 ) = ζ(s 1 , s 2 )P(s 1 , s 2 )). We assume that ζ(s 1 , s 2 )|u(s 1 , s 2 ) = 1. Furthermore, the vector π(s 1 , s 2 ) is defined as the vector (π 1 (a) -s1 π 2 (a) -s2 ) a∈A where (π i (a)) a∈A is the left eigenvector of matrix P i for i ∈ {1, 2}. In other words (π i (a)) a∈A is the stationary distribution of the Markov source i.

We start our presentation with the simplest case, namely the case when the matrix P(0, 0) is nilpotent [START_REF] Horn | Matrix Analysis[END_REF], that is, for some K the matrix P K (0, 0) is the null matrix. Notice that for nilpotent matrices ∀(s 1 , s 2 ): P K (s 1 , s 2 ) = 0. Theorem 3. If P(s 1 , s 2 ) is nilpotent, then there exists γ 0 such that

lim n→∞ J n,n = γ 0 := 1 C (I -P(0, 0)) -1 |1 ( 6
)
where 1 is the unit vector, 1 C the vector on A with 1 C (a) = 1 when a is common to both sources, and

1 C (a) = 0 otherwise.
This result is not surprising and rather trivial since the common factors can only occur in a finite window at the beginning of the strings. It turns out that γ 0 = 1168 for 3rd order Markov model of English versus Polish languages used in our experiments.

From now on, we assume that P(s 1 , s 2 ) is not nilpotent. We need to pay much closer attention to the structure of the set of roots of the characteristic equation λ(s 1 , s 2 ) = 1 that will play a major role in the analysis. We discuss in depth properties of these roots in Section 4.5.

Here we introduce only a few important definitions. Definition 4. The kernel K is the set of complex tuples (s 1 , s 2 ) such that P(s 1 , s 2 ) has its largest eigenvalue equal to 1. The real kernel K = K ∩ R 2 , i.e. the set of real tuples (s 1 , s 2 ) such that the main eigenvalue λ(s 1 , s 2 ) = 1.

The following lemma is easy to prove. Lemma 1. The real kernel forms a concave curve in R 2 .

Furthermore, we introduce two important notations:

κ = min (s1,s2)∈K {-s 1 -s 2 } (7) (c 1 , c 2 ) = arg min (s1,s2)∈K {-s 1 -s 2 }. (8)
Easy algebra shows that κ ≤ 1. Furthermore, in the Appendix we prove the following property.

Lemma 2. Let c 1 and c 2 minimize -s 1 -s 2 where real tuple

(s 1 , s 2 ) ∈ K. Assume ∀(a, b) ∈ A 2 : P 1 (a|b) > 0 then c 1 ≤ 0 and c 2 ≥ -1.
Finally, we introduce a new concept ∂K, the border of the kernel K, defined as follows.

Definition 5. We denote ∂K the subset of K made of the pairs (s 1 , s 2 ) such ℜ(s 1 , s 2 ) = (c 1 , c 2 ).

The case when both matrices P 1 and P 2 have some zero coefficients is the most intricate part. Therefore, to present our strongest results, we start with a special case when one of the source is uniform. Later we generalize it.

We first consider a special case when source 1 is uniform memoryless, i.e. P 1 = 1 |A| 1 ⊗ 1 and the other matrix P 2 is not nilpotent and general (that is, it may have some zero coefficients). In this case we always have c 1 < 0 and c 2 < 0. This case we have the following theorem.

Theorem 4. Let P 1 =1 |A| 1 ⊗ 1 and P 2 = P 1 is a general transition matrix. Thus both c 1 and c 2 are between -1 and 0. (i) [Mono periodic case.] If P 2 is not logarithmically rationally related, then there exists a periodic function Q 1 (x) of small amplitude such that

C n,n = γ 2 n κ √ α 2 log n + β 2 (1 + Q 1 (log n) + o(1)). (9)
(ii) [Double periodic case.] If P 2 is logarithmically rationally related, then there exists a double periodic function 1 Q 2 (.) of small amplitude such that

C n,n = γ 2 n κ √ α 2 log n + β 2 (1 + Q 2 (log n) + o(1)). ( 10
)
The constants γ 2 , α 2 and β 2 in the Theorem 4 are explicitly computable as presented next. To simplify our notation for all (a, b) ∈ A 2 we shall write P 2 (a|b) = P (a|b) and P 2 = P. Therefore

P(s 1 , s 2 ) = |A| s1 P(s) (11)
with P(s) = P(0, s). We also write π(a) = π 2 (a) and π(s) = [π(a) -s ] a∈A , thus

π(s 1 , s 2 ) = |A| s1 π(s 2 ) . (12)
Let λ(s 1 , s 2 ) be again the main (largest) eigenvalue of P(s 1 , s 2 ). We have

λ(s 1 , s 2 ) = |A| s1 λ(s 2 ) (13)
where λ(s) is the main eigenvalue of matrix P(s). We also define u(s) as the right eigenvector of P(s) and ζ(s) as the left eigenvector provided ζ(s)|u(s) = 1. It is easy to see that

λ(s) = ζ(s)|P(s)u(s) .
Now we can express c 1 and c 2 defined in (8) in another way. Notice that if λ(s 1 , s 2 ) = 1, then in this case

s 1 = -log |A| λ(s 2 ). Define L(s) = log |A| λ(s). Then c 2 is the value that minimizes L(s) -s, that is, λ ′ (c 2 ) λ(c 2 ) = log |A|. (14)
Also

c 1 = -L(c 2 ) and κ = -c 1 -c 2 = min s {L(s) -s}. We have κ ≤ 1 since L(0) = 1.
We now can present explicit expression for the constants in Theorem 4.

Theorem 5. We consider the case

P 1 = 1 |A| 1 ⊗ 1 and P 2 = P 1 has all non negative coefficients. Let f (s) = π(s)|u(s) and g(s) = ζ(s)|1 . Furthermore, with Ψ(s) being the Euler psi function, define α 2 = L ′′ (c 2 ) where L(s) = log |A| λ(s), and
β 2 (s 1 , s 2 ) = -α 2 Ψ(s 1 ) + 1 1 + s 1 + log |A| + Ψ ′ (s 1 ) - 1 (s 1 + 1) 2 + Ψ ′ (s 2 ) - 1 (s 2 + 1) 2 + f ′′ (s 2 ) f (s 2 ) - f ′ (s 2 ) f (s 2 ) 2 + g ′′ (s 2 ) g(s 2 ) - g ′ (s 2 ) g(s 2 ) 2
as well as

γ(s 1 , s 2 ) = f (s 1 )g(s 2 )(s 1 + 1)Γ(s 1 )(s 2 + 1)Γ(s 2 ) λ(s 2 ) log |A| √ 2π .
We have c 1 = -log |A| λ(c 2 ), and then

C n,n = n κ γ(c 1 , c 2 ) α 2 log n + β 2 (c 1 , c 2 ) +n κ Q(log n) + o( n κ √ log n ). ( 15
)
The function Q(x) can be expressed as

Q(x) = (s1,s2)∈∂K * e ixℑ(s1+s2) γ(s 1 , s 2 ) α 2 x + β 2 (s 1 , s 2 )
.

If the matrix P 2 is logarithmically rationally related, then ∂K is a lattice. Let ω the root of P 2 then

∂K = c 1 + 2ikπ log |A| , c 2 + 2iπℓω , (k, ℓ) ∈ Z 2 ,
and √ xQ(x) is asymptotically double periodic. Otherwise (i.e., irrational case),

∂K = c 1 + 2ikπ log 2 , c 2 , k ∈ Z and √ xQ(x)
is asymptotically single periodic. The amplitude of Q is of order 10 -6 .

Now we consider the case when the matrices P 1 and P 2 are general and P 1 = P 2 . If they contain some zero coefficients, then we may have P(-1, 0) = P 1 and/or P(0, -1) = P 2 . In this (very unlikely) case we may have P(-1, 0) = P(0, -1) or more generally they are conjugate. 2 For example for matrices:

P 1 =     0 0 5 8 1 2 0 1 8 1 8 1 4 1 2 1 4 1 4 1 8 1 2 5 8 0 1 8     P 2 =     1 2 5 8 0 1 2 1 2 1 8 1 8 1 4 0 1 4 1 4 1 8 0 0 5 8 1 8     we have P(-1, 0) = P(0, -1) =     0 0 0 1 2 0 1 8 1 8 1 4 0 1 4 1 4 1 8 0 0 0 1 8    
If P(-1, 0) = P(0, -1), then there is no unique solution (c 1 , c 2 ) of the characteristic equation. As a consequence, we have the following theorem: Theorem 6. When P(-1, 0) and P(0, -1) are conjugate matrices we have

C n,n = γ 0 (-κ)n κ (1 + o(1)) (16)
where κ < 1 is such that (-κ, 0) ∈ K and γ 0 (-κ) are explicitly computable. When both matrices are logarithmically rationally related, then

C n,n = γ(-κ)n κ 1 + Q 0 (log n) + O(n -ǫ (17)
where Q 0 (.) is small periodic function and ǫ > 0.

In general, however, P(-1, 0) and P(0, -1) are not conjugate, and therefore, there is a unique (c 1 , c 2 ) of the characteristic equation λ(c 1 , c 2 ) = 1. As in the special case discussed above, c 1 > -1 and c 2 > -1, however, our results are quantitatively different when c 1 > 0 or c 2 > 0. We consider it first in Theorem 7 below. Since both cases cannot occur simultaneously, we dwell only on the case c 2 > 0; the case c 1 > 0 can be handled in a similar manner.

Theorem 7. Assume P(0, 0) is not nilpotent and c 2 > 0. (i) [Noncommensurable Case.] We assume that P(-1, 0) is not logarithmically related. Let -1 < c 0 < 0 such that (c 0 , 0) ∈ K. There exist γ 1 such that

C n,n = γ 1 n -c0 (1 + o(1)) (18)
(ii) [Commensurable Case.] Let now P(-1, 0) be logarithmically rationally related. There exists a periodic function Q 1 (.) of small amplitude such that

C n,n = γ 1 n -c0 (1 + Q 1 (log n) + O(n -ǫ ) (19)
Finally, we handle the most intricate case when both c 1 and c 2 are between -1 and 0. Recall that when both matrix P 1 and P 2 have all positive coefficients, then P(-1, 0) = P 1 and P(0, -1) = P 2 .

Theorem 8. Assume that both c 1 and c 2 are between -1 and 0 and P(0, 0) is not nilpotent. (i) [Non periodic Case.] If P(-1, 0) and P(0, -1) are not logarithmically commensurable matrices, then there exist α 2 , β 2 and γ 2 such that

C n,n = γ 2 n κ √ α 2 log n + β 2 (1 + o(1)). (20)
(ii) [Mono periodic case.] If only one of the matrices P(-1, 0) and P(0, -1) is logarithmically rationally related, then there exists a periodic function Q 2 (x) of small amplitude such that

C n,n = γ 2 n κ √ α 2 log n + β 2 (1 + Q 1 (log n) + o(1)). (21)
(iii) [Double periodic case.] If both matrices P 1 and P 2 are logarithmically rationally related, then function Q 2 (.) is double periodic with small amplitude such that

C n,n = γ 2 n κ √ α 2 log n + β 2 (1 + Q 2 (log n) + o(1)). (22)
In the three cases the constants γ 2 , α 2 and β 2 are explicitly computable.

Remark

In the double periodic case when the ∂K forms a lattice with commensurable vectors, the double periodic function reduces to a simple periodic function.

At last, we provide explicit expressions for some of constants in previously stated results, in particular in the most interesting Theorem 8. We denote

H(s 1 , s 2 ) = 1 -λ(s 1 , s 2 ). Let H 1 (s 1 , s 2 ) = ∂ ∂s1 λ(s 1 , s 2 ), f (s 1 , s 2 ) = π(s 1 , s 2 )|u(s 1 , s 2 ) and g(s 1 , s 2 ) = ζ(s 1 , s 2 )|1 .
Theorem 9. Let c 1 and c 2 be between -1 and 0. In the general case we have

C n,n = n κ (s1,s2)∈∂K γ(s 1 , s 2 )n -iℑ(s1+s2) α 2 log n + β(s 1 , s 2 ) 1 + O( 1 log n ) . (23)
With and

H 1 , α 2 , β 2 (s 1 , s 2 ) and γ(s 1 , s 2 ) such H 1 = ∂ ∂s 1 H(c 1 , c 2 ) α 2 = ∆H -2 ∂ 2 ∂s1∂s2 H H 1 | (s1,s2)=(c1,c2) β 2 (s 1 , s 2 ) = - α 2 2 Ψ(s 1 ) + Ψ(s 2 ) + ∂ ∂s1 f + ∂ ∂s2 f f + ∂ ∂s1 g + ∂ ∂s2 g g +Ψ ′ (s 1 ) + Ψ ′ (s 2 ) + ∆f -2 ∂ 2 ∂s1∂s2 f f + ∆g -2 ∂ 2 ∂s1∂s2 g g - ∂ ∂s1 f -∂ ∂s2 f f 2 - ∂ ∂s1 g -∂ ∂s2 g g 2 + α 2 2 2 - ∂ 3 ∂s 3 1 H -∂ 3 ∂s 2 1 ∂s2 H -∂ 3 ∂s1∂s 2 2 H + ∂ 3 ∂s 3 2 H 2H 1 +   ∂ 2 ∂s 2 1 H -∂ 2 ∂s 2 2 H 2H 1   2
γ(s 1 , s 2 ) = f (s 1 )g(s 2 )(s 1 + 1)Γ(s 1 )(s 2 + 1)Γ(s 2 ) λ(s 2 ) log |A| √ 2π .
The expression for α 2 seems to be asymmetric in (s 1 , s 2 ). In fact, it is not since the maximum of

s 1 + s 2 for (s 1 , s 2 ) ∈ K attained on (c 1 , c 2 ) necessarily implies that ∂ ∂s1 H(c 1 , c 2 ) = ∂ ∂s2 H(c 1 , c 2 ). Formally the constant α 2 is equal to ∆λ 1 (c 1 , c 2 ) 1|∇λ 1 (c 1 , c 2 ) where ∇ is the gradient operator, ∆ the Laplacian operator ∂ 2 ∂s 2 1 + ∂ 2 ∂s 2 2 .
Finally, we illustrate our results on two examples.

Example. In Figures 3 and4 we plot the joint complexity for several pairs of strings X and Y . String X is generated by a Markov source with the transition matrix P, and string Y is generated by a uniform memoryless source. We consider two Markov sources for X with the following transition matrix:

P = 0 0.5 1 0.5 P = 0.2 0.8 0.8 0.2 . ( 24
)
For the first P in Figure 3 we have c 2 > 0 (see Theorem 7) while for the second P in Figure 4 we have c 2 < 0 (cf. Theorem 4(i)).

Figure 4: Joint semi-complexity: three simulated trajectories (black) versus asymptotic average (dashed red)for the case c 2 < 0.

Proof of Theorem 1

We recall that X and Y are two independent strings of length n and m, generated by two Markov sources characterized by transition matrices P 1 and P 2 , respectively. In the previous section we write |X| w and |Y | w for the number of w ∈ A occurrences in X and Y . But it will be convenient to use another notation for these quantities, namely

O 1 n (w) := |X| w , O 2 m (w) := |Y | w .
We shall use this notation interchangeably. Finally, we write A + = A * -{ν}, that is, for the set of all nonempty words. As observed in (1) we have

J n,m = w∈A + P (O 1 n (w) ≥ 1)P (O 2 m (w) ≥ 1). ( 25
)
In [START_REF] Régnier | On pattern frequency occurrences in a Markovian sequence[END_REF][START_REF] Jacquet | Analytic Pattern Matching: From DNA to Twitter[END_REF] the generating function of P (O n (w) ≥ 1) for a Markov source is derived. It involves the autocorrelation polynomial of w, as discussed below. However, to make our analysis tractable we notice that O i n (w) ≥ 1, i = 1, 2, is equivalent to w being a prefix of at least one of the n suffixes of X. But this is not sufficient to push forward our analysis. We need a second much deeper observation that replaces dependent suffixes with independent strings to shift analysis from suffix trees to tries, as already observed in [START_REF] Jacquet | Autocorrelation on Words and Its Applications. Analysis of Suffix Trees by String-Ruler Approach[END_REF] and briefly discussed in Section 2. In order to accomplish it, we consider two sets of infinite length strings of cardinality n and m, respectively, generated independently by Markov sources P 1 and P 2 . As in Section 2 we denote by Ω i n (w) the number of strings for which w is a prefix when there are n strings generated by source i, for i ∈ {1, 2}. The average joint prefix complexity satisfies (2) that we repeat below

C n,m = w∈A + P (Ω 1 n (w) ≥ 1)P (Ω 2 m (w) ≥ 1). (26)
Before we prove our first main result Theorem 1 we need some preliminary work. First, observe that it is relatively easy to compute the probability P (Ω i n (w) ≥ 1). Indeed, P (Ω i n (w) ≥ 1) = 1 -(1 -P i (w)) n . Notice that the quantity 1 -(1 -P (w)) n is the probability that |X n | w > 0 where X n is a set of n independently generated strings. To prove Theorem 1 we must show that for Markov sources when n → ∞ P (O i n (w) ≥ 1) ∼ P (Ω i n (w) ≥ 1) which we do in the next key lemma.

We denote by B k the set of words of length k such that a word w ∈ B k does not overlap with itself over more than k/2 characters (see [START_REF] Jacquet | Analytic Pattern Matching: From DNA to Twitter[END_REF][START_REF] Jacquet | Autocorrelation on Words and Its Applications. Analysis of Suffix Trees by String-Ruler Approach[END_REF][START_REF] Fayolle | Analysis of the average depth in a suffix tree under a Markov model[END_REF] for more precise definition). It is proved in [START_REF] Fayolle | Analysis of the average depth in a suffix tree under a Markov model[END_REF] that

w∈A k -B k P (w) = O(δ k 1 )
where A k is the set of all words of length k and δ 1 < 1 is the largest element of the Markovian transition matrix P. In order to allow some transition probabilities to be equal to 0 we define

p = exp lim sup k,w∈A k log P (w) k q = exp lim inf k,w∈A k ,P (w) =0 log P (w) k .
These quantities exist and are smaller than 1 since A is a finite alphabet [START_REF] Pittel | Asymptotic Growth of a Class of Random Trees[END_REF][START_REF] Szpankowski | Analysis of Algorithms on Sequences[END_REF]. In fact, they are related to Renyi's entropy of order ±∞, respectively [START_REF] Szpankowski | Analysis of Algorithms on Sequences[END_REF]. We write δ = √ p < 1. Let X n be a string of length n generated by a Markov source. For w ∈ A * , define

d n (w) = P (O n (w) > 0) -(1 -(1 -P (w)) n ). ( 27
)
We prove the following lemma Lemma 3. Let w ∈ A k be of length k. There exists ρ > 1 and a sequence R n (w) = O(P (w)ρ -n ) such that for all 1 > ǫ > 0 we have:

(i) for w ∈ B k : d n (w) = O((nP (w)) ǫ kδ k ) + R n (w); (ii) for w ∈ A k -B k : d n (w) = O((nP (w)) ǫ δ k ) + R n (w).
Proof. Let N 0 (z) = n≥0 P (O n (w) = 0)z n . We know from [START_REF] Jacquet | Analytic Pattern Matching: From DNA to Twitter[END_REF] that

N 0 (z) = S w (z) D w (z)
where S w (z) is the autocorrelation polynomial of word w and D w (z) is defined as follows

D w (z) = S w (z)(1 -z) + z k P (w) (1 + F w1,w k (z)(1 -z)) , (28)
where k = |w| is the length of word w with first symbol w 1 and the last symbol w k . Here F a,b (z) for (a, b) ∈ A 2 is a generating function that depends on the Markov sources, as describe below. We also write F w (z) when w 1 = a and w k = b.

Let P be the transition matrix of the Markov source. Let π be its stationary vector and for a ∈ A let π a be its coefficient at symbol a. The vector 1 is the vector with all coefficients equal to 1 and I is the identity matrix. Assuming that the symbol a (resp. b) is the first (resp. last) character of w, we have [START_REF] Régnier | On pattern frequency occurrences in a Markovian sequence[END_REF]

F w (z) := F a,b(z) = 1 π a (P -π ⊗ 1) (I -z(P + π ⊗ 1)) -1 a,b (29)
where ⊗ is the tensor product, and [A] a,b denotes the (a, b)th coefficient of matrix A. An alternative way to express F w (z) is

F w (z) = 1 π a e a (P -π ⊗ 1) (I -z(P + π ⊗ 1)) -1 e b (30)
where e c for c ∈ A is the vector with a 1 at the position corresponding to symbol c and all other coefficients are 0. By the spectral representation of matrix P we have [START_REF] Horn | Matrix Analysis[END_REF]

P = π ⊗ 1 + i>1 λ i u i ⊗ ζ i
where λ i for i ≥ 1 is the ith eigenvalue (in decreasing order) of matrix P (with λ 1 = 1), and u i (resp. ζ i ) are their corresponding right (resp. left) eigenvectors. Thus

(P -π ⊗ 1) (I -z(P + π ⊗ 1)) -1 = i>1 λ i 1 -λ i z u i ⊗ ζ i (31)
and therefore the function F w (z) is defined for all z such that |z| < 1 |λ2| and is uniformly O( 1 1-|λ2z| ). We now follow the approach from [START_REF] Fayolle | Analysis of the average depth in a suffix tree under a Markov model[END_REF] that extends to Markovian sources the analysis presented in [START_REF] Jacquet | Autocorrelation on Words and Its Applications. Analysis of Suffix Trees by String-Ruler Approach[END_REF] for memoryless sources (see also [START_REF] Jacquet | Analytic Pattern Matching: From DNA to Twitter[END_REF]). Let

∆ w (z) = n≥0 d n (w)z n
be the generating function of d n (w) defined in (27). After some algebra we arrive at

∆ w (z) = P (w)z 1 -z 1 + (1 -z)F w (z) D w (z) - 1 1 -z + P (w)z . ( 32
)
We have

d n (w) = 1 2iπ ∆ w (z) dz z n+1 ,
integrated on any loop encircling the origin in the definition domain of d w (z). Extending the result from [START_REF] Jacquet | Autocorrelation on Words and Its Applications. Analysis of Suffix Trees by String-Ruler Approach[END_REF], the authors of [START_REF] Fayolle | Analysis of the average depth in a suffix tree under a Markov model[END_REF] show that there exists ρ > 1 such that the function D w (z) defined in (28) has a single root in the disk of radius ρ. Let A w be this root. We have via the residue formula

d n (w) = Res(∆ w (z), A w )A -n w -(1 -P (w)) n + d n (w, ρ) (33)
where Res(f (z), A) denotes the residue of function f (z) on complex number A. Thus

d n (w, ρ) = 1 2iπ |z|=ρ ∆ w (z) dz z n+1 . ( 34
)
We have

Res(∆ w (z), A w ) = P (w) (1 + (1 -A w )F w (A w )) (1 -A w )C w ( 35
)
where

C w = D ′ w (A w ). But since D w (A w ) = 0 we can write Res(∆ w (z), A w ) = - A -k w S w (A w ) C w . ( 36
)
We can take the asymptotic expansion of A w and C w as it is described in [START_REF] Jacquet | Analytic Pattern Matching: From DNA to Twitter[END_REF], in Lemma 8.1.8 and Theorem 8.2.2. Anyhow the expansions were done in the memoryless case. But an extension to Markov sources simply consists in replacing S w (1) into S w (1) + P (w)F w (1), so we find

           A w = 1 + P (w) Sw(1) +P 2 (w) k-Fw (1) S 2 w (1) - S ′ w (1) S 3 w (1) + O(P (w) 3 ), C w = -S w (1) + P (w) k -F w (1) -2 S ′ w (1) Sw(1)
+O(P (w) 2 ).

(37) These expansions also appear in [START_REF] Fayolle | Analysis of the average depth in a suffix tree under a Markov model[END_REF].

From now the proof takes the same path as the proof of Theorem 8.2.2 in [START_REF] Jacquet | Analytic Pattern Matching: From DNA to Twitter[END_REF]. We define the function

d w (x) = A -k w S w (A w ) C w A -x w -(1 -P (w)) x . ( 38
)
More precisely, we define the function dw (x) = d w (x) -d w (0)e -x . Its Mellin transform [START_REF] Szpankowski | Analysis of Algorithms on Sequences[END_REF] is

d * w (s)Γ(s) = ∞ 0 dw (x)x s-1 dx defined for all ℜ(s) ∈ (-1, 0) with d * w (s) = A -k w S w (A w C w ((log A w ) -s -1) + 1 -(-log(1 -P (w)))) -s (39)
where Γ(s) is the Euler gamma function. When w ∈ B k with the expansion of A w and since S w (1) = 1 + O(δ k ) and S ′ w (1) = O(kδ k ), we find that similarly as in [START_REF] Jacquet | Analytic Pattern Matching: From DNA to Twitter[END_REF]

d * w (s) = O(|s|kδ k )P (w) 1-s (40)
and therefore by the reverse Mellin transform, for all 1 > ǫ > 0:

dw (n) = 1 2iπ -ǫ+i∞ -ǫ-i∞ d * w (s)Γ(s)s -n ds = O(n ǫ P (w) ǫ kδ k ). ( 41
) When w ∈ A k -B k it is not true that S w (1) = 1 + O(δ k
), thus it is shown in [START_REF] Fayolle | Analysis of the average depth in a suffix tree under a Markov model[END_REF] that there exists α > 0 such that for all w ∈ A * : S w (z) > α for all z such that |z| ≤ ρ. Therefore we get dw (n) = O(n ǫ P (w) ǫ ).

We set

R n (w) = d w (0)e -n + d n (w, ρ). ( 42
)
We first investigate the quantity d w (0). We prove that d w (0) = O(P (w)). Noticing that

S w (A w ) = S w (1) + P (w) S w (1) S ′ w (1) + O(P (w) 2 )
we have the expansion

- A -k w S w (A w ) C w = 1 - P (w) S w (1) F w (1) + S ′ w (1) S w (1) + O(P (w) 2 ). ( 43
)
Thus

d w (0) = - P (w) S w (1) F w (1) + S ′ w (1) S w (1) + O(P (w)) 2 ). ( 44
)
Thus d w (0) = O(P (w)). Now we need to consider d n (w, ρ). Since ∆ n (z) is clearly O(P (w)) and the integral ∆(z) dz z n+1 is over the circle of radius, the result is O(P (w)ρ -n ). Now we are ready to prove Theorem 1.

Proof. Again staring with

J n,m = w∈A * P (O 1 n (w) > 0)P (O 2 m (w) > 0) (45)
we note that

P (O 1 n (w) > 0)) = 1 -(1 -P 1 (w)) n + d 1 n (w), P (O 2 m (w) > 0) = 1 -(1 -P 2 (w)) m + d 2 m (w).
Thus

J n,m = C n,m + w∈A d 1 n (w)P (O 2 m (w) > 0) + w∈A (1 -(1 -P 1 (w)) n )d 2 m (w). ( 46
)
We will give the proof for the first sum, since the proof for the second proof being somewhat similar. When w ∈ B k , we have for all ǫ > 0

d 1 n (w) = O(n ǫ P 1 (w) ǫ kδ k 1 ) + R 1 n (w) (47)
and the R 1 n (w) terms are all O(P 1 (w)ρ -n ). We look at the sum

k w∈B k n ǫ P (w) ǫ kδ k 1 .
It is smaller than

k w∈A k n ǫ P 1 (w)k(q ǫ-1 δ 1 ) k
which is equal to n ǫ k k(q ǫ-1 δ 1 ) k . By choosing a value ǫ 1 of ǫ enough close to 1 so that q ǫ1-1 δ 1 < 1 we have the n ǫ1 order. Notice that with δ 1 = √ p we must conclude that 1/2 < ǫ 1 < 1. When w ∈ A k -B k the δ k 1 factor disappears in the right-hand side expression for d 1 n (w). But in this case

w∈A k -B k n ǫ P (w)(q ǫ-1 ) k = O(n ǫ δ k 1 (q ǫ-1 ) k ),
and we conclude similarly. It remains the sum w∈A * R 1 n (w)P 2 (O m (w) > 0). For this we remark that P 2 (O m (w) > 0) = O(mP 2 (w)). Therefore the sum is of order ρ -n m w∈A * P 1 (w)P 2 (w). It turns out that

w∈A k P 1 (w)P 2 (w) = O(λ k 12 )
where λ 12 is the main eigenvalue of the Shur product matrix P 1 ⋆ P 2 (also known denoted P(-1, -1). Since λ 12 < 1 the sum converges and is O(ρ -n m).

Some Preliminary Results

In this section we first derive the recurrence on C n,m which will lead to the functional equation on the double Poisson transform C(z 1 , z 2 ) of C n,m , that in turn allows us to find the double Mellin transform

C * (s 1 , s 2 ) of C(z 1 , z 2 )
. Finally applying a double depoissonization we first recover the original C n,n and ultimately the joint string complexity J n,n through Theorem 1.

Functional Equations

Let a ∈ A and define

C a,m,n = w∈aA * P (Ω 1 n (w) ≥ 1)P (Ω 2 m (w) ≥ 1)
where w ∈ aA * means that w starts with an a ∈ A. We recall that Ω i n (w) represents the number of strings of length n that start with prefix w.

Notice that C a,m,n = 0 when n = 0 or m = 0. Using Markov nature of the string generation, the quantity C a,n,m for n, m ≥ 1 satisfies the following recurrence for all a, b ∈ A

C b,n,m = 1 + a∈A na,ma n n a m m a ×(P 1 (a|b)) na (1 -P 1 (a|b)) n-na ×(P 2 (a|b)) ma (1 -P 2 (a|b)) m-ma C a,na,ma ,
where n a (resp. m a ) denotes the number of strings among n (resp. m) independent strings from source 1 (resp. 2) that have symbol a followed by symbol b. Indeed, partitioning bA * as {b} + a∈A aA * we obtain the recurrence noting that strings are independent and n na (P 1 (a|b)) na (1 -P 1 (a|b)) n-na is the probability of n a out of n starting with ba. starts In a similar fashion, the unconditional average C n,m satisfies for n, m ≥ 2

C n,m = 1 + a∈A na,ma n n a m m a π na 1 (a)(1 -π 1 (a)) n-na ×π ma 2 (a)(1 -π 2 (a)) m-ma C a,n,m .
To solve it we introduce the double Poisson transform of C a,n,m as

C a (z 1 , z 2 ) = n,m≥0 C a,n,m z n 1 z m 2 n!m! e -z1-z2 (48)
that translates the above recurrence into the following functional equation:

C b (z 1 , z 2 ) = (1 -e -z1 )(1 -e -z2 ) + a∈A C a (P 1 (a|b)z 1 , P 2 (a|b)z 2 ) . (49)
To simplify it, we define the double Poisson transform

C(z 1 , z 2 ) = n,m≥0 C n,m z n 1 z m 2 n!m! e -z1-z2 (50)
finding that

C(z 1 , z 2 ) = (1 -e -z1 )(1 -e -z2 ) + a∈A C a (π 1 (a)z 1 , π 2 (a)z 2 ). ( 51
)
Our goal now is to find asymptotic expansion of C(z 1 , z 2 ) as z 1 , z 2 → ∞ in a cone around the real axis. This will be accomplished in the next subsection using double Mellin transform. Granted it, we shall appeal to a double depoissonization result to recover asymptotically C n,m and ultimately J n,m .

Double DePoissonization

Once we know C(z 1 , z 2 ) for z 1 = n, z 2 = m → ∞ we then need to recover C n,m . Double depoissonization lemma discussed and proved in [START_REF] Jacquet | Analytic Pattern Matching: From DNA to Twitter[END_REF] (see Lemma 10.3.4) allows us to do exactly that but in order to apply it we need to postulate some conditions on the underlying Poisson transforms. We briefly review double depoissonization next.

For a double sequence a n,m define

f (z 1 , z 2 ) = ∞ m,n=0 a n,m z n 1 n! e -z1 z m 2 m! e -z2 , f n (z 2 ) = ∞ m=0 a n,m z m 2 m! e -z2 .
We notice that f (z 1 , z 2 ) is the Poisson transform of the sequence f n (z 2 ) with respect to the variable z 1 . Now we postulate certain conditions on f (z 1 , z 2 ) and f n (z 2 ) that will allow us to extract asymptotics of a n,m from f (z 1 , z 2 ).

First depoissonization. For z 2 ∈ S θ := {z 2 : arg(z 2 ) < θ} we postulate that there exist constants β, α, B and D such that

z 1 ∈ S θ : |f (z 1 , z 2 )| < B(|z 1 | β + |z 2 | β ) z 1 / ∈ S θ : |f (z 1 , z 2 )e z1 | < D|z 2 | β e α|z1| .
Therefore, from the one-dimensional analytic depoissonization of [START_REF] Jacquet | Analytical DePoissonization and Its Applications[END_REF][START_REF] Szpankowski | Analysis of Algorithms on Sequences[END_REF] for z 2 ∈ S θ , we have for all integers k > 0

f n (z 2 ) = f (n, z 2 ) + O n β-1 + |z 2 | β n + O(|z 2 | β n β-k ).
Similarly, when z 2 / ∈ S θ we postulate

z 1 ∈ S θ : |f (z 1 , z 2 )e z2 | < D|z 1 | β e α|z2| z 1 / ∈ S θ : |f (z 1 , z 2 )e z1+z2 | < De α|z1|+α|z2| .
Thus for all integer k and ∀z 2 / ∈ S t h

f n (z 2 )e z2 = f (n, z 2 )e z2 + O(n β-1 e α|z2| ) + O(n β-k e α|z2| ).
Second depoissonization. The above two conditions on f n (z 2 ), respectively for z 2 ∈ S θ and z 2 / ∈ S θ , allow us to depoissonize f n (z 2 ). For all k > β:

• for z 2 ∈ S θ : f n (z 2 ) = O(n β + |z 2 | β ); • for z 2 / ∈ S θ : f n (z 2 )e z2 = O(n β e α|z2| ).
These estimates are uniform. Therefore,

a n,m = f n (m) + O n β m + m β n + O n β m β-k . Since f n (m) = f (n, m) + O n β-1 + m β n
and setting k > β + 1, we find the desired estimate. Now we are ready for formulate our depoissonization lemma. In [START_REF] Jacquet | Analytic Pattern Matching: From DNA to Twitter[END_REF] it is shown that C(z 1 , z 2 ) satisfies depoissonization conditions for memoryless sources. In Appendix we prove the following lemma.

Lemma 4 (DePoissonization). We have

C n,m = C(n, m) + O n m + m n
for large n and m.

To find C(n, m) from C(z 1 , z 2 ) we follow the Mellin transform approach, however for general sources we need to consider a double Mellin transform. We start in the next subsection with a simple case when P 1 = P 2 .

Mellin Transform for P

1 = P 2 : Proof of Theorem 2
We first present a general result for identical Markov sources, that is, P 1 = P 2 = P proving Theorem 2. In this case (49) can be rewritten with c a (z) = C a (z, z):

c b (z) = (1 -e -z ) 2 + a∈A c a (P (a|b)z) . ( 52
)
This equation is directly solvable by the Mellin transform defined as

c * a (s) = ∞ 0 c a (x)x s-1 dx
that exists in the fundamental strip -2 < ℜ(s) < -1. Properties of Mellin transform can be found in [START_REF] Flajolet | Analytic Combinatorics[END_REF][START_REF] Szpankowski | Analysis of Algorithms on Sequences[END_REF]. It follows that for all b ∈ A [23]

c * b (s) = (2 -s -2)Γ(s) + a∈A (P (a|b)) -s c * a (s). ( 53
)
It is better to write it in the matrix form. Let c(s) = [c * a (s)] a∈A be the vector of Mellin transforms c * a (s) and and P(s) = [P -s (a|b)] a,b∈A . Then (53) becomes

c(s) = (2 -s -2)1(I -P(s)) -1
where, again, 1 is the vector of dimension |A| made of all 1's, and I is the identity matrix. We now can derive the Mellin transform c * (s) of c(z) := C(z, z) representing the unconditional joint string complexity. From above and (51) we arrive at

c * (s) = (2 -s -2)Γ(s) + a∈A (π(a)) -s c * a (s) .
which in matrix form can be rewritten as

c * (s) = (2 -s -2)Γ(s) 1 + 1(I -P(s)) -1 |π(s) (54)
where π(s) is the the vector made of coefficients π(a) -s and we recall x|y is the inner product of vectors x and y.

To find the behavior of c(z) for large z near the real axis we apply the inverse Mellin approach as discussed in [START_REF] Flajolet | Analytic Combinatorics[END_REF][START_REF] Szpankowski | Analysis of Algorithms on Sequences[END_REF]. We observe that

c(z) = 1 2πi -3/2+∞ -3/2-∞ c * (s)z -s ds.
The asymptotics of c(z) for | arg(z)| < θ is given by the residues of the function c * (s)z -s occurring at the poles s = -1 and s = 0. They are respectively equal to 2 log 2 h z and -1 -1(I -P(0, 0)) -1 π(0) .

The first residues comes from the singularity of (I -P(s)) -1 at s = -1. This leads to Theorem 2(i).

When P is rationally related then there are additional poles on a countable set of complex numbers s k regularly spaced on the line ℜ(s k ) = -1, and such that P(s k ) has eigenvalue 1. These poles contributes to the periodic terms of Theorem 2(ii). The proof of Theorem 2 is now complete.

Double Mellin transform: Case P 1 = P 2

From now on we only consider the case P 1 = P 2 , and therefore we need to study properties of C a (z, z) through double Mellin transform defined as

C * a (s 1 , s 2 ) = ∞ 0 ∞ 0 C a (z 1 , z 2 )z s1-1 1 z s2-1 2 dz 1 dz 2 (55)
or similarly the Mellin transform C * (s 1 , s 2 ) applied to C(z 1 , z 2 ), provided we can find a strip a < ℜ(s 1 ), ℜ(s 2 ) < b where the above transforms exist. Since for any y ∈ R + and a function f we have the identity

∞ 0 f (yx)x s-1 dx = a -s ∞ 0 f (x)x s-1 dx we conclude that C * (s 1 , s 2 ) = Γ(s 1 )Γ(s 2 )1 + P(s 1 , s 2 )C * (s 1 , s 2 ) (56) or formally C * (s 1 , s 2 ) = Γ(s 1 )Γ(s 2 ) (I -P(s 1 , s 2 )) -1 1. (57)
However, the above formal derivation needs to be amended with a careful analysis of the convergence issues, which we do next. Notice that for any a ∈ A:

C a (z 1 , z 2 ) = O(|z 1 | + |z 2 |) when z 1 , z 2 → ∞. But as easy to check C a (z 1 , z 2 ) is also O(|z 1 | + |z 2 |) when z 1 , z 2 → 0,
therefore the Mellin transform is not appropriately defined in (55). To correct it, we now introduce correction terms in the expression of C a (z 1 , z 2 ) so that the corresponding Mellin transform exists for -2 < ℜ(s 1 ), ℜ(s 2 ) < -1.

To continue, we now define a slightly modified Mellin transform, namely

C(z 1 , z 2 ) = C(z 1 , z 2 ) -D(z 1 , z 2 )
where

D(z 1 , z 2 ) = z 1 e -z1 C 1 (z 2 ) + z 2 e -z2 C 2 (z 1 ) -C 1,1 z 1 z 2 e -z1-z2 with C 1 (z) = ∂ ∂z 1 C(z 1 , z 2 )| (z1,z2)=(0,z) C 2 (z) = ∂ ∂z 2 C(z 1 , z 2 )| (z1,z2)=(z,0) . 20 Notice that C(z 1 , z 2 ) is now O(|z 1 | 2 +|z 2 | 2 ) when z 1 , z 2 → 0. We can show that C(z 1 , z 2 ) = O(|z 1 |+|z 2 |) for (z 1 , z 2 ) in four dimension cone containing R + ×R + , therefore by Ascoli theorem ∂ ∂z1 C(z 1 , z 2 ) = O(1) in the same cone, D 1 (z) is O(|z|) for z ∈ R + , and similarly D 2 (z) is O(1). All of this is to state that C(z 1 , z 2 ) is O(|z 1 | + |z 2 |) when z 1 , z 2 → ∞,
thus the Mellin transform of C(z 1 , z 2 ) is well defined for ℜ(s 1 ), ℜ(s 2 ) ∈ (-2, -1). Let C * (s 1 , s 2 ) be the corresponding Mellin transform.

For a ∈ A let C 1a (z) be the coefficient of the vector C 1 (z) corresponding to the symbol a. For b ∈ A we have the functional equation

C 1b (z) = 1 -e -z + a∈A P 1 (a|b)C 1a (P 2 (a|b)z) (58)
and the Mellin transform of C 1 (z), say C * 1 (s) formally satisfies

C 1 (s) = -Γ(s)1 + P(-1, s)C 1 (s) (59) or C 1 (s) = -Γ(s)(I -P(-1, s)) -1 1. ( 60
)
Similarly the Mellin transform C 2 (s) of C 2 (z) satisfies C 2 (s) = Γ(s)(I -P(s, -1)) -1 1. To finish, we notice that C 1,1 = (I -P(-1, -1)) -1 . Denoting C(s 1 , s 2 ) = (I -P(s 1 , s 2 )) -1 1, we find

C * (s 1 , s 2 ) = Γ(s 1 )Γ(s 2 ) C(s 1 , s 2 ) + s 2 C(s 1 , -1)
+s 1 C(-1, s 2 ) + s 1 s 2 C(-1, -1)
finally leading to

C * (s 1 , s 2 ) = Γ(s 1 )Γ(s 2 ) 1 + π(s 1 , s 2 )| C(s 1 , s 2 ) (61)
where π(s 1 , s 2 ) denotes the vector composed of π 1 (a) -s1 π 2 (a) -s2 for a ∈ A and | is the vector internal product.

Our goal is to find C n,n (i.e., n = m). But by depoissonization it is asymptotically equal to C(n, n), therefore we must find C(z, z) which by the inverse Mellin transform becomes

C(z, z) = D(z, z) + 1 (2iπ) 2 ρ1 ρ2 C * (s 1 , s 2 )z -s1-s2 ds 1 ds 2 .
After some algebra we finally arrive at

C(z, z) = (1 -e -z ) 2 + (62) 1 (2iπ) 2 ρ1 ρ2 Γ(s 1 )Γ(s 2 ) π(s 1 , s 2 )| C(s 1 , s 2 )+s 2 C(s 1 , -1)+s 1 C(-1, s 2 )+s 1 s 2 C(-1, -1) z -s1-s2 ds 1 ds 2
where the integration is over the lines ℜ(s 1 ) = ρ 1 and ℜ(s 1 ) = ρ 2 with (ρ 1 , ρ 2 ) belonging to the fundamental strip of C * (s 1 , s 2 ): (-2, -1). We shall analyze asymptotically (62) in the next sections.

Properties of the Kernel

We recall from Section 2 that we define the kernel K as the set of complex tuples (s 1 , s 2 ) such that P(s 1 , s 2 ) has largest eigenvalue λ(s 1 , s 2 ) = 1. Furthermore, we also define ∂K as the subset of K consisting of the pairs (s 1 , s 2 ) such ℜ(s 1 , s 2 ) = (c 1 , c 2 ) where

(c 1 , c 2 ) = arg min (s1,s2)∈K {-s 1 -s 2 }.
We also denote ∂K * = ∂K -{(c 1 , c 2 )}. Let us start with the structure of the set ∂K.

Definition 6. Let P be a matrix on A × A of complex coefficients p ab for all (a, b) ∈ A 2 . Let Q be a matrix q ab . In the following we say P and Q are conjugate if there exists a non-zero complex vector (x a ) a∈A such that q ab = xa x b p ab . We say that such matrices are imaginary conjugate if |x a | = 1 for all a ∈ A.

Observe that: (i) two conjugate matrices have the same eigenvalue set; (ii) if u = (u a ) a∈A is right eigenvector of P, then (x a u a ) a∈A is right eigenvector of Q. Similarly, if (ζ a ) a∈A is left eigenvector of P, then ( 1 xa ζ a ) a∈A is the left eigenvector of Q. The following lemma is essential and proved in [START_REF] Jacquet | Joint String Complexity for Markov Sources, 23rd International Meeting on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms[END_REF] but we give an independent proof in the Appendix (see also [START_REF] Merhav | Average Redundancy of the Shannon Code for Markov Sources[END_REF]). Lemma 5. Let M = [m ab ] (a,b)∈A 2 be a matrix such that m ab ≥ 0. We assume that 1 is the largest eigenvalue of M. Let Q be a matrix with coefficients q ab = e iθ ab m ab where θ ab is real. The matrix Q has eigenvalue 1 if and only if Q is imaginary conjugate to matrix M. Corollary 1. Let c ∈ A. The matrix Q defined in Lemma 5 has eigenvalue 1 if and only if for all (a, b) ∈ A 2 :

1 2π (θ ab + θ ca -θ cb ) ∈ Z . ( 63
)
Proof. If Q is conjugate to M , we should have a real vector θ a∈A such that ∀(a, b) ∈ A 2 θ ab = θ a -θ b . Then e i(θa-θ b ) = e iθ cb e iθca , thus e i(θ cb -θca) = e iθ ab . Lemma 6. Let c ∈ A. A tuple (s 1 , s 2 ) belongs to ∂K iff for all (a, b) ∈ A 2 we have

ℑ(s 1 ) 2π log P 1 (a|b)P 1 (c|a) P 1 (c|b) - ℑ(s 2 ) 2π log P 2 (a|b)P 2 (c|a) P 2 (c|b) ∈ Z . (64)
Proof. Set M = P(c 1 , c 2 ) and Q = P(s 1 , s 2 ) for (s 1 , s 2 ) ∈ ∂K. Then, it follows directly from Corollary 1 with e iθ ab = (P 1 (a|b)) iℑ(s1) (P 2 (a|b)) -iℑ(s2) .

Furthermore, in the Appendix we prove the following important characterization of the set K. We say that a curve is strictly concave (or strictly convex) if the is never linear, even locally. Lemma 7. If P 1 and P 2 are not conjugate, then the set K is strictly concave.

We summarize our knowledge about ∂K.

Theorem 10. There are three possible structures of ∂K:

• the punctual case: ∂K = {(c 1 , c 2 )}, this is the most typical case;

• the linear case: there exist a vector (x, y) ∈ R 2 such that ∂K = {(c 1 , c 2 ) + ik(x, y), k ∈ Z};

• the lattice case: there exists two vectors (x 1 , y 1 ) and (x 2 , y 2 ) ∈ R 2 which are not colinear such that

∂K = {(c 1 , c 2 ) + ik 1 (x 1 , y 1 ) + ik 2 (x 2 , y 2 ), (k 1 , k 2 ) ∈ Z 2 .}.
Proof. This follows from the fact that according to Lemma 6 if (c

1 , c 2 ) + (s 1 , s 2 ) ∈ ∂K then ∀k ∈ Z (c 1 , c 2 ) + k(s 1 , s 2 ) ∈ ∂K. Furthermore if (c 1 , c 2 ) + (s ′ 1 , s ′ 2 ) ∈ ∂K then (s 1 , s 2 ) + a(s ′ 1 , s ′ 2 ) ∈ ∂K.
Thus K forms a lattice. In Lemma 6 this occurs when P 1 and P 2 are rationally related.

When both matrices P 1 and P 2 are logarithmically rationally related then we are in the lattice case, and the lattice is made of edges parallel to the axes. Anyhow the reverse is not necessarily true, although we don't know an explicit example of non logarithmically rationally related matrix which makes a pair of logarithmically commensurable matrices which would lead to edges non parallel to the axes.

When only one matrix is logarithmically rationally related, then we are in the linear case, and ∂K is a set of periodic points laying on one axis. It is nevertheless possible to have a linear case when none of the matrices is logarithmically rationally related, for example when P 1 and P 2 are of the form log * P 1 = 2πQ 1 + M and log * P 2 = -2πQ 2 + M where Q 1 and Q 2 have integer coefficients but M is not rationally related (in this case x log * P 1 + y log * P 2 integers would implies x = y. Now we establish some properties of the eigenvalue λ(s 1 , s 2 ) of P(s 1 , s 2 ). Lemma 8. For all s 2 such that ℜ(s 2 ) = c 2 , assume ∃s

1 : (s 1 , s 2 ) ∈ ∂K then λ(s 1 , s 2 ) = 1 ⇒ ℜ(s 1 ) < c 1 .
Proof. Notice that ℜ(s 1 ) = c 1 is not possible by construction since it would imply that (s 1 , s 2 ) ∈ ∂K. Let's consider the hypothesis ℜ(s 1 ) > c 1 . But we have |λ(s 1 , s 2 )| ≤ λ(ℜ(s 1 ), ℜ(s 2 ). Since ℜ(s 1 ) > c 1 , each non zero coefficient of P(ℜ(s 1 ), ℜ(s 2 )) are strictly smaller than the corresponding coefficients P(c 1 , ℜ(s 2 )) and therefore λ(ℜ(s 1 ), ℜ(s 2 )) < λ(c 1 , ℜ(s 2 )) = 1 which contradicts the hypothesis λ(s 1 , s 2 ) = 1.

Lemma 9. We have λ(c 1 , c 2 ) > |λ 2 (c 1 , c 2 )|.
Proof. It follows from Perron-Frobenius that the main eigenvalue is unique.

Let U be a complex neighborhood of 0 such that ∀s ∈ U: |λ(c 2 + s)| > |λ 2 (c 2 + s)|. Therefore the function λ(c 2 + s) is analytic. In the Appendix we prove the following lemma.

Lemma 10. Let (x k , y k ) be a sequence of complex numbers such that

lim k→∞ ℜ(x k , y k ) = (c 1 , c 2 ) and |λ(x k , y k )| → λ(c 1 , c 2 ) = 1. Then for all (s 1 , s 2 ) ∈ U we have ∀j : lim k→∞ λ j (x k + s 1 , y k + s 2 ) λ(x k + s 1 , y k + s 2 ) = λ j (c 1 + s 1 , c 2 + s 2 ) λ(c 1 + s 1 , c 2 + s 2 ) , ( 65
)
and the function λ(x k + s 1 , y k + s 2 ) are all analytic and uniformly bounded functions on a complex neighborhood of (0, 0) such that

lim k→∞ λ(x k + s 1 , y k + s 2 ) = λ(c 1 + s 1 , c 2 + s 2 ) (66) lim k→∞ ∇λ(x k + s 1 , y k + s 2 ) = ∇λ(c 1 + s 1 , c 2 + s 2 ) . ( 67
)
where ∇f is the gradient of f .

Proof of Theorem 3: Nilpotent Case

In this section we consider the case when the matrix P(s 1 , s 2 ) is nilpotent, that is, there exists K such that P K (s 1 , s 2 ) = 0 for all (s 1 , s 2 ). We first provide a simple derivation, and then "recover" it through the Mellin approach. Notice that for z ∈ C

1 + z 1 C |(I -zP(0, 0)) -1 1 = 1 + k≤K z k+1 1 C |P k (0, 0)1
is the generating function that enumerates all the common words between the language of source 1 and the language of source 2, including the empty word. Let us call this set W. Observe that 1 C |1 enumerate the word of length 1, and |W| = 1 + 1 C |(I -P(0, 0)) -1 1 is the total number of such common words. Notice that such words are all of length smaller than K. Since the Markov source are stationary we also notice that π(0, 0) = 1 C . The quantity J n,m converges to

1 + 1 C |(I -P(0, 0)) -1 1
when n, m → ∞ because all words in W will appear in both string almost surely. Indeed each word in w ∈ W may not appear in one string with exponentially small probability.

For similar reasons C n,m will converge to Interestingly enough we can find partially this result via the reverse Mellin transform (62). Partially because the error term is O(n -M ) for all M > 0. Let

D(s 1 , s 2 ) = π(s 1 , s 2 )| C(s 1 , s 2 ) + s 1 C(s 1 , -1) +s 1 C(-1, s 2 ) + s 1 s 2 C(-1, -1) .
We notice that D(s 1 , s 2 ) is never singular and furthermore for all s D(s, -1) = D(-1, s) = 0. Let

D n = 1 (2iπ) 2 ρ1 ρ2 Γ(s 1 )Γ(s 2 )D(s 1 , s 2 )n -s1-s2 .
Thus by (62) we find C(n, n) = (1 -e -n ) 2 + D n . Let M be an arbitrary non negative (large) number. By moving the integration path for s 2 from ℜ(s 2 ) = ρ 1 to ℜ(s 2 ) = M we only met the poles of Γ(s 2 ) on

s 2 = -1 with residues 1 2iπ ρ1 Γ(s 1 )D(s 1 , -1)n 1-s1 ds 1 and - 1 2iπ ρ1 Γ(s 1 )D(s 1 , 0)n -s1 ds 1 .
The first residues is null since D(s 1 , -1) = 0, thus

D n = - 1 2iπ ρ1 Γ(s 1 )D(s 1 , 0)n -s1 ds 1 + 1 (2iπ) 2 ρ1 M Γ(s 1 )Γ(s 2 )n -s1-s2
where the second term in the right-hand side is O(n -M-ρ1 ). The integration path -1 2iπ ρ1 Γ(s 1 )D(s 1 , 0)n -s1 ds 1 can also be moved on ℜ(s 1 ) = M , the residues on s 1 = -1 is D(-1, 0)n, which is null, and on s 1 = 0 is equal to D(0, 0). Thus

D n = D(0, 0) - 1 2iπ M Γ(s 1 )D(s 1 , 0)n -s1 + O(n -M-ρ1 ). ( 68
)
Since 1 2iπ M Γ(s 1 )D(s 1 , 0)n -s1 = O(n -M ) and that D(0, 0) = 1 C |(I -P(0, 0)) -1 1 , this concludes the proof.

Special Case: Proofs of Theorems 4 -5

To simplify our presentation we will first assume that

P 1 = 1 |A| 1 ⊗ 1,
i.e. the first source is uniform and memoryless. We will see in the next section how to translate these results into the general case.

In this case, we have

P(s 1 , s 2 ) = |A| s1 P(s 2 ) ( 69
)
with P(s) = P(0, s). We also write π(a) = π 2 (a) and π(s) = π(0, s), thus

π(s 1 , s 2 ) = |A| s1 π(s 2 ) . ( 70
)
Let λ(s 1 , s 2 ) be the main (largest) eigenvalue of P(s 1 , s 2 ). We have

λ(s 1 , s 2 ) = |A| s1 λ(s 2 ) ( 71
)
where λ(s) is the main eigenvalue of matrix P(s). We also define u(s) as the right eigenvector of P(s) and ζ(s) as the left eigenvector provided ζ(s)|u(s) = 1. We first present some simple results regarding λ(s) and L(s) = log |A| λ(s).

Lemma 11. The function L(s) is convex when s is real.

Proof. The function (-L(s), s) describes the set K which is known to be a concave curve by Lemma 1.

Notice that the proof will also be valid for the general case.

The proof of the following lemma is left for the reader.

Lemma 12. We have the following identities:

λ(s) = ζ(s)|P(s)u(s) = a,b ζ a (s)u b (s)P (a|b) -s , λ ′ (s) = ζ(s)|P ′ (s)u(s) = a
L ′′ (s) = a,b x a,b (log P (a|b)) 2 -   a,b
x a,b log P (a|b)

  2 . ( 73
)
Now we are ready to derive our results presented in Theorems 4 -5. The starting point is the Mellin transform C * (s 1 , s 2 ) shown in (61) with C * (s 1 , s 2 ) presented in (57). To recover C n,n we first need to find the inverse Mellin transform of (61). For -2 < ρ < -1 we have

C(z, z) -D(z, z) = 1 (2iπ) 2 ℜ(s1)=ℜ(s2)=ρ C * (s 1 , s 2 )z -s1-s2 ds 1 ds 2 = 1 (2iπ) 2 ℜ(s1)=ℜ(s2)=ρ Γ(s 1 )Γ(s 2 ) C(s 1 , s 2 ) + s 2 C(s 1 , -1)
+s 1 C(-1, s 2 ) + s 1 s 2 C(-1, -1) z -s1-s2 ds 1 ds 2 ,
where C(s 1 , s 2 ) = (I -P(s 1 , s 2 )) -1 1 and

C(s 1 , s 2 ) = π(s 1 , s 2 ) (I -P(s 1 , s 2 )) -1 1 . Since C(z, z) = D(z, z) + O(z -M ) for any M > 0 when ℜ(z) → ∞ we find C(z, z) -1 + O(z -M ) = 1 (2iπ) 2 ℜ(s1)=ℜ(s2)=ρ Γ(s 1 )Γ(s 2 ) (74) × C(s 1 , s 2 ) + s 2 C(s 1 , -1) s 1 C(-1, s 2 ) + s 1 s 2 C(-1, -1) z -s1-s2 ds 1 ds 2 .
To analyze it asymptotically, we investigate the set of singularities of (I-P(s

1 , s 2 )) -1 in C(s 1 , s 2 ). Recall that K is the set of complex numbers (s 1 , s 2 ) such that I -P(s 1 , s 2 ) is degenerate, i.e. (I -P(s 1 , s 2 )) -1 is singular.
Let λ 1 (s), λ 2 (s) . . . , λ |A| (s)) be the eigenvalues of P(s) in the non-increasing order (e.g., λ(s) := λ 1 (s)) while u i (s) and ζ i (s)) are respectively the right and the left eigenvectors of P(s) associated with λ i (s) subject to ζ i (s)|u i (s) = 1. By the spectral representation of matrices [START_REF] Szpankowski | Analysis of Algorithms on Sequences[END_REF], we have

(I -P(s 1 , s 2 )) -1 = |A| i=1 1 1 -|A| s1 λ i (s 2 ) u i (s 2 ) ⊗ ζ i (s 2 ) ( 75
)
where ⊗ denotes the tensor product. Observe that (I -P(s 1 , s 2 )) -1 cease to exist at (s 1 , s 2 ) satisfying

|A| s1 λ i (s 2 ) = 1, that is, for s 1 := L i,k (s 2 )
where

L i,k (s 2 ) = 1 -log |A| (log λ i (s 2 ) + 2ikπ).
The eigenvalues λ i (s) are individually analytic functions of s in any complex neighborhood where the order of the eigenvalues modulus does not change (i.e.

|λ i-1 (s)| > |λ i (s)| > |λ i+1 (s)| for all i).
But any function of the form i f (λ i (s)) is analytic even when the eigenvalue sequence is not strictly decreasing, as long as f () is analytic. To simplify our analysis, we also postulate that none of the eigenvalue is identically equal to zero, that is, we assume log λ i (s) exists except on a countable set R = {s : ∃i : λ i (s) = 0}. It should be pointed out that there are cases when some eigenvalues are identically equal to zero. For example, for memoryless sources we have for all i ≥ 2: λ i (s) ≡ 0 which we already discussed in [START_REF] Jacquet | Common words between two random strings[END_REF][START_REF] Jacquet | Analytic Pattern Matching: From DNA to Twitter[END_REF] so we will omit them here.

In order to evaluate the integral in (74) we first use (75) and then apply the residue theorem. To simplify, for 1 ≤ j ≤ |A|, let f j (s) = π(s)|u i (s) and g j (s) = ζ i (s)|1 . Define (here we set s := s 2 )

I(z, ρ) = (76) 1 2iπ ℜ(s)=ρ k∈Z |A| j=1 f j (s)g j (s)Γ(-L j,k (s))Γ(s) λ j (s) log |A| z L j,k (s)-s ds J(z, ρ) = 1 2iπ ℜ(s)=ρ C(0, s)Γ(s)z -s ds. (77)
Furthermore, let

H j (s, z) = k∈Z f j (s)g j (s 2 )Γ(-L j,k (s)) λ i (s) log |A| z L j,k (s) (78) thus I(z, ρ) = 1 2iπ j ℜ(s)=ρ H j (s, z)Γ(s)z -s ds.
The next lemma is crucial for the asymptotic evaluation of C(z, z) which by depoissonization lead to asymptotics of C n,n and ultimately J n,n . Lemma 13. For any M > 0 and for some ρ > -1, we have

C(z, z) = 1 + I(z, ρ) -J(z, ρ) + O(z -M ) (79)
for z → ∞.

Proof. In the inverse Mellin expression we see that for ℜ(s 1 ) = ℜ(s 2 ) = -1 we have |P(s 1 , s 2 )| ≤ P(-1, -1) and P(-1, -1) ≤ P 1 (-1) and P 2 (-1). Since the matrix P(s 1 , s 2 ) is not nilpotent there exists (a, b) ∈ A 2 such that |P(s 1 , s 2 ) a,b | < P(a|b). Consequently, there exists k such that |P k (s 1 , s 2 )|1 < 1 or more precisely |λ 1 (s 1 , s 2 )| ≤ 1 -ǫ ′ for some ǫ ′ > 0. Thus there exists ǫ > 0 such that for all s 1 , s 2 ℜ(s 1 ) > -1 + ǫ and ℜ(s 2 ) > -1 + ǫ implies that I -P(s 1 , s 2 ) is not degenerate.

To evaluate the inverse Mellin transform we apply standard approach by moving the line of integration to "catch up" relevant singularities, however, in our case there some complications. We move the integration path by increasing ρ. This does not change the value of I(z, ρ) and J(z, ρ) as long as the functions in the integral paths are analytic and not singular. When the path encounter a singularity we will use the residue theorem. But we may have a problem when any of the functions λ j ceases to be analytic. However, we shall see that when we sum all the terms of the integrand of I(z, ρ) we obtain an analytic function derived from π(s 1 , s 2 )(I -P(s 1 , s 2 )) -1 1 . Indeed we have the (somewhat complicated) identity

I(z, ρ) = k∈Z ℜ(s)=ρ π(s)|(P(s)) -1 exp - log z log |A| (log P(s) + 2ikπI) Γ - 1 log |A| (log P(s) + 2ikπI) 1 ds , (80)
knowing that any analytical function f (.) can be applied to matrix P(s) as long its eigenvalues do not correspond to a singularity of the function f (.). Therefore the only singularities that we meet when we move the integration line of I(z, ρ) are the elements of R = {s : λ i (s) = 0, for some i}.

If θ ∈ R, is one of these singularity, thus we have λ i (θ) = 0, then the function

L i,k (s) = 1 -log |A| (log λ i (s)+ 2ikπ
) is meromorphic around θ. However if θ is a simple pole of λ i (s), then moving around θ would be equivalent to add 1 to the integer k: log λ i (s) → log λ i (s) + 2iπ. If the root is of multiplicity ℓ it is equivalent to add ℓ to the integer k. In any case the function H i (s, z) being invariant when ℓ is added to k, turns out to be fully analytic around θ, and the integration path in I(z, ρ) can be moved over θ.

However, the function λ i (s) is a non polar singular on s = θ, hence there will be a contribution coming from the integration of H i (s, z)Γ(s)z -s on an arbitrary small loop around θ. Since ℜ(L i,k (s)) → -∞ when s → θ, having ℜ(L i,k (s)) < -M will guarantee that the contribution is in O(z 1-M ) and can be included in the error term.

Moving the integration path from ℜ(s 1 ) = ℜ(s 2 ) = ρ to ℜ(s 1 ) = ℜ(s 2 ) = -1 + ǫ will only hit the poles of Γ(s 1 )Γ(s 2 ) at s 1 = -1 and s 2 = -1. By construction of the function C(s 1 , s 2 ) + s 1 C(-1, s 2 ) + s 2 C(s 1 , -1) + s 1 s 2 C(-1, -1), the residues at these points are zero. Therefore the expression

C(z, z) -1 + O(z -M ) = 1 (2iπ) 2 ℜ(s1)=ℜ(s2)=ρ Γ(s 1 )Γ(s 2 ) × C(s 1 , s 2 ) + s 2 C(s 1 , -1)
s 1 C(-1, s 2 ) + s 1 s 2 C(-1, -1) z -s1-s2 ds 1 ds 2
still holds for ρ = -1 + ǫ. Now we take the integration contour for s 1 and we move it from ℜ(s 1 ) = ρ to ℜ(s 1 ) = M -ρ. By doing so we encounter many poles: (i) The poles of (I -P(s 1 , s 2 )) -1 at s 1 = L j,k (s 2 ). The residues is exactly the expression I(z, ρ).

(ii) The poles of C(s 1 , s 2 )Γ(s 1 ) at s 1 = 0 which has residues -J(z, ρ).

(iii) The double pole of C(s 1 , -1)Γ(s 1 )z -s1 at s 1 = 0 since (I -P(s 1 , s 2 )) -1 is singular at (s 1 , s 2 ) = (0, -1) because λ 1 (0, -1) = 1. It leads to the residue - 1 2iπ ℜ(s)=ρ sΓ(s)(a log z + b)z -s ds (81)
for some real number a and b coming from the derivative of f 1 (s) and g 1 (s) at s = 0. But when one moves the integration path of (81) to ℜ(s) = M the function sΓ(s)(a log z + b) has no singularity since sΓ(s) is not singular on the interval ] -1, +∞[, and thus the integration on ℜ(s) = M is O(z -M ), which can be included in the error term.

In the following we denote L(s) = L 1,0 (s) . The rule of the game is that we move the integration abscissa of I(z, ρ) and J(z, ρ) to the left (i.e. to larger values) on the value c 2 which minimizes the argument L(s) -s. Moving the integration path one meets some poles of Γ(-L j (s)) when L j (s) = 0. In fact when the matrices are strictly non negative, this case only applies to j ≥ 2. It turns out that when s is a pole for Γ(-L j (s)) then it is at the same time a pole of C(0, s). The residues of I(z, ρ) and J(z, ρ) when passes over such value are the same and cancel. Therefore C(z, z) = 1 + I(z, ρ)-J(z, ρ)+ O(z -M ) for all values of ρ < 0.

Proof of Theorems 4 and 5

Now we are going to prove Theorems 4 and 5 corresponding to the case where quantities c 1 and c 2 are both in the interval [-1, 0] in the case where one source is uniform memoryless. In this case, the main contribution to C(z, z) doesn't come from the poles, as in the previous section, but rather from the saddle point of z L1,0-s (in fact, infinitely many saddle points).

We start with reviewing some properties of the kernel K and the main eigenvalue. Recall that ∂K is the set of complex tuples (s 1 , s 2 ) satisfying |A| s1 λ(s 2 ) = 1 such that ℜ(s 1 ) = c 1 and ℜ(s 2 ) = c 2 . Its structure is crucial for our asymptotic analysis.

From the general Theorem 10 we deduce that only two cases are possible when one source, say source 1, is uniform (since P 1 is logarithmically rationally related):

• the lattice case when P 2 is also logarithmically rationally related, we call this case the rational case;

• the linear case when P 2 is not logarithmically rationally related, we call this case the irrational case;

Now we focus on proving in the next four lemmas that the main eigenvalue is well separated.

Lemma 14. Let t 2 be a real number. We have the equivalence , then there will be t 1 such that |A| it1 λ(s 2 ) = λ(c 2 ), and therefore (c 1 + it 1 , s 2 ) ∈ ∂K.

∄(s 1 , s 2 ) ∈ ∂K ℑ(s 2 ) = t 2 ⇐⇒ |λ(c 2 + it 2 )| < λ(c 2 ).
Lemma 15. We have a non zero spectral gap, that is, λ(c 2 ) > λ 2 (c 2 ).

Proof. It follows from Perron-Frobenius that the main eigenvalue is unique.

Let U be a complex neighborhood of 0 such that ∀s ∈ U: |λ(c 2 + s)| > |λ 2 (c 2 + s)|. Therefore the function λ(c 2 + s) is analytic.

Lemma 16. Let s k be a sequence such that ℜ(s k ) = c 2 and |λ(s k )| → λ(c 2 ). Then for all s ∈ U we have

lim k→∞ L(s k + s) -L(s k ) = L(c 2 + s) -L(c 2 ) (82) lim k→∞ L ′ (s k + s) = L ′ (c 2 + s) . (83)
The convergence also holds for any derivative of function L ′ (s), and the function λ(s k + s) is analytic and uniformly bounded on a complex neighborhood of 0.

= λ j (c 1 , c 2 + s) λ(c 1 , c 2 + s) = λ j (c 2 + s) λ(c 2 + s) (84)
Since |λ2(c2)| λ(c2) < 1, there exists U such that ∀s ∈ U:

λj (c2+s)
λ(c2+s) < 1 thus λ(c 2 + s) is analytic because it never cross the value of another eigenvalue and so is λ(s k + s).

Hence, the logarithm of the eigenvalue, L(s k + s) -L(s k ) converges to L(c 2 + s) -L(c 2 ). The property |λ(c 1 + s, c 2 + s 2 )| > λ 2 (c 2 + s) for all s ∈ U implies the analyticity of L(c 2 + s), and therefore L ′ (c 2 + s).

In passing, we have L ′ (s k ) → 1 and L ′′ (s k ) → α 2 . Finally, we prove that the main eigenvalue dominates all other eigenvalues in a complex neighborhood of c 2 .

Lemma 17. There exists ǫ > 0 such that for all i = 1 and for all s such that ℜ(s) = c 2 :

|λ i (s)| < λ(c 2 ) -ǫ . ( 85
)
Proof. This is a consequence of previous lemmas. Suppose that there exists s k such that |λ 2 (s k )| → λ(c 2 ). This implies that |λ(s k )| → λ(c 2 ), but by previous lemma

|λ 2 (s k )| → λ 2 (c 2 ) = λ(c 2 ) -ǫ.
Now we are in the position to evaluate the integral of C(z, z) by the saddle point methods. Recall that for all M > 0 we have C(z, z) = I(z, c 2 )-J(z, c 2 )+1+O(z 1-M ) where I(z, ρ) and J(z, ρ) are given by (76). We already prove that J(z, c 2 ) = O(z c2 ) = O(z κ-ǫ ) for some ǫ > 0 (in fact ǫ = L(c 2 ) > 0). We reinforce it in the next lemma.

Lemma 18. There exists ǫ > 0 such that

C(z, z) = 1 + 1 2iπ ℜ(s)=c2 H 1 (s, z)Γ(s)z -s ds + O(z κ-ǫ ) ( 86
)
where κ = -c 1 -c 2 and we recall that

H 1 (z, s) = k∈Z f 1 (s)g 1 (s)Γ(-L 1,k (s)) λ(s) log |A| .
Proof. By Lemma 17 for all j > 1 we have log |A| |λ j (s)| < log |A| λ(c 2 ) -ǫ for some ǫ > 0, thus the contribution of ℜ(s)=c2 H j (s, z)Γ(s)z -s ds is of order

ℜ(s)=c2 |Γ(s)|z ℜ(Lj (s)-s) ds = O z L(c2)-c2-ǫ = O z κ-ǫ ,
as desired.

Rational Case. We assume now that the matrix log * ( 1 P (c|c) P) is rationally balanced. The matrix P(s + 2iπν) is then imaginary conjugate with the matrix P (c|c) 2iπν P(s) and L(s + 2iπν) = L(s) + 2iπν log P (c|c). Thus ℜ(L(c 2 + it)) is periodic in t with period 2πν. Furthermore, L ′ (s) is also periodic with period 2πν. Thus, s ℓ = c 2 + 2iπℓν for ℓ ∈ Z are saddle points of z L(s)-s .

We concentrate now on the term k = 0 in H 1 (s, z)Γ(s)z -s in (86). Define

b 2 (s) = d 2 ds 2 log f 1 (s)g 1 (s) λ 1 (s) Γ(-L(s))Γ(s) . (87)
1 2iπ ℜ(s)=c2 f (s)g(s) λ(s) Γ(-L(s))Γ(s)z L(s)-s ds = = ℓ f (s ℓ )g(s ℓ ) λ(s ℓ ) Γ(-L(s ℓ ))Γ(s ℓ ) × z L(s ℓ )-s ℓ 2π(α 2 log z + b 2 (s ℓ )) (1 + o(1)). (88)
Notice that ℜ(L(s ℓ ) -s ℓ ) = κ. When adding the contribution from the L(s) + 2ikπ log |A| we obtain the expression for Q(log z) with ∂K = {(-L(s ℓ ) -2ikπ log |A| , s ℓ ), (k, ℓ) ∈ Z 2 }. The double periodicity comes from the fact that √ xQ(x) = k,ℓ q k,ℓ e i(kα+ℓβ)x + o(1) when x → ∞ for some incommensurable3 pair of real numbers (α, β) and complex numbers {q k,ℓ } (k,ℓ)∈Z 2 .

Irrational Case. We now turn to the irrational case. Let A > 0 be a number such that for all |s| ≤ A we have |λ(c 2 + s)| > |λ 2 (c 2 + s)|; thus L(c 2 + s) is analytic. We assume that c 2 < 0 is the only saddle point on ℜ(s) = c 2 for |ℑ(s)| ≤ A. There also exists α 3 > 0 such that

|t| ≤ A ⇒ ℜ(L(c 2 + it) -L(c 2 )) ≤ -α 3 t 2 . ( 89
)
From the previous analysis we know that

1 2iπ k∈Z ℜ(s)=c2,|ℑ(s)|≤A f (s)g(s) λ(s) log |A| ×Γ -L(s) - 2ikπ log |A| ×Γ(s)z L(s)-s+2ikπ/ log |A| ds = Q(log z)(1 + o(1)). (90)
Assume now (89) and define

ξ(s) = k∈Z Γ s - 2ikπ log |A| . ( 91
)
The function ξ(s) is continuous and bounded as long as ℜ(s) is bounded. Our aim is to prove that 1 2iπ

ℜ(s)=c2,|ℑ(s)|>A f (s)g(s) λ(s) ξ(-L(s)) ×|Γ(s)|z ℜ(L(s))-c2 ds = o( z κ √ log z ) , (92)
which will complete the proof of Theorem 4.

We know that |f (s)g(s)| ≤ f (c 2 )g(c 2 ). In addition, we know that for ℜ(s) = c 2 we have ℜ(L(s)) < L(c 2 ) as long as ℑ(s) = 0. We also have |λ(s)| > ǫ ′ for some ǫ ′ > 0 since the matrix P(s) stays away from the null matrix. Therefore, we need to estimate

ℜ(s)=c2,|ℑ(s)|>A |Γ(s)|z ℜ(L(s))-c2 ds . (93)
For any ǫ > 0, the portion of the line ℜ(s) = c 2 , where ℜ(L(s)) < L(c 2 ) -ǫ, contributes z κ-ǫ to C(z, z).

Our attention must turn to the values of s on this line such that ℜ(L(s)) is arbitrary close to L(c 2 ). In particular, we are interested in the local maxima of ℜ(L(s)) that are arbitrary close to L(c 2 ). Indeed, these local maxima play a role in the saddle point method.

Let us consider the sequence of those maxima denoted by s ℓ for ℓ ∈ N such that ℜ(L(s ℓ )) → L(c 2 ). By Lemma 10 we know that for all real t L(s ℓ + it) -L(s ℓ ) → L(c 2 + it) -L(c 2 ) and that L ′ (s ℓ + it) → L ′ (c 2 + it). Therefore for all real t such |t| ≤ A lim sup

ℓ→∞ (ℜ(L(s ℓ + it)) -ℜ(L(s ℓ ))) ≤ -α 3 t 2 . ( 94
)
We define I(A) to be the set of complex numbers s such that ℜ(s) = c 2 and min ℓ {|s -s ℓ |} > A.

Lemma 19. There exists ǫ such that for all s ∈ I(A): ℜ(L(s)) < L(c 2 ) -ǫ.

Proof. Assume s ∈ I(A). Since s is not a local maxima, we study the variation of ℜ(L(s)) around the local maxima s ℓ . Without loss of generality we assume that s ℓ -A is between s and s ℓ , thus

ℜ(L(s ℓ -A)) > ℜ(s). Since lim sup ℜ(L(s ℓ -A)) < L(c 2 ) -α 3 A 2 < L(c 2 ) -ǫ the lemma is proved.
In view of the above, we conclude that

ℜ(s)=c2,|ℑ(s)|>A |Γ(s)|z ℜ(L(s))-c2 ds ≤ ℓ |t|≤A |Γ(s ℓ + it)|z ℜ(L(s ℓ +it))-c2 dt + O(z κ-ǫ ) . (95)
By virtue of the properties of function Γ(s) on the imaginary lines, there exists a real B > 0 such that ∀s:

ℜ(s) = c 2 ⇒ max |t|≤A {|Γ(s + it)|} ≤ B|Γ(s)| . (96)
Therefore, our analysis can be limited to

ℓ |t|≤A |Γ(s ℓ )|z ℜ(L(s ℓ +it))-c2 dt . (97)
Finally, we establish a separation result.

Lemma 20. For ℓ tending to infinity, the s ℓ are separated by a distance at least equal to A.

Proof. First, let us assume that ℓ, ℓ ′ → ∞ and |s ℓ -s ℓ ′ | → 0, then we have

L ′ (s ℓ ′ ) = L ′ (s ℓ ) + (s ℓ ′ -s ℓ )L ′′ (s ℓ ) + O(|s ℓ -s ℓ ′ | 2 ). ( 98
) Since L ′′ (s ℓ ) → α 2 = 0, then we cannot have L ′ (s ℓ ′ ) = 1, thus s ℓ ′ cannot be a local maximum of ℜ(L(s)). Second, if lim inf |s ℓ -s ℓ ′ | > ǫ for some ǫ > 0 with |s ℓ -s ℓ ′ | < A, then using the inequality lim sup ℜ(L(s ℓ ′ )) -ℜ(s ℓ ) ≤ -α 3 |s ℓ -s ℓ ′ | 2 < -α 3 ǫ 2 (99) we cannot have ℜ(L(s ℓ ′ )) → L(c 2 ).
From the above we conclude

|t|≤A z ℜ(L(s ℓ +it))-c2 dt = z κ z ℜ(s ℓ )-L(c2) |t|≤A z ℜ(L(s ℓ +it))-ℜ(L(s ℓ ) dt . (100)
In summary, the consequence of the previous lemma is that since lim sup ℓ→∞ ℜ(L(s ℓ + it)) -ℜ(L(s ℓ ) ≤ -α 3 t 2 , we have [START_REF] Szpankowski | Analysis of Algorithms on Sequences[END_REF] lim sup

ℓ→∞ |t|≤A z ℜ(L(s ℓ +it))-ℜ(L(s ℓ ) dt ≤ 1 √ πα 3 log z , (101)
and the properties of function Γ(s) is that ℓ |Γ(s ℓ )| < ∞. Therefore,

ℓ |t|≤A |Γ(s ℓ )|z ℜ(L(s ℓ +it))-c2 dt = z κ ℓ |Γ(s ℓ )|z ℜ(s ℓ )-L(c2) × |t|≤A z ℜ(L(s ℓ +it))-ℜ(L(s ℓ ) dt (102)
since lim z→∞ z ℜ(s ℓ )-L(c2) = 0, by the dominating convergence theorem. We finally arrive at

ℓ |Γ(s ℓ )|z ℜ(s ℓ )-L(c2) |t|≤A z ℜ(L(s ℓ +it))-ℜ(L(s ℓ ) dt = o( 1 √ log z ) . (103)
In fact, the saddle point expansion is extendible to any order of 1 √ log n . This proves Theorems 4 and 5. In passing we observe that when P 1 and P 2 are logarithmically commensurable, the line ℜ(s 1 ) = c 1 contains an infinite number of saddle points that contribute to the double periodic function Q 2 (log n) (cf. [START_REF] Jacquet | Joint String Complexity for Markov Sources, 23rd International Meeting on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms[END_REF] for more details).

7 General Case: Proofs of Theorem 6 -9

We now look at the general case when P 1 = P 2 . The main difficulty of the general case is when P 1 and P 2 have some zero coefficients, not at the same locations. For example P(-1, 0) may differ from P 1 , and P(0, -1) may differ from P 2 since P(s 1 , s 2 ) retains only the coefficients that are both non zero in P 1 and P 2 . For example, P(-1, 0) and P(0, -1) may be conjugate while P 1 and P 2 are not. Indeed we can have P(-1, 0) = P(0, -1) even when P 1 = P 2 .

In this section we first prove Theorem 6 which consider the case when P(-1, 0) and P(0, -1) are conjugate. Then we present a detailed proof of Theorem 7, and finally we briefly discussed proofs of Theorems 8-9.

Proof of Theorem 6. When P(-1, 0) and P(0, -1) are conjugate, the situation is more similar to the case when P -1 = P 2 discussed in Section 4. In particular there is no saddle point, and the analysis reduces to computing some residues of poles.

To start, we notice that in this case there exists a vector of real numbers (x a ) a∈A such that

P 1 (a|b)P 2 (a|b) > 0 ⇒ P 2 (a|b) x a x b P 1 (a|b).
As a consequence we have the same spectrum of P(c -s, s) for all c and s, and thus we have the identity λ(c -s, s) = λ(c, 0). We will prove the result when ∀a ∈ A : x a 1. This does not implies that P 1 = P 2 since the above identity only applies to nonzero coefficients in both matrices. In fact we only have P(-1, 0) = P(0, -1). We also notice that P(s, 1 -s) is identical for all s. We leave as an exercise the case where the x a are not identical. We notice that K consists of the tuple (s, 1 -s) where s is real. We know that

C(z 1 , z 2 ) = (1 -e -z1 )(1 -e -z2 ) + a∈A C a (π 1 (a)z 1 , π 2 (a)z 2 ). (104)
The issue here is that the π 1 (a) are not necessarily equal to the π 2 (a) because they also depend on the other coefficients of matrices P Let P = P(-1, 0) = P(0, -1), i.e. the matrix whose coefficients are those P 1 (a|b) when P 1 (a|b)P 2 (a|b) > 0, and zero otherwise.

From the functional equation

C a (z 1 , z 2 ) = (1 -e -z1 )(1 -e -z2 ) + c∈A C c (P (a|c)z 1 , P (a|c)z 2 ).
We have the identity The first singularity of G(s) is the pole of (I -P(s, 0)) -1 which is at s = -κ such that λ(s, 0) = 1. The only singular term of G * (s) at s = -κ is on its main eigenvectors:

g a,b (z) = (1 -e -π1(b)z )(1 -e -π2(b)z ) + c∈A g c,b (P (a|c)z). ( 105
Γ(s) 1 λ(s, 0) (ζ(s, 0) ⊗ u(s, 0)) (r(s) ⊗ 1) whose trace is Γ(s) 1 -λ(s, 0) r(s)|u(s, 0) ζ(s, 0)|1 .
Thus the residue of trace(G * (s)) is

γ 0 (-κ) = 1 λ ′ (-κ, 0) r(-κ)|u(-κ, 0) ζ(-κ, 0)|1 . The inverse Mellin gives C(z, z) = (1 -e -z ) 2 + z κ γ 0 (-κ) (1 + o(1)) . (107)
When P(-1, 0) is logarithmically rationally related, there are several poles of (I -P(s, 0)) regularly spaced on the vertical axis ℜ(s) = -κ giving a periodic contribution z κ Q 0 (log z).

Proof of theorem 7. Let H 1 (s 1 , s 2 ) = ∂ ∂s1 λ(s 1 , s 2 ) and

f (s 1 , s 2 ) = π(s 1 , s 2 )|u(s 1 , s 2 ) , g(s 1 , s 2 ) = ζ(s 1 , s 2 )|1 .
We first notice that Lemma 11 about the convexity of L 1 (s) is still valid since it depends only on general properties of the set K. Define now L j,k (s) implicitly as

λ j (-L j,k (s), s) = 1.
where λ j (s 1 , s 2 ) is the jth eigenvalues of matrix P(s 1 , s 2 ), listed in decreasing modulus. The index k indicates that these functions can be polymorphic since the root of the equation λ j (s 1 , s 2 ) = 1 for s 2 fixed can be multiple as we have seen in the case when one source is uniform memoryless. For j fixed, each of the functions L j,k (s) are homeomorphic as long as λ j (L j,k (s), s) is non ambiguous i.e. the jth eigenvalue has not the same modulus as the previous or next eigenvalues. This would happen only on a discrete set of values s.

Let now for 1 ≤ j ≤ |A| and k ∈ Z

f j,k (s) = π(-L j,k (s), s)|u j (-L j,k (s), s) , (108) g j,k (s) = ζ j (-L j,k (s), s)|1 . (109)
Then

I(z, ρ) = (110) 1 2iπ ℜ(s)=ρ k∈Z |A| j=1 f j,k (s)g j,k (s)Γ(-L j,k (s))Γ(s) -∂ ∂s1 λ j (-L j,k (s), s) z L j,k (s)-s ds and J(z, ρ) = 1 2iπ ℜ(s)=c2 C(0, s)Γ(s)z -s ds. (111)
With these new definitions the expression (79) in Lemma 13 is still valid, that is for all M > 0:

C(z, z) = 1 + I(z, ρ) + J(z, ρ) + O(z -M ).
The proof is indeed the same, the pole cancellations occur the same way and the identity between residues is formally the same. We know that for all k we have λ 1 (-L 1,k (s), s) = 1. We assume that = 0 defines the branch where L 1,0 (s) is real when s is real. To simplify we denote L(s) = L 1,0 (s). We then move the integration path to the value s = c 2 which attains the minimum of L(s) -s at s = κ. We know that the J(z, c 2 ) = O(z κ-ǫ ) for ǫ > 0 such that κ -ǫ > L(0). Therefore C(z, z) = 1 + I(z, c 2 ) + O(z κ-ǫ ) as in the case with uniform one source. Since z L(s)-s is at a minimum for real values of s, we have again a saddle point for ℜ(s)=c2 µ(s)z L(s)-s ds.

Thus we arrive to two cases: (i) either c 1 > 0 or c 2 > 0 or (ii) c 1 and c 2 are both negative. In the first case the condition of Theorem 7 applies. In the second case the condition of Theorem 8 applies. We consider the case c 2 > 0 (case c 1 > 0 is symmetric). Moving the integration toward ℜ(s) = c 2 one meets the pole of function Γ(s) at zero.

When we meet the pole at s = 0 by moving ρ toward the positive value we obtain a residue from I(z, ρ) equal to j H j (0, z) and a residue from J(z, ρ) equal to C(0, 0). Notice that H 1 (0, z) = Ω(z c0 ) since c 0 = L(0) > 0 while the residue from J(z, ρ) is negligible. The function H 1 (0, z) turns out to be the leading term since the other terms are of order z Lj(0) for j > 1 and ℜ(L j (0)) < L 1 (0). By moving again the integration path with ℜ(s) > 0 we arrive at ℜ(s) = c 2 thus C(z, z) = j H j (0, z) + I(z, c 2 ) + O(z -M ).

We know from the previous discussion that I(z, c 2 ) = O(z κ ) which is of order smaller than z L(0) per definition of κ. Therefore we have C(z, z) = 1 + H 1 (0, z) + O(z c0-ǫ ) for some ǫ > 0. Notice that H 1 (0, z) = f 1 (0)g 1 (0) λ 1 (0)

z c0 + Q 1 (log z)z c0
where Q 1 (.) is a periodic function of periodic log |A| and of mean 0 with small amplitude. Recapitulating all cases of Theorem 7: (i) when P(-1, 0) is not logarithmically related, then

C n,n = γ 1 (c 0 , 0)n -c0 (1 + o(1))
with γ 1 (s 1 , s 2 ) = f (s 1 , s 2 )g(s 1 , s 2 )(1 + s 1 )Γ(s 1 ) H 1 (s 1 , s 2 ) .

(ii) When P(-1, 0) is logarithmically commensurable

C n,n = n -c0 k∈Z n 2ikπν γ(c 0 + 2ikπν, 0) + O(n c0-ǫ )
where ν is the root of P 1 .

Proof of Lemma 4. In order to prove Lemma 4 we adopt here the following general double depoissonization lemma that is proved in [START_REF] Jacquet | Analytic Pattern Matching: From DNA to Twitter[END_REF] (see Lemmma 10.3.4 in Chapter 10).

Lemma 22. Let a n,m be a two-dimensional (double) sequence of complex numbers. We define the double Poisson transform f (z 1 , z 2 ) of a n,m as

f (z 1 , z 2 ) = n,m≥0
a n,m z n Just to prove the Lemma 4, we need to establish three conditions (i)-(iii) of Lemma 22. We accomplish it through a generalization of the so called increasing domain approach discussed in [START_REF] Jacquet | Analytical DePoissonization and Its Applications[END_REF][START_REF] Szpankowski | Analysis of Algorithms on Sequences[END_REF].

We first prove the lemma for the generating functions C a (z 1 , z 2 ) for every a ∈ A. Assume now that ρ = max (a,b)∈A 2 ,i∈{1,2} {P i (a|b)}. We denote by S k part of the cone S θ that contains points such that |z| < ρ -k . Notice that S k ⊂ S k+1 for all integer k. We also notice C(z 1 , z

B k+1 ≤ B k + β max (z1,z2)∈S k+1 ×S k+1 -S k ×S k { 1 |z 1 | + |z 2 | } = B k + βρ k . ( 115
)
We should notice that min

Figure 2 :

 2 Figure 2: Average theoretical joint complexity of 3rd Markov order text of English, vs French (top), and vs Polish (bottom) languages, versus order estimate O(n κ ). The x-axis is the length of the text, while the y-axis shows the joint complexity.

Figure 3 :

 3 Figure 3: Joint complexity: three simulated trajectories (black) versus asymptotic average (dashed red) for the case c 2 > 0.

  ,b ζ a (s)u b (s)P (a|b) -s (-log P (a|b)), λ ′′ (s) = ζ(s)|P ′′ (s)u(s) = a,b ζ a (s)u b (s)P (a|b) -s (log P (a|b)) 2 . (72) Finally, to compute some of the constants in Theorems 4 -5, we need to computer L ′′ (s). To do so, let x a,b = 1 λ(s) ζ a (s)u b (s)P (a|b) -s . Clearly, by Lemma 12 we have a,b x a,b = 1 and

Proof. Let s 2 = c 2 +

 22 it 2 . By the Perron-Frobenius, we have |λ(s 2 )| ≤ λ(c 2 ) since ℜ(s 2 ) = c 2 and |P(s 2 )| = P(c 2 ) (by taking the modulus element-wise). If |λ(s 2 )| = λ(c 2 )

Proof.

  It turns out that lim k |λ(c 1 , s k )| = |A| c1 λ(c 2 ) = 1. There exists x k such that ℜ(x k ) = c 1 and λ(x k , s k ) = |λ(c 1 , s k )|. Hence Lemma 10 applies. Thus for any complex number s ∀j : lim k→∞ λ j (s k + s) λ(s k + s) = lim k→∞ λ j (x k , s k + s) λ(x k , s k + s)

Notice that b 2

 2 (s) = β 2 (-L(s), s) mentioned in Theorem 8. Since the function log f (s)g(s) λ(s) Γ(-L(s))Γ(s)has bounded variations, we have the classic saddle point result[START_REF] Flajolet | Analytic Combinatorics[END_REF][START_REF] Szpankowski | Analysis of Algorithms on Sequences[END_REF]

1 and P 2

 2 which are not tied up by the conjugation property (because their alter ego coefficients in the other matrix are null). This implies that we have to consider a new matrix G(z) whose coefficients g a,b (z) for (a, b) ∈ A 2 are g a,b (z) = C a (π 1 (b)z, π 2 (b)z).

  π 1 (a)z, π 2 (a)z), and then we can rewrite equation (104) forz 1 = z 2 = z as C(z, z) = (1 -e -z ) 2 + trace(G(z)).We then compute the Mellin transform G * (s) of G(z), which is a matrix of elements g * a,b (s) (i.e., Mellin transforms of g a,b (z)) that are equal tog * a,b (s) = r a (s)Γ(s) + c∈A g * c,b (s)P (a|c) -s .Herer a (s) = -π 1 (a) -s -π 2 (a) -s + (π 1 (a) + π 2 (a)) -sis the Mellin transform of the term (1 -e -π1(b)z )(1 -e -π2(b)z ) in (105). EquivalentlyG * (s) = Γ(s)r(s) ⊗ 1 + P(s, 0)G * (s)(106)or G(s) = (I-P (s, 0)) -1 Γ(s)r(s)⊗ 1 where r(s) is the vector made of the r a (s)'s. The Mellin transform of C(z, z) which we denote as c * (s) satisfies c * (s) = (2 -s -2)Γ(s) + trace(G * (s)).

.

  Let now S θ be a cone of angle θ around the real axis. Assume that there exist B > 0, D > 0, α < 1 andβ such that for |z 1 |, |z 2 | → ∞: (i) if z 1 , z 2 ∈ S θ then |f (z 1 , z 2 )| = B(|z 1 | β + |z 2 | β ); (ii) if z 1 , z 2 / ∈ S θ then |f (z 1 , z 2 )e z1+z2 | = De α|z1|+α|z2| ; (iii) if z i ∈ S θ and z j / ∈ S θ for {i, j} = {1, 2} and |f (z 1 , z 2 )e zj | < D|z i | β e α|zj| .Thena n,m = f (n, m) + O n β m + m β nfor large m and n.

  2 ) = O((|z 1 | + |z 2 |)2 ) when z 1 , z 2 → 0, therefore we can defineB k = max a∈A,(z1,z2)∈S k ×S k |C a (z 1 , z 2 )| |z 1 | + |z 2 | < ∞ .We use the functional equationC b (z 1 , z 2 ) = (1 -(1 + z 1 )e -z1 )(1 -(1 + z 2 )e -z2 ) + a∈A C a (P 1 (a|b)z 1 , P 2 (a|b)z 2 ) .(113)In the above equation, we notice that if (z 1 , z 2 ) ∈ S k+1 × S k+1 -S k × S k , then for all (a, b) ∈ A 2 (P 1 (a|b)z 1 , P 2 (a|b)z 2 ) are in S k × S k and therefore we have for some fixed β > 0 and for all b ∈ A:|C b (z 1 , z 2 )| ≤ B k ( a∈A P 1 (a|b)|z 1 | + P 2 (a|b)|z 2 |) + β = B k (|z 1 | + |z 2 |) + β (114) since |1 -(1 + z i )e -zi| is uniformly bounded for all integers k by some √ β for both i ∈ {1, 2} when (z 1 , z 2 ) ∈ S k . Thus, we can derive the following recurrent inequality:

(. Then b =c m cb u b e iθ cb x b x c < b =c m cb u b . ( 124 )

 124 z1,z2)∈S k+1 ×S k+1 -S k ×S k {|z 1 | + |z 2 |} = ρ -k (116)because one of the number z i has modulus greater than ρ -k . It turns out that lim k→∞ B k < ∞, establishing condition (i) of the double depoissonization Lemma 22. Now we are going to establish condition (iii). To this end we define G as the complementary cone of S θ and G k as the portion made of the point of modulus smaller than ρ -k . We will use cos θ < α < 1, therefore ∀z ∈ G: |e z | < e α|z| . We define D k asD k = max a∈A,(z1,z2)∈G k ×G k |C a (z 1 , z 2 )e z1+z2 | exp(α|z 1 | + α|z 2 |) . (117)We define G a (z 1 , z 2 ) = C a (z 1 , z 2 )e z1+z2 , we have the following equationG b (z 1 , z 2 ) = (e z1 -1 -z 1 )(e z2 -1 -z 2 ) + a∈A C a (P 1 (a|b)z 1 , P 2 (a|b)z 2 ) e 1-P1(a|b)z1+(1-P2(a|b))z2 . (118) We notice that if (z 1 , z 2 ) ∈ G k+1 × G k+1 -G k × G k , then all (P 1 (a|b)z 1 , P 2 (a|b)z 2 ) are in G k × G k and therefore we have for all b ∈ A: |G b (z 1 , z 2 )| ≤ D k a∈A exp ((P 1 (a|b)α + (1 -P 1 (a|b)) cos θ)|z 1 | + (P 2 (a|b)α + (1 -P 2 (a|b)) cos θ)|z 2 |) +(e cos θ|z1| + 1 + |z 1 |)(e cos θ|z2| + 1 + |z 2 |).We notice that ∀(a, b) ∈ A 2 and ∀i ∈ {1, 2}:P i (a|b)α + (1 -P i (a|b)) cos θ -α ≤ -(1 -ρ)(α -cos θ) ,(119)We also have e cos θ|zi| + 1+ |z i | ≤ e cos θ|zi| (2 + 1 e cos θ ), therefore |G b (z 1 , z 2 )| exp(α(|z 1 | + |z 2 |)) ≤ D k |A|e -(1-ρ)(α-cos θ)(|z1|+|z2|) + (2 + 1 e cos θ ) 2 e -(α-cos θ)(|z1|+|z2|) . (120) Since (z 1 , z 2 ) ∈ G k+1 × G k+1 -G k × G k implies |z 1 | + |z 2 | ≥ ρ -k it follows D k+1 ≤ max D k , |A|D k e -(1-ρ)(α-cos θ)ρ -k + (2 + 1 e cos θ ) 2 e -(α-cos θ)ρ -k .(121)We clearly have lim k→∞ D k < ∞ and condition (iii) is established. The proof of condition (ii) for z 1 and z 2 being in S θ and G is a mixture of the above proofs. Furthermore, the proof about the unconditional generating function C(z 1 , z 2 ) is a trivial extension.Proof of Lemma 5. Let u = (u a ) a∈A be the right eigenvector of M and (v a ) a∈A be the right eigenvector of Q. Let also v a = x a u a . If 1 is the eigenvalue, we have for all c ∈ A:(1 -e iθcc m cc )u c = b =c m cb u b e iθ cb x b x c . (122) If e iθcc = 1, then |(1 -e iθcc m cc )u c | > (1 -m cc )u c .(123)By the Perron-Frobenius theorem all u a are real non negative. Suppose that |x c | = max a∈A {|x a |}. If ∃d ∈ A: |x d | |xc| < 1 or if (b, b ′ ) ∈ (A -{c}) 2 : e iθ cb x b xc = e iθ cb ′ x ′ b xc But we also know that (1 -m cc )u c = b =c m cb u b . (125) Therefore, we have e iθcc = 1 and for all b ∈ A: |x b | = |x c |, and for all (b, b ′ ) ∈ (A -{c}) 2 : e iθ cb x b xc = e iθ cb ′ x ′ b xc . But since for all b ∈ A |x b | = |x c | every symbol in A can play the role of c. Since for all c ∈ A (1 -m cc ) = b =c m cb u b e iθ cb x b x c = b =c m cb u b , (126) we simply have ∀(a, b) ∈ A: e iθ ab x b xa = 1. Denoting x a = e iθa we prove the expected result. The converse proposition is immediate.

This work was partially supported by LINCS. Paris as well as the NSF Center for Science of Information (CSoI) Grant CCF-0939370, and in addition by NSF Grants CCF-1524312, CCF-2006440, and CCF-2007238.

We recall that a double periodic function is a function on real numbers that is a sum of two periodic functions of non commensurable periods.

A conjugate matrix is a matrix obtained from a given matrix by taking the complex conjugate of each element of it.

+ 1 C |(I -P(0, 0)) -1 1 exponentially fast, because any word w ∈ W may be prefix to none of n independent strings with a probability decaying exponentially fast to 0.

recall that a pair of numbers (α, β) is commensurable if there exists a real number ν such that the vector (να, νβ) ∈ Z 2 ; otherwise the pair is incommensurable.

Remark Remember that when all coefficients of P 2 are non-negative P(-1, 0) = P 1 which is not necessarily the case when P 2 has some null coefficients.

Proof of Theorems 8 and 9. We need the following lemma which is basically equivalent of Lemmas 17 and 18 developed in the special case.

Lemma 21. There exists ǫ > 0 such that for all integers j > 1 and for all integers k the quantities ℜ(s)=c2 f j,k (s)g j,k (s)Γ(-L j,k (s))Γ(s)

-∂ ∂s1 λ j (-L j,k (s), s) z L j,k (s)-s ds (112)

are uniformly O(z κ-ǫ ).

Proof. The proof consists of showing that there exist ǫ > 0 such that if

) is strictly increasing in ℜ(s 1 ) and ℜ(s 2 ). Second we prove the existence of ǫ. By absurdum we assume that there is a sequence of complex numbers (x k , y k ) such that λ j (x k , y k ) = 1 and

. This would imply that

which contradicts Lemma 10.

The above lemma fills the gap necessary to establish of Theorems 8 and 9 by following the footsteps of the proofs of Theorems 4 and 5.

Appendix

Proof of Lemma 2. Let ∀(a, b) ∈ A 2 P 1 (a|b) > 0. Thus (0, -1) ∈ K, but since some P 2 (a|b) may be zero, the point (-1, 0) may not be

We know that the curve (-s 1 , -s 2 ) is convex for (s 1 , s 2 ) ∈ K, so is the curve (s 1 , -s 1 -s 2 ), then -s 1 -s 2 is a function of s 1 , say a(s 1 ). We have a(0) = 1 and a(-1) ≤ 1. Thus the minimum value of a(s 1 ) which is κ is attained on c 1 which must satisfies c 1 ≤ 0 We then have c 1 < 0 when the curve is strictly convex.

Similarly, the curve (s 2 , -s 1 -s 2 ) is convex, so is the function b(s 2 ) = -s 1 -s 2 . Since b(-1) = 1 and b(0) ≤ 1 the minimum is necessarily attained on c 2 ≥ -1, and c 2 > -1 when it is strictly convex.

Proof of Lemmas 1 and 7. We call K the set of real tuples such that λ(s 1 , s 2 ) ≤ 1. The set K is the topological border of K and since λ(s 1 , s 2 ) decreases when s 1 or s 2 decrease, it is the upper border. We will show that K is a convex set and thus its upper border is concave. Let (x 1 , x 2 ) and (y 1 , y 2 ) be two elements of K and α and β two non negative real numbers such that α + β = 1. We want to prove that (αx 1 + βy 1 , αx 2 + βy 2 ) ∈ K.

By construction P(αx 1 + βy 1 , αx 2 + βy 2 ) = P(αx 1 , αx 2 ) ⋆ P(βy 1 , βy 2 )

where ⋆ denotes the Schur product. For (s 1 , s 2 ) ∈ K let u(s 1 , s 2 ) the right main eigenvector of P(s 1 , s 2 ), i.e.

We know that λ(s 1 , s 2 ) ≤ 1 therefore

coefficientwise. Let u(s 1 , s 2 ) ⋆α denotes the vector u(s 1 , s 2 ) with all its coefficients raised to power α.

We want to give an estimate of P(αx 1 , αx 2 ) ⋆ P(βy 1 , βy 2 ) applied to the vector u(x 1 , x 2 ) ⋆α ⋆ u(y 1 , y 2 ) ⋆β .

Let a ∈ A the coefficient of the vector

Using Hölder inequality, the above quantity is smaller than

The above terms are respectively λ(x 1 , x 2 )u a (x 1 , x 2 ) and λ(y 1 , y 2 )u a (y 1 , y 2 ). Therefore the vector

Since λ α (x 1 , x 2 )λ( β (y 1 , y 2 ) ≤ 1 by Perron-Frobenius the main eigenvalue of P(αx 1 + βy 1 , αx 2 + βy 2 ) is smaller than or equal to 1, consequently (αx 1 + βy 1 , αx 2 + βy 2 ) ∈ K. The Hölder inequality is an equality if and only if the vectors (u a (x 1 , x 2 )P(x 1 , x 2 )) a∈A and (u a (y 1 , y 2 )P(y 1 , y 2 )) a∈A are colinear, which happens when P(x 1 , x 2 ) and P(y 1 , y 2 ) are conjugate, which is equivalent to the fact that P 1 and P 2 are conjugate (on the coefficients which are non zero).

Proof of Lemma 10. Consider the matrix 1 λ(x k ,y k ) P(x k , y k ). Since the coefficients of this matrix are bounded, there is no loss in generality to consider the sequence of matrices converging to a matrix M. The matrix M and matrix Q = P(c 1 , c 2 ), as defined in Lemma 5, are imaginary conjugate i.e. the coefficients of M are of the form e i(θa-θ b ) P 1 (a|b) -c1 P 2 (a|b) -c2

(128)

for some vector of real numbers θ a . Therefore, M and P(c 1 , c 2 ) have the same spectrum. The spectrum of 1 λ(x k ,y k ) P(x k , y k ) converges to the spectrum of M. Furthermore, the right eigenvector u(x k , y k ) converges to the vector e iθa u a (c 1 , c 2 ) and the left eigenvector ζ(x k , y k ) converges to e -iθa ζ a (c 1 , c 2 ).

For any pair of complex numbers (s 1 , s 2 ) we have the identity

Thus 1 λ(x k ,y k ) P(x k +s 1 , y k +s 2 ) converges to M * P(s 1 , s 2 ) and is conjugate to P(c 1 +s 1 , c 2 +s 2 ). Since the eigen spectrum of 1 λ(x k ,y k ) P(x k + s 1 , y k + s 2 ) converges to the eigen spectrum of P(c 1 + s 1 , c 2 + s 2 ), thus we have λ(x k + s 1 , y k + s 2 ) → λ(c 1 + s 1 , c 2 + s 2 ). We also have |λ(x k + s 1 , y k + s 2 )| > |λ 2 (x k + s 1 , y k + s 2 )| when k is large enough with (s 1 , s 2 ) in the complex neighborhood U 2 which implies the analyticity of λ(x k + s 1 , y k + s 2 ). Thus by Ascoli theorem the derivatives converge, too.