Philippe Jacquet
email: philippe.jacquet@inria.frspa@cs.purdue.edu

Wojciech Szpankowski

Distribution of Tail Symbols in DST for Markov Sources

Lempel-Ziv'78 is one of the most popular data compression algorithm on words. Over the last decades we uncover its fascinating behavior and understand better many of its beautiful properties. Among others, in 1995 by settling the Ziv conjecture we proved that for memoryless source (i.e., when a sequence is generated by a source without memory) the number of LZ'78 phrases satisfies the Central Limit Theorem (CLT). Since then the quest commenced to extend it to Markov sources, however, despite several attempts this problem is still open.

In this conference paper, we revisit the issue and focus on a much simpler, but not trivial problem that may lead to the resolution of the LZ'78 dilemma. We consider the associated Digital Search Tree (DST) version of the problem in which the DST is built over a fixed number of Markov generated sequences. In such a model we shall count the number of of the so called "tail symbol", that is, the symbol that follows the last inserted symbol. Our goal here is to analyze this new quantity under Markovian assumption since it plays crucial role in the analysis of the original LZ'78 problem. We establish the mean, the variance, and the central limit theorem for the number of tail symbols. We accomplish it by applying techniques of analytic combinatorics on words also known as analytic pattern matching.

Introduction

The Lempel-Ziv compression algorithm [START_REF] Ziv | Compression of individual sequences via variable-rate coding[END_REF] is a universal compression scheme. It partitions the text to be compressed into consecutive phrases such that the next phrase is the unique shortest prefix of the uncompressed text not seen before in the compressed portion of the text. For example, 11001010001000100 . . . is parsed into phrases ()(1)(10)(0)(101) . . .. The LZ'78 compression code for a word w over the alphabet A that we denote as C(w) consists of a pointer to the previous phrase and the last symbol of the current phrase. It is well known that the average compression rate |C(w)|/|w| tends to the source entropy rate h when |w| → ∞, however, one is often more interested in the called called (normalized) redundancy rate |C(w)| |w| -h, that is, the excess of the code length over the optimal code length represented by the entropy of the source. Its behavior is known now for memoryless sources [START_REF] Aldous | A Diffusion Limit for a Class of Random-Growing Binary Trees[END_REF][START_REF] Jacquet | Asymptotic behavior of the Lempel-Ziv parsing scheme and digital search trees[END_REF][START_REF] Jacquet | On the Limiting Distribution of Lempel Ziv'78 Redundancy for Memoryless Sources[END_REF] but the last fifty years failed to produce any significant progress for Markov sources.

It is convenient to organize the phrases (dictionary) of the Lempel-Ziv scheme in a digital search tree (DST) [START_REF] Knuth | The Art of Computer Programming[END_REF][START_REF] Szpankowski | Average Case Analysis of Algorithms on Sequences[END_REF] which represents a parsing tree. The root then contains an empty phrase. The first phrase is the first symbol, say "a ∈ A" which is stored in a node appended to the root. The next phrase is either "aa ∈ A 2 " stored in another node that branches out from the node containing the first phrase "a" or a new symbol that is stored in a node attached to the root. This process repeats recursively until the text is parsed into full phrases. A detailed description can be found in [START_REF] Cover | Elements of Information Theory[END_REF][START_REF] Jacquet | Asymptotic behavior of the Lempel-Ziv parsing scheme and digital search trees[END_REF][START_REF] Jacquet | Analytic Pattern Matching: From DNA to Twitter[END_REF][START_REF] Szpankowski | Average Case Analysis of Algorithms on Sequences[END_REF]; see also Fig. 1.

Figure 1: A digital tree representation of the Lempel-Ziv parsing for the string 11001010001000100 . . . into phrases ()(1)(10)(0)(101) . . . where () is the empty phrase stored in the root .

Let a text w be generated over an alphabet A, and let T (w) be the associated digital search tree constructed by the algorithm. Each node in T (w) corresponds to a phrase in the parsing algorithm. Let L(w) be the (total) path length in T (w), that is, the sum of all paths from the root to all nodes (i.e., the sum of phrases which is also the text length). We have L(w) = |w| (if all phrases are full). We also note that the compression code C(w) is a description of T (w), node by node in the order of creation. The compressed code length is then |C(w)| = M (w) k=1 ⌈log 2 (k)⌉ + ⌈log 2 (|A|)⌉ where M (w) is the number of full phrases needed to phrases w, and the pointer to the kth node requires at most ⌈log 2 k⌉ bits, while and the next symbol costs ⌈log 2 |A|⌉ bits. To simplify, we shall assume throughout that |C(w)| = M (w) (log(M (w)) + log(|A|)).

To understand LZ'78 behavior one must analyze the limiting distribution of M (w) and/or L(w). Indeed, let |w| = n and denote L n := L(w) and M n = M (w). It is is well known that P (M n > m) = P (L m < n) linking the number of phrases M n to the path length L n in the associated DST. For memoryless sources, this relation and the so called renewal equation are sufficient to analyze the limiting distribution of M n since one starts with a digital search tree built from m independently generated strings [START_REF] Jacquet | Asymptotic behavior of the Lempel-Ziv parsing scheme and digital search trees[END_REF][START_REF] Jacquet | On the Limiting Distribution of Lempel Ziv'78 Redundancy for Memoryless Sources[END_REF]. However, this approach fail when the original sequence w is generated by a Markov source since the phrases carved by the LZ'78 algorithm are strongly correlated thought a forward and backward dependence. In this case we need to understand the behavior of the number of phrases that start with a symbol a and end with a symbol b. This is the main challenge one encounters when analyzing LZ'78 under Markovian assumption.

In this conference paper we propose a first step towards resolving the dependence problem between phrases. We consider only a digital search tree built from Markov sequences over a binary alphabet A = {a, b}. We study here the asymptotic behavior of the following quantity. We consider n independent sequences generated by a Markov source with transition probability P. When a sequence is inserted into the DST, we call the "tail symbol" the symbol that follows the last symbol inserted in the DST. For example, in Figure 1 the tail symbol after phrase [START_REF] Jacquet | Analytic Pattern Matching: From DNA to Twitter[END_REF] is "0".

Let now c ∈ A be an arbitrary symbol from the alphabet, that is, it is either an "a" or a "b". We denote T n = (T a n , T b n ) the random variable vector representing the number of times the symbol a appears as a tail symbol after the insertion of the n sequences assuming that all sequences start with symbol a ∈ A for T a n or symbol b representing T b n . For example, in Figure 1 we have T (0) 8 = 5. Notice that we have a stochastic recursion

T c n+1 = δ a + T a na + T b n b (1)
where δ a is equal to 1 when the second symbol of the first sequence is a and is equal to 0 otherwise. The quantity n c is the number of sequences inserted after the first sequence such that their second symbol is equal to c (thus they fork to the subtree corresponding to c in the DST). Our goal in this paper is to analyze probabilistic behavior of T n ; in particular, its mean and variance, and its limiting distribution. In the Concluding remarks of this paper we show how analysis of T n can lead to a characterization of LZ'78 algorithm.

Let us now briefly review literature on LZ'78 and DST analysis. Our ultimate goal is to prove the Central Limit Theorem (CLT) for the number of phrases and establish precise rate of decay of the LZ'78 code redundancy for Markov sources. For memoryless sources, this result was already proved in our 1995 paper [START_REF] Jacquet | Asymptotic behavior of the Lempel-Ziv parsing scheme and digital search trees[END_REF] while the average redundancy was presented in [START_REF] Louchard | On the average redundancy rate of the Lempel-Ziv code[END_REF][START_REF] Savari | Redundancy of the Lempel-Ziv Incremental Parsing Rule[END_REF], It should be pointed out that since our 1995 paper [START_REF] Jacquet | Asymptotic behavior of the Lempel-Ziv parsing scheme and digital search trees[END_REF] no simpler, in fact, no new proof of CLT was presented except the one by Neininger and Rüschendorf [START_REF] Neininger | A General Limit Theorem for Recursive Algorithms and Combinatorial Structures[END_REF] but only for unbiased memoryless sources (as in [START_REF] Aldous | A Diffusion Limit for a Class of Random-Growing Binary Trees[END_REF]). The proof of [START_REF] Neininger | A General Limit Theorem for Recursive Algorithms and Combinatorial Structures[END_REF] applies the so called contraction method. The only known to us analysis of LZ'78 for Markov sources is presented in [START_REF] Jacquet | Average Profile of the Lempel-Ziv Parsing Scheme for a Markovian Source[END_REF], but the authors restricted their attention to a single phrase. An attempt to analyze of the LZ'78 for Markov sources was reported in [START_REF] Leckey | Probabilistic Analysis of Lempel-Ziv Parsing for Markov Sources[END_REF].

Regarding analysis of digital search trees, and in general digital trees, more is known. The reader is refer to our book [START_REF] Jacquet | Analytic Pattern Matching: From DNA to Twitter[END_REF] for details. Digital trees for memoryless sources were analyzed in [START_REF] Aldous | A Diffusion Limit for a Class of Random-Growing Binary Trees[END_REF][START_REF] Fayolle | Analysis of the average depth in a suffix tree under a Markov model[END_REF][START_REF] Louchard | On the average redundancy rate of the Lempel-Ziv code[END_REF][START_REF] Szpankowski | Average Case Analysis of Algorithms on Sequences[END_REF]. Digital trees under Markovian models were analyzed in [START_REF] Jacquet | Analysis of digital tries with Markovian dependency[END_REF][START_REF] Jacquet | Average Profile of the Lempel-Ziv Parsing Scheme for a Markovian Source[END_REF][START_REF] Leckey | Towards More Realistic Probabilistic Models for Data Structures: The External Path Length in Tries under the Markov Model[END_REF].

Main Results

In this section we present our main results delaying most of the proofs till the last section. We consider a stationary source generating a sequence of symbols drawn from a finite alphabet A. We assume that the source is stationary and ergodic. We will consider a Markovian process of order 1 with the transition matrix P = [P (a|b)] a,b∈A . For this conference paper we assume that P (a|b) > 0 for all a, bA. Extensions to finite alphabet and higher order Markov is possible since a Markovian source of order r is simply a Markovian source of order 1 over the alphabet A r .

In this section we shall analyze T c n representing the number of times the symbol a appears as a tail symbol after the insertion of the n sequences assuming that all sequences are generated by a Markov source with transition probability P and all sequences start with symbol c ∈ A. We have already observed that the vector T c satisfies the stochastic equation [START_REF] Aldous | A Diffusion Limit for a Class of Random-Growing Binary Trees[END_REF]. We will translate it now into the generating function world.

For

c ∈ A let D c n,k = P (T c n = k) and D c n (u) = E[u T c
n ] be the probability generating function of T c n defined for a complex variable u. We have the recursion:

D c n+1 (u) = (P (a|c)u + 1 -P (a|c)) + k n k P (a|c) k P (b|c) n-k D a k (u)D b n-k (u) (2) subject to (i) D c 0 (u) = 1 and (ii) D c 1 (u) = P (a|c)u+1-P (a|c). Furthermore, define the bivariate Poisson transform D c (z, u) = n≥0 E[u T c n ] z n n! e -z
be the Poisson transform of T c n . It satisfies the following differential-functional equation

∂ z D c (z, u) + D c (z, u) = D c 1 (u)D a (P (a|c)z, u)) • D b (P (b|c)z, u) (3)
with D c (z, 1) = 1 where ∂ z is the partial derivative with respect to variable z. We also sometimes write

f z (z, u) := ∂ z f (z, u).
We now focus on the first Poisson moment X c (z) = ∂ u D c (z, 1) where ∂ u is the derivative with respect to variable u. We also study the Poisson variance

V c (z) = ∂ 2 u D c (z, 1) + X c (z) -(X c (z)) 2
, and the limiting distribution of T c n . After finding asymptotic behavior of the Poisson mean X c (z) and variance V c (z) for large z → ∞ we invoke the depoissonization lemma of [START_REF] Jacquet | Analytical depoissonization and its applications[END_REF] to extract the original mean and variance:

E[T c n ] = X c (n) - 1 2 nX c z (n) + • • • , Var[T c n ] = V c (n) -n[X z (n)] 2 z + • • • .
Let us start with the Poisson mean X c (z). Taking the derivative of (3) with respect to u and setting u = 1 we find

∂ z X c (z) + X c (z) = P (a|c) + X a (P (a|c)z) + X b (P (b|c)z). ( 4
)
To complete this equation we need to calculate the initial values of

E[T c n ]. It is easy to see that E[T c 0 ] = 0, E[T c 1 ] = P (a|c), E[T c
2 ] = P (a|c) + P (a|c)P (a|a) + P (b|c)P (a|b).

(

) 5
In a similar fashion we can derive the differential-functional equation for the Poisson variance. After some tedious algebra we arrive at

∂ z V c (z) + V c (z) = P (a|c) -P 2 (a|c) + [∂ z X c (z)] 2 + V a (P (a|c)z) + V b (P (b|c)z). ( 6
)
Both differential-functional system of equations ( 3) and ( 5) can be solved using complicated Mellin transform approach. We will provide details of our approach in the next section. For now we need to introduce some extra notation to present our main results.

For complex s define P(s) = P (a|a) -s P (b|a) -s P (a|b) -s P (b|b) -s .

For such P(s) we denote by λ(s) the main eigenvalue. We also need another matrix

Q(s) = i≥1 (I -P(s -i)) -1 j=-2 j=-∞ (I -P(j))
which is well defined for ℜ(s) ∈ (-2, 0). We also define x, y as the scalar product of vectors x and y. Now we are in the position to formulate our main result.

Theorem 1 Consider a digital search tree (DST) built over n independent sequences generated by a Markov source. For (a, b, c) ∈ A 3 define

α abc = log P (a|b)P (c|a) P (c|b) . ( 8
) (i) [Aperiodic case] If not all {α abc } are rational, then E[T a n ] = n π a + 1 λ ′ (-1) 1 π ′ (-1) + πQ ′ (-1) (I -P)Pe a 1 + o(n). (9)
[Periodic case] If all {α abc } are rationally related, then for some ε > 0

E[T a n ] = n π a + 1 λ ′ (-1) 1 π ′ (-1) + πQ ′ (-1) (I -P)Pe a + Q 1 a (n) 1 + O(n -1+ε ) (10)
where

Q 1 a (n) is a periodic function. (ii) [Variance] The variance Var[T a n ] grows linearly, that is Var[T a n ] = Θ(n) for a ∈ A. More precisely, Var[T a n ] = n(ω a + Q 2 a (n)) + o(n)
where ω a is given explicitly in (28) of Theorem 2 (see Section 3.2), and Q 2 a (n) is a nonzero periodic function for rationally related case, and zero otherwise. (iii) [Central Limit Theorem] For any c ∈ A we have

T c n -E[T c n ] Var[T c n ] → N (0, 1)
where N (0, 1) denotes the standard normal distribution.

We notice that, unexpectedly, the number of tail symbols equal to a is not converging to nπ a as we should expect from a Markovian sequence converging to its stationary state when the length of the sequence increase. It departs from the stationary distribution by the term

1 λ ′ (-1) (π ′ (-1) + πQ ′ (-1)) (I -P)Pe a .
The reason is that the tail symbol is picked up at random in the sequence but occurs when the sequence path leaves the tree and this introduce a non trivial bias.

Proofs

In this section we prove separately Theorem 1(i), then Theorem 1(ii), and finally Theorem 1(iii).

Proof of Theorem 1(i): Mean

We first analyze asymptotically X(z) = (X a (z), X b (z)) that satisfies the system of differentialfunctional equations (4). We solve this system, and then apply Mellin transform and depoissonization to prove Theorem 1(i).

Since for all integer n, we have T c n ≤ n, we notice that the function X c (z) is O(z) both when z → ∞ and when z → 0. Thus the function X(z) has no Mellin transform. To correct this we introduce Xc

(z) = X c (z) -G c (z) with G c (z) = (E[T c 1 ]z + E[T c 2 ]z 2 /2)e -z which is O(z 3 ) when z → 0, where E[T c
1 ] and E[T c 1 ] are defined in [START_REF] Jacquet | Analysis of digital tries with Markovian dependency[END_REF]. The Mellin transform X * c (s) of Xc (z) on the strip ℜ(s) ∈] -3, -1[ exists. The Mellin transform of ∂ z Xc (z) exists too on the strip ℜ(s) ∈] -2, 0[. Thus the two Mellin transforms coexist on the strip ℜ(s) ∈] -2, -1[ and satisfies [START_REF] Szpankowski | Average Case Analysis of Algorithms on Sequences[END_REF]

-(s -1)(X * c (s -1) + G * c (s)) + X * c (s) + G * c (s) = P (a|c) -s (X * a (s) + G * a (s)) + P (b|c) -s (X * b (s) + G * b (s))
where G * c (s) for c ∈ A is the Mellin transform of G c (z) and has the explicit expression

E[T c 1 ]Γ(1+ s) + E[T c
2 ]Γ(s + 2)/2. This expression is here for completeness. An alternative but convenient way to see this equations is to consider the vector X * (s) made of the quantities X * c (s), which is also the Mellin transform of the vector X(z) made of the coefficients Xc (z). This yields the linear equation

-(s -1)(X * (s -1) + G * (s -1)) + X * (s) + G * (s) = P(s)(X * (s) + G * (s)) (11)
where G * (s) is the vector of the G * c (s). It can be rewritten in

(s -1)(X * (s -1) + G * (s -1)) = (I -P(s))(X * (s) + G * (s)).
This kind of equation has been studied in [START_REF] Jacquet | Average Profile of the Lempel-Ziv Parsing Scheme for a Markovian Source[END_REF] where we introduce a new function x(s) defined as

X * (s) + G * (s) = Γ(s)x(s)
for some function x(s). Thus the equation becomes x(s -1) = (I -P(s))x(s), which leads to

x(s) = i≥0 (I -P(s -i)) -1 K
where K is a constant vector. Notice that the matrices very likely don't commute thus the product order is specified from the left to right. Indeed we have

K =   j≥2 (I -P(-j)) -1   -1 x(-2) = j=2 j=-∞ (I -P(j))x(-2). (12)
To handle it we need an explicit formula for x(-2). The following lemma from [START_REF] Jacquet | Average Profile of the Lempel-Ziv Parsing Scheme for a Markovian Source[END_REF] is useful in this regard. We provide a proof for completeness.

Lemma 1 Let {f n } ∞
n=0 be a sequence of real numbers having the Poisson transform

F (z) = ∞ n=0 fn z n n! e -z := ∞ n=0 f n z n n! , (13)
which is an entire function. Furthermore, let its Mellin transform F (s) have the following factorization

F (s) = M[ F (z); s] = Γ(s)γ(s).
Assume that F (s) exists for ℜ(s) ∈ (-2, -1), and that γ(s) is analytic for ℜ(s) ∈ (-∞, -1). Then

γ(-n) = n k=0 n k (-1) k fk = (-1) n f n , for n ≥ 2. ( 14
)
Proof. Notice that f n and fn are related by [START_REF] Szpankowski | Average Case Analysis of Algorithms on Sequences[END_REF] fn

= n k=0 n k (-1) n-k f k , n ≥ 0 .
Define for some fixed M ≥ 2, the function

F M (z) = M -1 n=0 f n z n
n! . Due to our assumptions, we can continue F (s) analytically to the whole complex plane except s = -2, -3, . . . . In particular, for ℜ(s) ∈ (-M, -M + 1) we have

F (s) = M[ F (z) -F M (z); s].
As s → -M , due to the factorization F (s) = Γ(s)γ(s), we have

F (s) = 1 s + M (-1) M M ! γ(-M ) + O(1) ;
thus by the inverse Mellin transform, we have

F (z) -F M (z) = (-1) M M ! γ(-M )z M + O(z M +1 ) as z → 0 . (15)
But

F (z) -F M (z) = ∞ i=M f n z n n! = f M z M M ! + O(z M +1 ) . (16)
Comparing ( 15) and [START_REF] Savari | Redundancy of the Lempel-Ziv Incremental Parsing Rule[END_REF] shows that γ(-M ) = (-1)

M f M = M k=0 M k (-1) k fk for M ≥ 2.
Now we can compute x(-2) using above and (5) leading to

x(-2) = T a 2 -2P (a|a) T b 2 -2P (a|b) . (17)
In another notation x(-2) = (P 2 -P)e a ,

where e a is the vector made of a single 1 at a position and zero otherwise.

Next, we notice that the vector Γ(s)

i≥0 (I -P(s -i)) -1 j=-2 j=-∞ (I -P(j))x(-2)
may have a double pole on s = -1 since Γ(s) has a pole and also (I -P(s)) -1 since I -P(-1) = I -P is singular. But in fact the pole multiplicity is reduced by one, as prove below. Let us also define

Q(s) = i≥1 (I -P(s -i)) -1 j=-2 j=-∞ (I -P(j)). Then x(s) = (I -P(s)) -1 Q(s)x(-2).
We notice that when s → -1, then Q(s) = I + (s + 1)Q ′ (-1) + O((s + 1) 2 ). Furthermore let λ(s) be the main eigenvalue of matrix P(s) and 1(s) and π(s) be respectively the right and left main eigenvectors. We have λ(-1) = 1, 1(-1) is all made of one's, and π(-1) is the stationary distribution of the Markov source.

From the matrix spectral representation [START_REF] Szpankowski | Average Case Analysis of Algorithms on Sequences[END_REF] we have

P(s) = λ(s)1(s) ⊗ π(s) + R(s) = λ(s)Π(s) + R(s) (19)
where R(s) is the automorphism of the eigenplan orthogonal to the main eigenvector and Π(s) = 1(s) ⊗ π(s). Note that

Π • P = P • Π = Π. And (I -P(s)) -1 = 1 1 -λ(s) 1(-s) ⊗ π(s) - 1 λ ′ (-1) 1 ′ (-1) ⊗ π(-1) + 1 ⊗ π ′ (-1) + R(-1) -1 + O(s + 1). Finally (I -P(s)) -1 Q(s)x(-2) = 1 ⊗ π(s)(I -P)e a 1 -λ(s) - 1 λ ′ (-1) 1 ′ (-1) ⊗ π + 1 ⊗ π ′ (-1) +R -1 (-1) + (s + 1) 1 -λ(s) 1 ⊗ Q ′ (-1) + O(s + 1). Since s + 1 1 -λ(s) → - 1 λ ′ (-1)
when s → -1, and ΠP(I -P)e a = (Π -Π)e a = 0. Also R -1 (-1)(I -P)Pe a = Pe a -πPe a 1 = Pe aπe a 1.

We finally have lim s→-1

x(s) = Pe a -π a 1 - 1 λ ′ (-1) 1 π ′ (-1) + πQ ′ (-1) (I -P)Pe a , (21)
where π a is the coefficient of the stationary distribution π on symbol a. Now we are in position to establish asymptotics of X c (z) for large z and through depoissonization asymptotics of E[T c n ]. The inverse Mellin transform is

Xc (z) = 1 2iπ x+i∞ x-i∞ X * c (s)z -s ds (22)
valid for all x ∈] -2, -1[. Remembering that T c (z) = Xc (z) + P (a|c)z we have indeed

X(z) = 1 2iπ x+i∞ x-i∞ Γ(s)x(s)z -s ds - 1 2iπ x+i∞ x-i∞ G * (s)z -s ds (23)
We know that T(z) -X(z) is decaying exponentially fast when z → ∞.

Moving the line of integration toward the right, we meet a single pole at s = -1 of G * (s)z -z and its residues is -zPe a . Then

1 2iπ x+i inf ty x-i∞ G * (s)z -s ds = -Pe a + O(z -M ) for all M > 0.
The value -1 is also a simple pole for z -s Γ(s)x(s). We know that its residue has expression

-z Pe a -π a 1 - 1 λ ′ (-1) 1 π ′ (-1) + πQ ′ (-1) (I -P)Pe a . ( 24
)
Therefore we have

X(z) = z π a + 1 λ ′ (-1) 1 π ′ (-1) + πQ ′ (-1) (I -P)Pe a 1 + o(z). ( 25
)
For irrational case, we know that s = -1 is th only pole on the line ℜ(s) = -1, leading to the error term o(z) coming from other poles of (I -P(s)) -1 which may occur on the right half plan of s = -1.

But in the rational case, there is the possibility of other poles regularly spaced on the axis ℜ(s) = -1 with some specific matrices P detailed in [START_REF] Jacquet | Average Profile of the Lempel-Ziv Parsing Scheme for a Markovian Source[END_REF] where the coefficients α abc are introduced. In these very specific cases (the uniform probability distribution on A is one of them) the o(z) term should be replaced by a term zQ c (log z) + O(z 1-ǫ ), where Q c is a periodic vector of very small amplitude and mean zero, and ǫ > 0 depends on the matrix P. This proves Theorem 1(i).

Proof of Theorem 1(ii): Variance

We now analyze asymptotically V(z) = (V a (z), V b (z)) that satisfies the system of differentialfunctional equations [START_REF] Jacquet | Asymptotic behavior of the Lempel-Ziv parsing scheme and digital search trees[END_REF]. In order to apply depoissonization, for θ ∈ [0, π/2] we define C(θ) as the complex cone containing the complex number z such that | arg(z)| ≤ θ. on increasing domains [START_REF] Jacquet | Normal limiting distribution of the size of tries[END_REF][START_REF] Szpankowski | Average Case Analysis of Algorithms on Sequences[END_REF][START_REF] Jacquet | On the Limiting Distribution of Lempel Ziv'78 Redundancy for Memoryless Sources[END_REF] C k (θ) = {z, z ∈ C(θ)&|z| ≤ ρ k } with ρ = min c { 1 P (a|c) , 1 P (b|c) }. Our first goal is to prove that V c (z) = O(z). We shall use use the increasing domain approach [START_REF] Szpankowski | Average Case Analysis of Algorithms on Sequences[END_REF] applied to [START_REF] Jacquet | Asymptotic behavior of the Lempel-Ziv parsing scheme and digital search trees[END_REF] following the footsteps of the proof of Lemma 7A of [START_REF] Jacquet | Asymptotic behavior of the Lempel-Ziv parsing scheme and digital search trees[END_REF]. From Fact 1 of [START_REF] Jacquet | Asymptotic behavior of the Lempel-Ziv parsing scheme and digital search trees[END_REF] we conclude that

V c (z) = V c (ρz)e -z(1-ρ) + e -z z ρz e x (V a (P (a|c)x) + V b (P (b|c)x) + g(x)) dx ( 26
)
where g(z) = P (a|c) -

P 2 (a|c) + [X c z (z)] 2 = O(1)
. Indeed, it follows from Fact 1 of [START_REF] Jacquet | Asymptotic behavior of the Lempel-Ziv parsing scheme and digital search trees[END_REF] that the differential equation like

f ′ (z) = b(z) -a(z)f (z) (27) satisfies f (z) = f (z 0 )e A(z 0 )-A(z) + z z 0 b(x)e A(x)-A(z) dx where A(z) = a(z) is the primitive function of a(z). Setting in (27) f (z) = V c (z), b(z) = V a (P (a|c)z) + V b (P (b|c)z) + g(z)
and a(z) = 1 we obtain (26). Now we apply induction over the increasing domains. In short, we assume that for z ∈ C k (θ) we have |V c (z)| ≤ B k |z| for some B k . Using the induction of the increasing domains we prove, as in the Appendix of [START_REF] Jacquet | Asymptotic behavior of the Lempel-Ziv parsing scheme and digital search trees[END_REF] that B k are bounded. This completes the proof, after applying the depoissonization lemma of [START_REF] Jacquet | Analytical depoissonization and its applications[END_REF].

In order to find a precise estimate of the asymptotic development of V(z) we denote V * (s) the Mellin transform of V(z). From ( 6) we arrive at

-(s -1)V * (s -1) + V * (s) = P(s)V * (s) + g * (s),
where g * (s) is the Mellin transform of the vector made of the coefficients (∂ z X c (z)) 2 . Let V * (s) = Γ(s)B(s) and g * (s) = Γ(s)G(s). Then

B(s) = (I -P(s)) -1 (B(s -1) + G(s)) .
The quantity (I -P(s)) -1 has a pole at s = -1. Together with Γ(s) it would give a double pole at s = -1 which is not possible, as proved above. Indeed, notice that the coefficient at the double pole at s = 1 is Π(B(-2) + G(-1). But G(-1) is the the coefficient at z of g(z) and B(-2) is the coefficient at z 2 of V(z), as already proved in Lemma 1. Then we easily see that B(-2) + G(-1) = P 2 e a -Pe a , and consequently the coefficient at the double pole at s = 1is equal to Π(P 2 e a -Pe a ) = (Π -Π)e a = 0, as desired.

Therefore, the contribution of pole s = -1 to the asymptotic of V(z) is B(-1) becomes

B(-1) = 1 λ ′ (-1) π ′ (-1)(B(-2) + G(-1)) + π(B ′ (-2) + G ′ (-1)) 1
+(I -R(-1)) -1 (B(-2) + G(-1)).
Notice also that

(I -R(-1)) -1 (P 2 e a -Pe a ) = πPe a 1 -Pe a = πe a 1 -Pe a .
The real issue here is how to compute B ′ (-2) and G ′ (-1). The following lemma answers this question.

Lemma 2 Let a function g(z) = n≥1 an n! z n and f (z) = g(z)e -z = n≥1 bn n! z n . Let also g k (z) = n≤k an n! z n and f k (z) = f (z) -g k (z)e -z with f * k (s) being its Mellin transform defined for -k -1 < ℜ(s) < 0. Then lim s→-k f * (s) Γ(s) ′ = f * k (-k) 1 Γ(s) ′ s=-k + n≤k a n n! s n ′ s=-k = f * k (-k)(-1) n-1 n! + n≤k a n n! s n ′ s=-k
,

where s n = Γ(s+n) Γ(s) = (s + n -1) × • • • × s.
Proof. We start with a simple identity

f * (s) -f * k (s) Γ(s) = n≤k a n n! s n
which is easy to derive.. But the Mellin transform of f k (z) and

f * k (s) are defined for -k -1 < ℜ(s) < 0. The derivative of f * k (s)/Γ(s) at s = -k is equal to f * k (-k) Γ -1 (s) ′ s=-k since Γ -1 (-k) = 0. Finally we notice that [19] lim s→-k 1 Γ(s) ′ = lim s→-k Ψ(s) Γ(s) = lim s→-k (s + n)Ψ(s) (s + n)Γ(s) = (-1) n-1 n!
where Ψ(s) is the psi function.

In absence of specific properties on f k (z) there is no other way than numerical computation to get an estimate of f * k (-k). Finally, we can present a precise asymptotic expression for the variance.

Theorem 2 We have V(z) = ω1z + o(z) in the aperiodic case, and in the periodic case V(z) = ω1z +Q 2 (log z)z +O(z 1-ǫ ) for some ǫ > 0 and Q 2 (.) being a periodic function of small amplitude and mean zero, where

ω = 1 λ ′ (-1) π ′ (-1)((P -I)Pe a + π(B ′ (-2) + G ′ (-1)) + πe a . ( 28
)
Notice that ω = B(-1) + Pe a .

Proof of Theorem 1(iii): Central Limit Theorem

In this section we prove the CLT for T c n for any c ∈ A. The proof is heavily based on our paper [START_REF] Jacquet | On the Limiting Distribution of Lempel Ziv'78 Redundancy for Memoryless Sources[END_REF] to which we refer throughout this section. We should point out that in [START_REF] Jacquet | On the Limiting Distribution of Lempel Ziv'78 Redundancy for Memoryless Sources[END_REF] we proved CLT for the path length in DST built over of memoryless sources. In this paper we extend the main technical part of [START_REF] Jacquet | On the Limiting Distribution of Lempel Ziv'78 Redundancy for Memoryless Sources[END_REF] to Markov sources that hopefully will lead a the CLT for LZ'78.

Let us recall some notation. We define D c n (u) = E[u T c n ] as the probability generating function of T c n . To prove that T c n satisfies a central limit theorem, we use Levy's continuity theorem and show that for a complex τ we have

D c n exp τ Var(T c n ) e -τ E(T c n )/ √ Var(T c n ) → e τ 2 /2 .
In order to accomplish it we first considering a Poisson version of D c n (u), namely D c (z, u) = n D c n (u) z n n! e -z that satisfies

∂ z D c (z, u) + D c (z, u) = D c 1 (u)D a (P (a|c)z, u)D b (P (b|c)z, u) (29)
where, for short, we write D c 1 (u) = uP (a|c) + P (b|c). To follow the footsteps of our proof from [START_REF] Jacquet | On the Limiting Distribution of Lempel Ziv'78 Redundancy for Memoryless Sources[END_REF] we need to generalize deep technical result of [START_REF] Jacquet | On the Limiting Distribution of Lempel Ziv'78 Redundancy for Memoryless Sources[END_REF], namely Theorem 10 (and its un-Poissonized version Theorem 6) to T c n with the Markov input. Once we prove below Theorem 3 we not only recover CLT but also large and moderate deviation for T c n . In this conference version we present our results for CLT. For δ > 0 we denote |z * | -δ = max{1, |z| -δ } in order to avoid a singular behavior when z → 0. Theorem below is equivalent to Theorem 10 of [START_REF] Jacquet | On the Limiting Distribution of Lempel Ziv'78 Redundancy for Memoryless Sources[END_REF].

Theorem 3 For all real number δ > 0, there exists 0 < θ < π/2 and a complex neighborhood U (0) of 1 such that for t ∈ U (0) and z ∈ C(θ) log(D c (z, e t|z * | -δ )) exists and log(D c (z, e t|z * | -δ ) = O(z) uniformly in t ∈ U (0).

Proof. We notice that D c (z, 1) = 1 thus log D c (z, 1) = 0 From now we will work with Dc (z, u) = D c (z, u)e z . As in [START_REF] Jacquet | On the Limiting Distribution of Lempel Ziv'78 Redundancy for Memoryless Sources[END_REF] we define the kernel functions f c (z, u): . Clearly if f c (z, u) exists and has no roots in a given domain, then the function log Dc (z, u) exists in this domain. Again following [START_REF] Jacquet | On the Limiting Distribution of Lempel Ziv'78 Redundancy for Memoryless Sources[END_REF] we are going to prove that for u = e t|z| -δ we have f c (z, u) = 1 + b(z, t) with b(z, t) = O(|t|) when z is in a complex cone C(θ). That way by selecting t sufficiently close to 0 (see (32) below) we will have f c (z, u) = Θ(1). At the same time we prove that log Dc (z, u) exists and is O

(z) in C(θ) since Dc (z, u) = 1 + z 0 dx f c (x, u)
for z ∈ C(θ) and the integration path in C(θ).

In fact we will prove a slightly different result which indeed implies the main result. For an arbitrary number ν < 1 and t complex we define the sequence u k = e ν k t and the function f c,k (z) = f c (z, u k ). To make the connection with the main result it suffice to set δ = -log ν log ρ . We denote

f c,k (z) = 1 + b k (z, t), 1 f c,k (z) = 1 + a k (z, t).
We will prove that for all integer k and for all z ∈ C k (θ) we uniformly have a k (z, t) = O(|t|) and b k (z, t) = O(|t|). We will prove this property by recursion on the increasing domains C k (θ). For k = 0 we already checked the proposition. In passing we notice that a k+1 (z, t) = a k (z, νt) and similarly b k+1 (z, t) = b k (z, νt). As in [START_REF] Jacquet | On the Limiting Distribution of Lempel Ziv'78 Redundancy for Memoryless Sources[END_REF] we have the differential equation

∂ z f c,k (z) = 1 -f c,k (z)g c,k (z) with g c,k (z) = P (a|c) f a,k (P (a|c)z) + P (b|c) f b,k (P (b|c)z)
.

The resolution of the differential equation is (see also previous section)

f c,k (z) = 1 + z 0 (1 -g c,k (z)) exp(G c,k (z) -G c,k (x))dx
with the function G c,k (z) being a primitive of g c,k (z).

We notice now that when z ∈ C k , then ∀(c, d) P (d|c)z ∈ C k-1 (θ), therefore we can apply the recurrence hypothesis. For this purpose we denote

a k = max z∈C k (θ),c∈A,t∈U (0) |a k (z, t)| |t| .
We have g c,k (z) -1 = P (a|c)a a,k-1 (P (a|c)z, νt) + P (b|c)a b,k-1 (P (b|c)z, νt)

and therefore |g c,k (z) -1| ≤ a k-1 ν|t|. Consequently |f c,k (z) -1| ≤ a k-1 ν|t| 1 0 |z| exp (ℜ(G c,k (z) -G c,k (yz))) dy.
Now we observe that for any y

ℜ (G c,k (yz) -G c,k (z)) = -ℜ(z)(1 -y) + 1 y ℜ((g c,k (xz) -1)z)dx (30) ≤ (-cos(θ)|z| + νa k-1 |t|.|z|)(1 -y). (31)
Consequently

b k |t| ≤ νa k-1 |t| 1 0 |z|e -(cos θ-νa k-1 |t|)|z|y dy ≤ νa k-1 |t| cos θ -νa k-1 |t| .
As noticed in [START_REF] Jacquet | On the Limiting Distribution of Lempel Ziv'78 Redundancy for Memoryless Sources[END_REF] the sequences b k and a k converges if |t| is small enough and θ is selected such as ν/cos θ < 1.

The path from the previous result to the normal limiting distribution for the D c (z, u) and for the D c n (u) is now via depoissonization as detailed in [START_REF] Jacquet | On the Limiting Distribution of Lempel Ziv'78 Redundancy for Memoryless Sources[END_REF]. In short for all values of δ > 0, in particular for the small values, we have log Dc (z, e |z| -δ t ) = O(z) = z + O(z|t|) for z → ∞ which translates to log Dc (z, e |z| -δ t ) = z + T c (z)|z| -δ t + V ar c (z)|z| -2δ t 2 + O(|z| 1-3δ |t| 4 ).

The proof of Theorem 1(iii) is complete by setting as in [START_REF] Jacquet | On the Limiting Distribution of Lempel Ziv'78 Redundancy for Memoryless Sources[END_REF] t = τ n δ VarT c n = O(n -1/2+δ ) → 0 (32) for δ < 1/2.

Concluding Remarks

Our ultimate goal is to solve the fifty year open problem of a full characterization of the Lempel-Ziv'78 scheme under Markovian assumption. We claim that our Theorem 1 proved in this paper is a step in the direction of resolving this open problem. In this concluding remarks we provide some evidence justifying our confidence. We recall that D c n = P (T c n = k), and to make the notation under control we shall assume that the tail symbol involved in T c n could be an a or a b. It will be clear from the context. In Theorem 1 we presented our main results concerning D c n . Now, we show how it can be used to analyze LZ'78 scheme under Markovian assumption. It should be clear that to analyze LZ'78 with Markov input we need to study the number of phrases or blocks that start with a symbol c ∈ A and end with another symbol. However, it will be more convenient to consider the tail symbol, that is, the symbol that follows the last symbol of a phrase.

We shall prove the following claim. This and Lemma 3 will allow us to bound P ma,m b between two normal distributions of very similar mean and variance. Stay tuned!

  f c (z, u) = Dc (z, u) ∂ z Dc (z, u) = Dc (z, u) D c 1 (u) Da (P (a|c)z, u) Db (P (b|c)z, u).Notice that f c (z, 1) = 1. We have f c (z, u) = 1 ∂z log Dc(z,u)

Lemma 3

 3 Let m a + m b = m. Let P c ma,m b the probability that m a blocks/phrases among the first m start with symbol a while m b start with symbol b assuming that the sequence starts with c. ThenP c ma,m b ≤ k D a ma,k D b m b ,ma-1-k + D a ma,k D b m b ,ma-k , or written differently P c ma,m b ≤ [u ma ](1 + u)D a ma (u)D b m b (u) where D c n (u) = E[u T c n ] is analyzed in Theorem 1.

Finally, we indicateLemma 4

 4 a lower bound. Let (c, d) ∈ A 2 , we denote D c,d m,k the probability that m + 1 i.i.d Markovian sequences all starting with symbol c have k tail symbols equal to a and the last sequence has a tail symbol equal to d. The D c,d m,k quantity have similar recursion as the D c m,k 's and we write D c,d m (u) = k D c,d m,k u k . We have P a ma+1,m b ≥ [u ma ]D a,a ma (u)D b m b (u).

This author was supported by NSF Science & Technology Center Grant CCF-0939370, NSF Grant CCF-1524312, and NIH Grant 1U01CA198941-01.