domain: info math

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

Wojciech Szpankowski

Analysis of Lempel-Ziv'78 for Markov Sources

Keywords: 2012 ACM Subject Classification Mathematics of computing → Information theory Lempel-Ziv algorithm, digital search trees, depoissonization, analytic combinatorics, large deviations Digital Object Identifier 10.4230/LIPIcs.AofA.2020.15

Lempel-Ziv'78 is one of the most popular data compression algorithms. Over the last few decades fascinating properties of LZ78 were uncovered. Among others, in 1995 we settled the Ziv conjecture by proving that for a memoryless source the number of LZ78 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. The 1995 proof of the Ziv conjecture was based on two models: In the DST-model, the associated digital search tree (DST) is built over m independent strings. In the LZ-model a single string of length n is partitioned into variable length phrases such that the next phrase is not seen in the past as a phrase. The Ziv conjecture for memoryless source was settled by proving that both DST-model and the LZ-model are asymptotically equivalent. The main result of this paper shows that this is not the case for the LZ78 algorithm over Markov sources. In addition, we develop here a large deviation for the number of phrases in the LZ78 and give a precise asymptotic expression for the redundancy which is the excess of LZ78 code over the entropy of the source. We establish these findings using a combination of combinatorial and analytic tools. In particular, to handle the strong dependency between Markov phrases, we introduce and precisely analyze the so called tail symbol which is the first symbol of the next phrase in the LZ78 parsing.

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 as a phrase. For example, aababbababbb is parsed as ()(a)(ab)(abb)(aba)(b)(bb). The LZ78 compression code consists of a pointer to the previous phrase and the last symbol of the current phrase. The distribution of the number of phrases and other related quantities (such as redundancy and code length) are known for memoryless sources [START_REF] Louchard | Average profile and limiting distribution for a phrase size in the lempel-ziv parsing algorithm[END_REF][START_REF] Savari | Redundancy of the lempel-ziv incremental parsing rule[END_REF] but research over the past 40 years has failed to produce any significant progress for Markov sources. In this paper, we present novel large deviations and precise redundancy results that had been wanting since the algorithm inception, as well as some surprising findings regarding the difference between the memoryless case and the Markov case.

15:2

Lempel-Ziv'78 for Markov Sources

It is convenient to organize phrases (dictionary) of the Lempel-Ziv scheme in a digital search tree (DST) [START_REF] Jacquet | Analytic Pattern Matching: From DNA to Twitter[END_REF] which represents a parsing tree. We assume throughout that A = {a, b}. Then the root 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 (ab) that is stored in a node attached to the root. This process repeats recursively until the text is parsed into full phrases (see Figure 1). A detailed description can be found in [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] Knuth | The Art of Computer Programming Sorting and Searching[END_REF].

Figure 1 The DST-model vs LZ-model. In the DST-model we inserted eight (infinite) strings: We consider two models called the DST-model and the LZ-model. In the DST-model we insert independent strings although each string may be generated by a source with memory like a Markov source. In the LZ-model we parse a single string as shown in Figure 1. We distinguish two types of DST and LZ models. To define them we need to introduce the path length L as the sum of all depths in the digital search tree or the sum of all phrases in the LZ model. In the "m"-DST model we insert m independent strings into a digital search tree -leading to a variable path length denoted as L m -while the "n"-DST model is built over a random number of independent strings such that the total path length is equal to n. Similarly, we have "m"-LZ and "n"-LZ models: In the former we construct m LZ phrases to form a string of (variable) length denoted as L m while in the "n"-LZ model we parse a string of length n into a variable number of phrases that we denote as M n . Throughout, m will denote number of strings or phrases while n will stand for the length of a string.

X 1 = abb • • • , X 2 = abb • • • , X 3 = bbba • • • , X 4 = abaaa • • • , X 5 = bbaa • • • , X 6 = baaa • • • , X 7 = bbba • • •
There is a simple relation between M n and L m called the renewal equation which asserts

P (M n > m) = P (L m < n). ( 1
)
Finally, observe that the code length of the LZ78 algorithm is C n = Mn k=1 log 2 (k) + log 2 (|A|) since the pointer to the kth node requires at most log 2 k bits, while the next symbol costs log 2 |A| bits. For binary alphabet A = {a, b} we simplify the code length to

C n = M n (log 2 M n + 1).
To understand LZ78 behavior one must analyze the limiting distribution of M n and/or L m connected through the renewal equation [START_REF] Aldous | A diffusion limit for a class of random-growing binary trees[END_REF]. For memoryless sources we benefited from the fact the random variable L m and L m are probabilistically equivalent as shown in 1995 paper [START_REF] Jacquet | Asymptotic behavior of the lempel-ziv parsing scheme and digital search trees[END_REF]. Unfortunately, this equivalence breaks for sources with memory such as Markov sources. To capture this dependency we introduce the notion of the tail symbol. In the DST-model the tail symbol of an inserted string is the first non-inserted symbol of that string, as shown in Figure 1. In the LZ-model the tail symbol of a phrase is the first symbol of the next phrase (see Figure 1). Furthermore, in the Markov case there is additional complication, even for the DST-model. In the DST-model we need to consider two digital search trees: one built over all (independent) strings starting with symbol a ∈ A, and the second one built over all strings that start with b ∈ A. At the end we construct a cumulative knowledge by weighting over the initial symbols (see [START_REF] Jacquet | Average profile of hte lempel-ziv parsing scheme for a markovian source[END_REF]).

In this paper, we present large deviation results for the number of phrases M n in "n"-LZ model and the average length of a LZ (Markov) string built over m phrases in the "m"-LZ model. 1 In the memoryless case we could read the number of phrases M n directly from the path length L m of the m-DST model. It is not the case in the Markov model but through the tail symbol distribution we will connect both quantities. Recall that L m is the length of a string generated by a Markov source which is parsed by the LZ78 scheme until we see m phrases (our m-LZ model). This should be compared to the total path length L m (notice roman font for L) in the the m-DST model. In the memoryless case, we proved in [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] that the expected value of L m and the expected value of the length of a string built from m phrases, L m , are the same. Somewhat surprisingly it is not the case for the Markov case. We will prove in Theorem 5 that

E[L m ] -E[L m ] = Θ(m).
Let us now briefly review literature on LZ78 and DST analysis. The goal is to prove the Central Limit Theorem (CLT) for the number of phrases and establish precise rate of decay of the LZ78 code redundancy for Markov sources. For memoryless sources, CLT was already proved in [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 | Average profile and limiting distribution for a phrase size in the lempel-ziv parsing algorithm[END_REF][START_REF] Savari | Redundancy of the lempel-ziv incremental parsing rule[END_REF]. It should be pointed out that since 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 only known to us analysis of LZ78 for Markov sources is presented in [START_REF] Jacquet | Average profile of hte lempel-ziv parsing scheme for a markovian source[END_REF], but the authors restricted their attention to a single phrase. We should point out that for another Lempel-Ziv scheme known as LZ'77 algorithm, Fayolle and Ward [START_REF] Fayolle | Analysis of the average depth in a suffix tree under a markov model[END_REF] analyzed an associated suffix tree built over a Markov string and obtained the distribution of the depth, which allows us to conclude the limiting distribution of a phrase in the LZ'77 scheme (see also [START_REF] Merhav | Universal coding with minimum probability of codeword length overflow[END_REF][START_REF] Merhav | On the amount of statistical side information required for lossy data compression[END_REF]). Regarding analysis of digital search trees, and in general digital trees, more is known [START_REF] Knuth | The Art of Computer Programming Sorting and Searching[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]. 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] Louchard | Average profile and limiting distribution for a phrase size in the lempel-ziv parsing algorithm[END_REF][START_REF] Jacquet | Analytic Pattern Matching: From DNA to Twitter[END_REF] while digital trees under Markovian models were studied in [START_REF] Jacquet | Average profile of hte 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][START_REF] Fayolle | Analysis of the average depth in a suffix tree under a markov model[END_REF]. This information is surveyed in detail in [START_REF] Jacquet | Analytic Pattern Matching: From DNA to Twitter[END_REF].

The paper is organized as follows. In the next section we present our main results regarding the LZ and DST models including the mean, variance and distribution of the number of tail symbols in the DST model (see Theorem 2-4), and large deviations as well as precise redundancy for the LZ model (see . We prove these findings in Section 3 (DST model) and in Section 4 (LZ model), with most details delayed till the appendix. Throughout we use combinatorics on words and analytic tools such as generating functions, Poisson transform, analytic depoissonization, and Mellin transform.

Main Results

We consider a stationary ergodic Markov source generating a sequence of symbols drawn from a finite alphabet A. In this paper we study only a binary Markovian process of order 1 with the transition matrix P = [P (c|d)] c,d∈A where A = {a, b}. In this section we present our main results with proof delayed till Sections 3-4 and appendix. However, first we present a road map of our methodology and findings.

1 From now on we drop the quotes around m and n to simplify the presentation.

A o f A 2 0 2 0 15:4

Lempel-Ziv'78 for Markov Sources

Our main goal is to analyze the Lempel-Ziv'78 scheme for Markovian input. However, as discussed before, we first consider an auxiliary model named DST-model built over m independent Markov strings, also called the m-DST model. However, for Markov sources we need to construct two conditional digital search trees: one built over m Markov strings all starting with symbol a ∈ A and the other DST built over m strings starting with b ∈ A. We write c ∈ A for a generic symbol from A, that is, either c = a or c = b. For a given c ∈ A, we consider m independent Markov strings all starting with c and build an m-DST tree. For such a tree we analyze two quantities, namely the total path length denoted as L c m , and the number T c m (a) of inserted strings (all starting with c) with the tail symbol a, that is, among m Markov strings there are T c m (a) strings with the tail symbol a. Clearly,

T c m (a) + T c m (b) = m.
Throughout, we also assume that the tail symbol is always a so we just write T c m := T c m (a). In Theorems 2-3 we summarize our new results regarding T c m , while in Theorem 4 we present large deviation results for both T c m and L c m . Second, we consider the m-LZ model (in which we run LZ78 algorithm on a single string until we see m phrases) and tie it up to the m-DST model just discussed. Here we use a combinatorial approach. For a given sequence s over A of length m we compare in Lemmas 10-11 two probabilities: (i) the probability that in the m-LZ model (constructed from m LZ phrases) we end up with a LZ sequence of length n having all tail symbols equal to s; and (ii) the probability that in the m-DST model (built over m independent Markov strings) the resulting digital search tree has path length equal to n and all tail symbols are equal to s. Using this, we present in Theorem 5 our large deviations for the m-LZ model and using the renewal equation ( 1) in Theorem 6 we establish large deviations for the n-LZ model. In Corollary 7 we find a precise expression for the redundancy of LZ78 for Markov sources.

Finally, when comparing the average path length L c m in the m-DST model with the length L c m in the m-LZ model we shall use the following simple fact.

Proposition 1. For δ < 1 let there exist B, C > 0 such that for a discrete random variable X m the following holds uniformly

P (X m = k) ≤ B exp -Cm -δ |k -A m | . ( 2
)
Then

E[X m ] = A m + O(m δ ). (3)
Proof. Define B m = m δ (log B)/C ≤ |k -A m |. Then it is easy to see that EX m = k kP (X m = k) = A m + k (k -A m )P (X m = k)
, and the latter term can be estimated by the integral 2B ∞ 0 exp(-Cm -δ x)(x + 1)dx = O(m δ ). This completes the proof.

Results on DST

In this section we summarize our results for the m-DST model: We first focus on the number of times, T c m := T c m (a), the tail symbol is a when all m Markov sequences start with c ∈ A. Then we study the path length L c m in the m-DST model when all sequences start with c. Finally, we present large deviations for both T c m and

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

D c m+1 (u) = (P (a|c)u + 1 -P (a|c)) k m k P (a|c) k P (b|c) m-k D a k (u)D b m-k (u) (4) subject to D c 0 (u) = 1 and D c 1 (u) = P (a|c)u + 1 -P (a|c). Furthermore, define the bivariate Poisson transform D c (z, u) = m≥0 E[u T c m ] z m m! e -z .
From above we easily find 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) (5)
with D c (z, 1) = 1 where ∂ z is the partial derivative with respect to variable z.

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 2 , and the limiting distribution of T c m . After finding the 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 | Anaylytical depoissonization and its applications[END_REF] to extract the original mean and variance:

V c (z) = ∂ 2 u D c (z, 1) + X c (z) - (X c (z))
E[T c m ] = X c (m) - 1 2 m∂ z X c (m) + O(X c (m)/m), Var[T c m ] ∼ V c (m) -m[∂ z X c (m)] 2 .
Let us start with the Poisson mean X c (z). Taking the derivative of ( 5) 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). ( 6
)
To complete this equation we need to calculate the initial values of

E[T c m ]. 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).

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). ( 8
)
Both differential-functional system of equations ( 5) and ( 7) can be solved using complicated Mellin transform approach [START_REF] Szpankowski | Average Case Analysis of Algorithms on Sequences[END_REF]. We provide details of our approach in the Appendix. 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 and π(s) the main eigenvector. We notice that π(-1) is the stationary vector of the Markov process. We also need another matrix

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

Theorem 2. Consider a digital search tree built over m independent sequences (m-DST) generated by a Markov source. We have E[T

c m ] = τ c (m)m and E[L c m ] = m log m/h + m + µ c (m)m such that: τ c (m + 1) -τ c (m) = O(1/m) and µ c (m + 1) -µ c (m) = O(1/m) ∀(c, d) ∈ A 2 τ c (m) -τ d (m) = O(1/m) and µ c (m) -µ d (m) = O(1/m).
A o f A 2 0 2 0 15:6

Lempel-Ziv'78 for Markov Sources

Thus τ c (m) = τ (m) + O(1/m) where τ (m) does not depend on initial symbol c. In fact, τ (m) depends on the tail symbol, but since throughout the paper we assume the tail symbol is always a, we drop this dependency on a in τ (m). We present precise formula on τ (m) in the next theorem.

Similarly we have µ c (m) = µ(m) + O(1/m). The function µ(m) for Markov sources is given in Theorem 1 of [START_REF] Jacquet | Average profile of hte lempel-ziv parsing scheme for a markovian source[END_REF]. For the memoryless source, it is h2 h + γ -1 + α and the average path length is m log m/h + mµ(m), as discussed in [START_REF] Jacquet | Asymptotic behavior of the lempel-ziv parsing scheme and digital search trees[END_REF].

To complete our analysis of the tail symbol, we present now precise behaviour of τ (m). We give a detailed proof in the Appendix.

Theorem 3. For (a, b, c) ∈ A 3 define α abc = log P (a|b)P (c|a) P (c|b) . ( 10
) (i) Aperiodic case. If not all {α abc } are rational, then τ (m) = τ + o(1) with τ = π a + 1 λ (-1) π (-1) + πQ (-1) (I -P)Pe a , ( 11
)
where π a is the stationary distribution of symbol a, and e a is the vector made of a single 1 at the position corresponding to symbol a and zero otherwise. Periodic case. If all {α abc } are rationally related, then for some ε > 0 we have

τ (m) = τ (m) + O(m -ε ) with τ (m) = τ + Q 1 (log m), where Q 1 (.) is a periodic function. (ii) Variance. The variance Var[T c m ] grows linearly, that is Var[T c m ] ∼ mω a (m)
, where ω a (m) = ωa for the aperiodic case and ω a (m) = ωa + Q 2 (m) for the periodic case, where ωa is given explicitly in the Appendix in (B. [START_REF] Ziv | Compression of individual sequences via variable-rate coding[END_REF]) of Theorem 14, and Q 2 (m) is a nonzero periodic function for rationally related case, and zero otherwise. (iii) Central Limit Theorem. For any c ∈ A we have

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

Similarly we have the same behaviour for µ(m) which is equal to μ + o(1) in the aperiodic case and, in the periodic case, is equal to μ + Q 3 (log m) + O(m -ε ) whose expressions are in [START_REF] Jacquet | Asymptotic behavior of the lempel-ziv parsing scheme and digital search trees[END_REF] and [START_REF] Jacquet | Average profile of hte lempel-ziv parsing scheme for a markovian source[END_REF] where Q 3 (.) is a periodic function. For details the reader is referred to [START_REF] Jacquet | Average profile of hte lempel-ziv parsing scheme for a markovian source[END_REF].

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. The reason is that the tail symbol is not picked up at random in the sequence but occurs when the sequence path leaves the tree.

Finally, we present joint large deviations for both T c m and L c m which is a new result needed to establish large deviations for the LZ model. We prove it in Section 3. Theorem 4. Consider a digital search tree (DST) built over m independent sequences generated by a Markov source. For all δ > 1/2 there exist B, C and β strictly positive such that for all x > 0 uniformly in x

P |T c m -E[T c m ]| + |L c m -E[L c m ]| ≥ xm δ ≤ Be -xCm β (12)
for large m.

Results for the LZ78 Model

Let us start with the m-LZ model. For a given m, let L c m (note calligraphic L) be the length of the LZ78 string composed of m phrases when the first phrase starts with symbol c. For memoryless sources, this quantity is equivalent to the path length L m in the associated DST built over m independent strings. However, it is not the case for Markov sources. In Section 4 we prove

E[L c m ] = m log m/h + µ(m * )m * + µ(m -m * )(m -m * ) + m(1 -H(m * /m)/h) + O(m δ ) ( 13
)
where

H(x) = -x log x -(1 -x) log(1 -x)
is the binary entropy and h the source entropy. (ii) For all δ > 1/2 there exist B, C, β > 0, and γ > 0 such that uniformly for all x > 0

P |L c m -E[L c m ]| ≥ xm δ ≤ Bm γ e -xCm β (14)
for large m.

Remark. The property of function τ (•) implies that the equation x-xτ (x)-(m-x)τ (m-x) has a single root as we will see in the proof of Section 4. Notice that m * /m converges to τ in the aperiodic case, and similarly µ(m * )m * + µ(m -m * )(m -m * ) is asymptotically equivalent to μm. In the periodic case there will be small periodic contributions (contained in τ (m) and µ(m)) as shown in Theorem 3. Notice that H(m * /m) is the tail symbol entropy, which is equal to h when the source is memoryless. Using Theorem 6 we can find a precise estimate on the LZ78 redundancy. Indeed, a good approximation for the LZ78 code length is

C c n = M c n (log M c n + 1)
. The average conditional redundancy is defined as

r c n := E[C c n ]/n -h, while the total average redundancy is r n = π a r a n + π b r b n .
Corollary 7. The average redundancy rate r n satisfies for all 1 2 < δ < 1:

r n = h 1 -β( -1 (n)) log -1 (n) + β( -1 (n)) + O(n δ-1 log n) ∼ h 1 -β( -1 (n)) log n ,
and more specifically in the aperiodic case we have

r n ∼ h 1 - μ log n + H(τ ) -h log n
where m * /m → τ .

Proof of Theorem 4 for DST

Now we prove Theorem 4, that is, the joint large deviations for T c m and L c m in the m-DST model. We use Chernoff's bounds, so we need to introduce some bivariate generating functions. Define

P c m,k, = P (T c m = k & L c m = ), P c m (u, v) = E[u T c m v L c m ] = k, P c m,k, u k v and P c (z, u, v) to be the Poisson generating function P c (z, u, v) = m P c n (u, v) z m m! e -z .
The following partial differential equation for P c (z, u, v) is easy to establish from ( 5)

∂ z P c (z, u, v) + P c (z, u, v) = (uP (a|c) + P (b|c))P a (P (a|c)zv, u, v)P b (P (b|c)zv, u, v).
Lemma below is equivalent to Theorem 10 of [START_REF] Jacquet | On the limiting distribution of lempel ziv'78 redundancy for memoryless sources[END_REF] so we skip the proof in this conference paper.

Lemma 8. For all reals ε > 0 and > 0, there exists 0 < ϑ < π/2 and a complex neighborhood U(0) of 0 such that iuniformly for (t 1 , t 2 ) ∈ U(0) 2 and | arg(z)| < ϑ so that log(P c (z, e t1|z| -ε , e t2|z| -ε )) exists and log(P c (z, e t1|z| -ε , e t2|z| -ε ) = O(z 1+ε ).

To prove Theorem 4 we need the following property that will be established in the final version of this paper. Lemma 9. For all δ > 1/2 there exists B such that

P c m (e τ1m -δ , e τ2m -δ ) exp(-m -δ (τ 1 E[T c m ] + τ 2 E[L c m ])) ≤ B √ m. ( 15
)
P. Jacquet and W. Szpankowski

15:9

Now we proceed to prove Theorem 4. We apply Markov inequality for all θ and for all x > 0

P (|T c m -E[T c m |+|L c m -E[L c m ]| ≥ 2xm δ ) ≤ P (|T c m -E[T c m ]| ≥ xm δ ∨(|L c m -E[L c m ]| ≥ xm δ ) ≤ P c m (e θ , 1)e -E[T c m ]θ + P c m (e -θ , 1)e E[T c m ])θ e -xθm δ + P c m (1, e θ )e -E[L c m ]θ + P c m (1, e -θ )e E[L c m ]
)θ e -xθm δ .

To complete the proof we will use (15) of Lemma 9. If we take τ 1 = ±C and τ 2 = 0 (and reverse) for some C > 0 such that (τ 1 , τ 2 ) ∈ U(0) 2 , and θ = Cm -δ for some δ < δ, then we find e θm δ = e -Cm β with β = δ -δ > 0, and

P (|T c m -E[T c m ]| + |L c m -E[L c m ]| ≥ 2xm δ ) ≤ 4 √ mBe -xCm β
which prove (12) Theorem 4. We can readjust by taking 0 < β < β and the value of B to omit the factor √ m.

Proof of Theorem 5 for LZ

We now consider the LZ78 algorithm over a single infinite sequence generated by a Markov source, that is, the n-LZ model and connect it to the n-DST model in which the path length is equal to n (over a variable number of independently inserted strings). In the m-LZ model there are exactly m LZ phrases, each being a block carved in the Markovian sequence. The blocks are not i.i.d Markovian sequences. Let P c m,n be the probability that the length of the first m LZ phrases is exactly n (when the first symbol is c), leading to the n-LZ model. Notice that not every pair (n, m) is feasible in the LZ model since by adding another phrase the path length may "jump" by more than one. We are interested in finding an asymptotic estimate of P c m,n . We start by introducing yet another model. Let s be a sequence of m symbols, namely s = (c 1 , . . . , c m ) ∈ A m . For c ∈ A we now compute the probability P c s,n that an infinite Markovian sequence starting with symbol c when parsed by LZ algorithm satisfies the following two properties: (i) the first m blocks have tail symbols c i ∈ s for i ≤ m so that c i is the first symbol of block i + 1; (ii) the length of the first m LZ phrases is equal to n. If a string satisfies these two conditions, then we say it is (s, n) compatible and that it belongs to the (s, n)-LZ model. Given a string s of tail symbols we denote by t a c (s) (resp. t b c (s)) the subsequence of s consisting of tail symbols of the LZ blocks starting with symbol a (resp. starting by symbol b). Now, it is easy to see that given the initial symbol c we can deduce the sequence of tails symbols and initial symbols of all phrases just by looking at the sequence s, where the initial symbol of the next phrase is the tail symbol of the previous phrase. For example, if s = (a, b, a, b, b) and c = a we have the following tail symbol and initial symbol sequence displayed in the following table: Now we consider a sequence t of m symbols and introduce a new n-DST model which we call (t, n)-DST model. We define by P c t,n the probability that m i.i.d. (independent) Markovian sequences all starting with c satisfy the following two conditions (notice that we use roman P for this probability and calligraphic P for LZ model): (i) the tail symbol sequence follows the sequence t; (ii) the external path length of the DST is exactly n. We will say that such m strings are (t, n)-fit if they satisfy the above conditions and call it (t, n)-DST model. We also define

P c m,k,n = t: |t|=m,|t|a=k P c t,n (16)
with |t| being the length of sequence t and |t| a being the number of symbols equal to a in it.

We finally establish the following fundamental lemma that connects the above two parameters which also connects the LZ parsing over a single Markovian sequence and the DST made of independent Markovian sequences, that is, (s, n)-LZ model and (t, n)-DST model where t is a function of s.

Lemma 10. For any s ∈ A m we have

P c s,n = na P a t a c (s),na P b t b c (s),n-na ( 17
)
where n c (equal either to n a or n b ) is the path length in n c -DST model with all strings starting with c, and t a c (s), t b c (s) are substrings of s as defined above. Proof. In this conference paper, we give a proof using an example to ease the presentation. Let us consider X = aabbababab • • • which results in the following LZ blocks:

()(a)(ab)(b)(aba)(ba)(b • • • ). Or equivalently X = aabbababab • • •
where the initial block (phrase) symbols are displayed in bold. We notice that the first five blocks (excluding the initial empty block) accounts for a string of length 9. Thus the sequence X is (s, 9) compatible with s = (a, b, a, b, b). Given that X starts with symbol a we have P (X) = P (a|a)P (aa|a)P (abb|a)P (ba|b))P (abab|a)P (bab|b). Notice that we display in bold the tail symbol of each block (which is the initial symbol of the next block). We must incorporate P (X) into P a s, [START_REF] Leckey | Towards more realistic probabilistic models for data structures: The external path length in tries under the markov model[END_REF] . In fact X should be viewed as the set of (infinite) strings having aabbababab as the common prefix. We can rewrite P (X) by regrouping the terms with respect to the initial symbol of each block as: P (X) = [P (aa|a)P (abb|a)P (abab|a)] × [P (ba|b)P (bab|b)] . Observe that the sequence of strings (aa, abb, abab) are the prefixes of a set of tuples of independent infinite strings that are all (s a , 6) compatible with s a = t a a (s) = (a, b, b) under the condition that the strings start with symbol a (the path length in the DST excludes the tail symbols, thus we must remove one from the length of each prefix). The probability of such event is exactly P (aa|a)P (abb|a)P (abab|a) and must be incorporated in P a s a ,6 . Furthermore, these sequences are used to build one (left) part of the DST tree with independent Markov strings all starting with a. The same holds for the sequence of strings (ba, bab) which is (s b , 3) compatible with s b = t b a (s) = (a, b) and used to build the other part (right) of the DST tree. This leads to (17).

The next crucial lemma connects n-LZ and n-DST models.

P c m,n = s∈S c 0 (m)∪S c 1 (m) P c s,n + s∈S2(m) P c s,n + s∈S3 (m)
P c s,n .

Now we have to deal with the right hand side of (18), that is, with the DST model. Let T 1 (m) be the set of pairs of arbitrary sequences denoted as (t a , t b ) such that

|t a | + |t b | = m and |t a | a + |t b | a = |t a |. We notice that for s ∈ S c 1 (m) ∪ S c 2 (m): (t a c (s), t b c (s)) ∈ T 1 (m), hence s∈S c 0 (m)∪S c 1 (m) P c s,n = na s∈S c 0 ∪S c 1 (m) P a t a (s),na P b t b (s),n-na ≤ na (ta,t b )∈T1(m) P a t a ,na P b t b ,n-na .
Notice that we have an upper bound, since for some pair (t a , t b ) in T c 1 (m) there may not exist s ∈ S c 1 (m) ∪ S c 2 (m) such that t a = t a (s) and t b = t b (s). For example, let c = a and for m = 4 we set t a = (a, b) and t b = (b, a), so that

|t a | a + |t b | a = |t a | but it is impossible to find s such that (t a a (s), t b (s)) = (t a , t b
). Thanks to [START_REF] Ziv | Compression of individual sequences via variable-rate coding[END_REF] we have t: |t|=m,|t|a=k P c t,n = P c m,k,n leading to

(ta,t b )∈T1(m) na P a t a ,na P b t b ,n-na = ma,k P a ma,k,na P b m-ma,ma-k,n-na .
This proves the first term in the right hand side of (18). To prove the other two terms we introduce T 2 (m) as the set of pairs of sequence (t a , t b ) such that

|t a | + |t b | = m and |t a | a + |t b | a = |t a | -1. In this case s∈S2(m) P c s,n ≤ na (t a ,t b )∈T2(m) P a t a ,na P b t b ,n-na ,
and the second term of ( 18 To finish the proof of Theorem 5 we now use the previous lemmas to upper bound

P c m,n . Let P c m,n ≤ K c m,n (0) + K c m,n (1) + K c m,n (-1) with K c m,n (i) = ma na k P a ma,k,na P b m-ma,ma-k-i,n-na .
To simplify our presentation we only study K c m,n (0). First, we rewrite the bound in Theorem 4 for the DST model as follows: for δ > 1/2 there exist B and C strictly positive such that

P c m,k,n ≤ B exp -Cm -δ |k -E[T c m ]| -Cm -δ |n -E[L c m ]| . Thus K c m,n (0) ≤ ma+m b =m k≤ma na+n b =n B 2 exp -Cm -δ a |k -E[T c ma ] -Cm -δ a |n a -E[L a ma | -Cm -δ b |m a -k -E[T b m b ] -Cm -δ b |n b -E[L b m b | .
From here we use m a , m b ≤ m to find

Cm -δ a |k -E[T c ma ] + Cm -δ a |n a -E[L a ma | + Cm -δ b |m a -k -E[T b m b ] + Cm -δ b |n b -E[L b m b | ≥ Cm -δ |k -E[T c ma ] + Cm -δ |n a -E[L a ma | + Cm -δ |m a -k -E[T b m b ] + Cm -δ |n b -E[L b m b | ≥ Cm -δ |m a -E[T a ma ] -E[T b m b ]| + Cm -δ |n -E[L a ma ] -E[L b m b ]|.
Replacing We now focus only on the aperiodic case and set τ (m) = τ m and µ(m) = μm. (We know that even in this case for small values of m, the µ(m) and τ (m) are not exactly linear in m, but we handle it later.) Thus our term K c m,n (0) is bounded by

B 2 m ma≤m exp[-Cm -δ |m a -τ m|] exp[-Cm -δ |n-m log m/h-μm+m(H(m a /m)/h-1)|].
If we take any δ > δ we find

K c m,n (0) ≤ B 2 m ma≤m exp[-Cm -δ |m a -τ m|] × exp[-Cm -δ |n -m log m/h -μm + m(H(m a /m)/h -1)|].
We observe that exp[-Cm -δ |m a -τ m|] attains its maximum at m a = m * = τ m. Thus

K c m,n (0) ≤ B 2 ma≤m * e Cm -δ (m-m * ) ×exp[-Cm -δ |n-m log m/h-μm+m(H(m a /m)/h-1)|]] +B 2 ma≥m * e Cm -δ (m * -m) × exp[-Cm -δ |n -m log m/h -μm + m(H(m a /m)/h -1)|]].
P. Jacquet and W. Szpankowski

15:13

Notice that the terms e Cm -δ (m-m * ) and e Cm -δ (m * -m) form a geometrically decreasing series with rate e -Cm -δ . Since |mH((

m a + 1)/m) -mH(m a /m)| ≤ log m, the term exp[-Cm -δ |n -m log n/h -μm + m(H(m a /m)/h -1)|]]
is at most geometrically increasing with a rate e m -δ log m/h which is smaller than e Cm -δ . Therefore, the whole series has its maximum at m a = m * and

K c m,n (0) ≤ 2B 2 k=0 ∞ e -Ck(m -δ -log m/hm -δ ) × exp[-Cm -δ |n -m log n/h -μm + m(H(m * /m)/h -1)|]] = 2B 2 1 -e -(m -δ -log m/hm -δ )C × exp[-Cm -δ |n -m log m/h -μm + m(H(m * /m)/h -1)|]] = O(2B 2 m δ ) exp[-Cm -δ |n -m log m/h -μm + m(H(τ )/h -1)|]].
Including all contributions, the final estimate for some B > 0 is

P c m,n ≤ B m 1+δ exp[-Cm -δ |n -m log m -μm + m(H(τ )/h -1)|].

Conclusions

In this paper we analyze the Lempel-Ziv'78 algorithm for binary Markov sources, a problem left open since the algorithm inception. To handle the strong dependency between Markov phrases, we introduce and precisely analyze the so called tail symbol which is the first symbol of the next phrase in the LZ78 parsing. We focus here on the large deviations for the number of phrases in the LZ78 and also give a precise asymptotic expression for the redundancy which is the excess of LZ78 code over the entropy of the source. In future work we plan to extend our analysis to non-binary Markov sources and present some bounds on the central limit theorem. Furthermore, we shall study LZ78 for Markov sources of higher order, however, this will require a new approach to the tail symbols which may span over consecutive phrases.

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.

(A.8)

We finally have lim

s→-1 x(s) = Pe a -π a 1 - 1 λ (-1)
1 π (-1) + πQ (-1) (I -P)Pe a , (A.9)

where π a is the coefficient of the stationary distribution π at 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 m ]. The inverse Mellin transform is Xc (z) = 1 2iπ x+i∞ x-i∞ X * c (s)z -s ds (A.10) 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. (A.11)
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 is

-z Pe a -π a 1 - 1 λ (-1)
1 π (-1) + πQ (-1) (I -P)Pe a . (A.12)

Therefore we have

X(z) = z π a + 1 λ (-1) 1 π (-1) + πQ (-1) (I -P)Pe a 1 + o(z). (A.13)
For irrational case, we know that s = -1 is the 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 hte 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 3(i).

A o f A 2 0 2 0 15:18 Lempel-Ziv'78 for Markov Sources

B Proof of Theorem 3(ii): Variance

We now analyze asymptotically V(z) = (V a (z), V b (z)) that satisfies the system of differentialfunctional equations [START_REF] Knuth | The Art of Computer Programming Sorting and Searching[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] 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] Knuth | The Art of Computer Programming Sorting and Searching[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 ). 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 | Anaylytical depoissonization and its applications[END_REF].

V c (z) = V c (ρz)e -z(1-ρ) + e -z
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 ( 8) 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 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 [START_REF] Szpankowski | Average Case Analysis of Algorithms on Sequences[END_REF] 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 14. We have V(z) = ωa 1z + o(z) in the aperiodic case, and in the periodic case V(z) = ωa 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

  Figure 1The DST-model vs LZ-model. In the DST-model we inserted eight (infinite) strings:X 1 = abb • • • , X 2 = abb • • • , X 3 = bbba • • • , X 4 = abaaa • • • , X 5 = bbaa • • • , X 6 = baaa • • • , X 7 = bbba • • • and X 8 = abbbb • • • ,where bold symbols denote DST tail symbols. In the LZ-model we parsed one string X = ()(a)(ab)(b)(aaba)(bb)(bbb)(abb) with bold denoting LZ tail symbols.

Figure 2

 2 Figure 2 The difference E[L c m ] -E[L c m ] by simulation confirming that it grows linearly with m.

  Theorem 5 presented below by showing that E[L c m ] -E[L c m ] = Θ(m), unlike in the memoryless case.

Theorem 5 .

 5 Figure 2 compares the difference E[L c m ] -E[L c m ] obtained by simulation results confirming our theoretical findings. For m given, let m * := m * (m) be the root of x -xτ (x) -(m -x)τ (m -x). (i) The average length E[L c m ] of the LZ-sequence consisting of the first m phrases is (for the aperiodic case)

6 .

 6 Our next goal is to present large deviation for the number of LZ phrases in the n-LZ model. Let M c n be the number of phrases obtained by parsing a Markovian sequence of length n starting with symbol c. By the renewal equation (1) we have P (M c n > m) = P (L c m < n) for all legitimate m and n. This allows us to read large deviation of M c n from Theorem 5. Following the footsteps of Theorem 2 of[START_REF] Jacquet | On the limiting distribution of lempel ziv'78 redundancy for memoryless sources[END_REF] we arrive at our next main result. For all δ > 1/2 there exist B, C, β, and γ all strictly positive such thatP |M c n --1 c (n)| ≥ xn δ ≤ Bn γ e -xCn β where -1 c (.) is the inverse function of c (m) = (m)+o(1) defined as (m) = m h (log m + β(m)) with β(m) = hµ(m * )m * /m + hµ(m -m * )(m -m * )/m -h + H(m * /m)where m * is defined in Theorem 5 and µ(m) has extra fluctuating function in the periodic case.

  By taking the blocks (phrases) starting with c = a we find t a a (s) = (a, b, b) and the blocks starting with b yield t b a (s) = (a, b).

  ),n-na . We now partition A m into four sets S c 0 (m), S c 1 (m), S c 2 (m) and S c 3 (m): s ∈ S c 0 (m): if neither of the initial symbol c or the final symbol of s, namely c m is identical to a. Thus the total number of tail symbols equal to a, namely |s| a is equal to |t a c (s)|. s ∈ S c 1 (m): if both the final symbol and c are equal to a so that the total number of tail (and initial) symbols equal to a is |t a c (s)|. s ∈ S c 2 (m): if c = a but c m = a so that the number of tail symbols equal to a is |t a c (s)| -1. s ∈ S c 3 (m): if c = a but the final symbol c m = a. Thus the number of tail symbols equal to a is |t a c (s)| + 1. Regrouping we have

  ) is proved. And finally with T 3 (m) as the set of pairs of sequence (t a , t b ) such that |t a | + |t b | = m and |t a | a + |t b | a = |t a | + 1, we establish the third term of (18).

  the E[T c m ] by τ c (m)m and E[L c m ] by m log m/h + m + mµ c (m) we arrive atK c m,n (0) ≤ B 2 m ma+m b =m exp -Cm -δ |m a -m a τ a (m a ) -m b τ b (m b )| × exp -Cm -δ |n -m log m/h + m(H(m a /m)/h -1) -m a µ a (m a ) -m b µ b (m a )| .Without changing the order of magnitude we further can replace τ c (m) by τ (m) and µ c (m) by µ(m).

  This gives the large deviation estimate and E[L c m,n ] = m log m/h + μm -m(H(τ )/h -1) + O(m δ ) by Fact 1. We recognize in H(τ ) the entropy of the tail symbol. In fact the quantities τ (m) and µ(m) are not exactly τ m and mμ. To handle it we observe that due to their slowly varying properties, the function exp(-Cm -δ |m a -τ (m a )m a -τ (mm b )(m -m a )| attains the maximum for m * such that m * = -τ a (m * )m * -τ b (m * )(m -m * ). Indeed the function m a -E[T a ma ] -E[T b m b ] is strictly increasing thus this value is unique. Then again E[L c m ] = m log m/h + m * µ(m * ) + (m -m * )µ(m -m * ) -m(H(m * /m)/h -1), and therefore E[L c m ] + mH(m * /m) + o(m). The latter is equal to E[L c m ] + mH(τ ) + o(m) in the aperiodic case. To complete the proof of Theorem 5 we just use Fact 1 applied to L m .

  z ρz e x (V a (P (a|c)x) + V b (P (b|c)x) + g(x)) dx(B.14) where g(z) = P (a|c) -P 2 (a|c) + [X c z (z)] 2 = O(1). Indeed, it follows from Fact 1 of [3] that the differential equation like f (z) = b(z) -a(z)f (z) (B.15) satisfies f (z) = f (z 0 )e A(z0)-A(z) + z z0 b(x)e A(x)-A(z) dx where A(z) = a(z) is the primitive function of a(z). Setting in (B.15) 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 (B.14

1 - 1 -Lemma 13 .

 1113 = 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 12. 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 = 1-is 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) becomesB(-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 Pe a = πe a Pe a .The real issue here is how to compute B (-2) and G (-1), which we address next. 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 where s n = Γ(s+n) Γ(s) = (s + n -1) × • • • × s.

  n)Ψ(s) (s + n)Γ(s) = (-1) n-1 n!where Ψ(s) is the psi function.

  π (-1)((P -I)Pe a + π(B (-2) + G (-1)) + πe a . (B.16) Notice that ω = B(-1) + Pe a . A o f A 2 0 2 0

Jacquet and W. Szpankowski 15:11 Proof.

  We naturally have P c m,n = |s|=m P c s,n where |s| is the length of the sequence s. Similarly we have P c m,k,n = t,|t|=m,|t|a=k P c t,n with |t| a is the number of symbols identical to a in t. The rest follows from Lemma 10 but we need to take into account some boundary effects. Let's look at it in more details. By (17) and above we find

	Lemma 11. The following holds
	P c m,n ≤	P a ma,k,na P b m-ma,ma-k,n-na	(18)
	na k ma
	+P a ma,k,na P b

m-ma,ma-k-1,n-na + P a ma,k,na P b m-ma,ma-k+1,n-na where n a is the total path length of the first m a phrases starting with an "a". P.

Funding Wojciech Szpankowski: This work was supported by NSF Center for Science of Information (CSoI) Grant CCF-0939370, and in addition by NSF Grant CCF-1524312.

Acknowledgements

We thank Guillaume Duboc for simulation of LZ78 scheme resulting in Figure 2.

A Proof of Theorem 3(i): Mean

We first analyze asymptotically X(z) = (X a (z), X b (z)) that satisfies the system of differentialfunctional equations [START_REF] Jacquet | Analytic Pattern Matching: From DNA to Twitter[END_REF]. We solve this system, and then apply Mellin transform and depoissonization to prove Theorem 3(i).

Since for all integer m, we have T c m ≤ m, 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 defined as X c (s) = ∞ 0 X c (z)z s-1 dz (see [START_REF] Szpankowski | Average Case Analysis of Algorithms on Sequences[END_REF] for more on the Mellin transform). To correct this we introduce Xc

are defined in [START_REF] Jacquet | Average profile of hte lempel-ziv parsing scheme for a markovian source[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] P. Jacquet and W. Szpankowski 15:15

where G * c (s) for c ∈ A is the Mellin transform of G c (z) and has the explicit expression

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), c ∈ A which is also the Mellin transform of the vector X(z) made of the coefficients Xc (z). This yields the linear equation

where G * (s) is the vector of the G * c (s). It can be rewritten in

This kind of equation has been studied in [START_REF] Jacquet | Average profile of hte lempel-ziv parsing scheme for a markovian source[END_REF] where we introduce a new function x(s)

Thus the equation becomes x(s -1) = (I -P(s))x(s), which leads to x(s) = i≥0 (I -P(si)) -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

To handle it we need an explicit formula for x(-2). The following lemma from [START_REF] Jacquet | Average profile of hte lempel-ziv parsing scheme for a markovian source[END_REF] is useful in this regard. We provide a proof for completeness. Lemma 12. Let {f n } ∞ n=0 be a sequence of real numbers having the Poisson transform

which is an entire function. Furthermore, let its Mellin transform F (s) have the following factorization

Assume that F (s) exists for (s) ∈ (-2, -1), and that γ(s) is analytic for (s) ∈ (-∞, -1). Then

Proof. Notice that f n and fn are related by [START_REF] Szpankowski | Average Case Analysis of Algorithms on Sequences[END_REF] fn =

A o f A 2 0 2 0 15:16 Lempel-Ziv'78 for Markov Sources Define for some fixed M ≥ 2, the function

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

thus by the inverse Mellin transform, we have

Comparing (A.4) and (A.5) shows that γ(-M ) = (-1)

Now we can compute x(-2) using above and (7) leading to

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) 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) = 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


Andrés Mauricio Ramírez
email: andres.ramirez@umayor.cl

Linda Cattin

Jean-Christian Bernè
email: jean-christian.bernede@univ-nantes.fr

Fernando Raúl Díaz

Manuel Alejandro Gacitúa
email: manuel.gacitua@usach.cl

María Angélica Del Valle

Nanostructured TiO 2 and PEDOT Electrodes with Photovoltaic Application

Keywords: dye-sensitized solar cell, electropolymerization, poly(3,4-ethylenedioxythiophene), polymer nanowires, solar cell, titanium dioxide

In this work, nanostructured TiO 2 and poly-3,4-ethylenedioxythiophene (PEDOT) layers were electrochemically prepared over transparent electrodes. Morphological characterization evidenced the presence of nanostructures as planed with 50-nm-wide TiO 2 rod formations followed by 30-nm-wide PEDOT wires. Different characterizations were made to the deposits, establishing their composition and optic properties of the deposits. Finally, photovoltaic cells were prepared using this modified electrode, proving that the presence of PEDOT nanowires in the cell achieves almost double the efficiency of its bulk analogue.

Introduction

Global warming is a current global concern known to be, in part, tightly linked to the large dependence of humans on non-renewable fossil-fuel-based energy sources involving the release of greenhouse gases. If renewable clean energy sources remain expensive, it will not be possible to reduce or stop global warming and its consequences. A valid strategy to lower the costs of clean-energy-harvesting devices, such as photovoltaic cells, could be to incorporate low-cost and more efficient materials, such as conducting polymers (CPs). This class of polymers has shown interesting electronic and optical properties, while maintaining feasible handling of plastics [START_REF] Eftekhari | Polyaniline supercapacitors[END_REF], with applications in supercapacitors, lightemitting diodes, electrochromic and photosensitive devices, sensors, batteries, transistors, fuel cells, electrocatalysis, and photovoltaics, among others [START_REF] Bagheri | Conductive polymer-based microextraction methods: A review[END_REF][START_REF] Abaci | Morphological and electrochemical properties of PPy, PAni bilayer films and enhanced stability of their electrochromic devices (PPy/PAni-PEDOT, PAni/PPy-PEDOT)[END_REF][START_REF] Wang | Organic/inorganic hybrid sensors: A review[END_REF][START_REF] Baker | Polyaniline nanofibers: Broadening applications for conducting polymers[END_REF][START_REF] Huang | Nanostructured Polypyrrole as a flexible electrode material of supercapacitor[END_REF][START_REF] Salgado | Selective electrochemical determination of dopamine, using a poly(3,4ethylenedioxythiophene)/polydopamine hybrid film modified electrode[END_REF][START_REF] Zhao | Glucose Sensing by Glucose Oxidase/PEDOT Thin Film Electrode[END_REF][START_REF] Hernández | Electrosynthesis and characterization of nanostructured polyquinone for use in detection and quantification of naturally occurring dsDNA[END_REF][START_REF] Friend | Electroluminescence in conjugated polymers[END_REF][START_REF] Nelson | Polymer: Fullerene bulk heterojunction solar cells[END_REF][START_REF] Mayer | Polymer-based solar cells[END_REF][START_REF] Liu | A solar rechargeable battery based on polymeric charge storage electrodes[END_REF][START_REF] Bhattacharya | Rechargeable electronic textile battery[END_REF][START_REF] Valle | Electro-synthesis and characterization of polythiophene nanowires/platinum nano-particles composite electrodes. Study of formic acid electro-catalytic oxidation[END_REF][START_REF] Valle | Nanowires and Platinum Nanoparticles Modified Electrodes to be Assayed in Formic Acid Electro-oxidation[END_REF][START_REF] Ramírez | Enhancement of electrodes modified by electrodeposited PEDOT-nanowires with dispersed Pt nanoparticles for formic acid electro-oxidation[END_REF].

CPs have proven their potential usefulness in energy-harvesting devices, and could be enhanced by a higher control of their morphology. A method using solely electrochemical perturbations has been developed ( [START_REF] Valle | Electrosynthesis of Polymer Nanowires Directly onto Solid Surfaces (Electrodes)[END_REF][START_REF] Valle | Electrosynthesis of polythiophene nanowires via mesoporous silica thin film templates[END_REF][START_REF] Valle | Electrosynthesis and Characterization of Poly(3,4-ethylenedioxythiophene) Nanowires[END_REF][START_REF] Valle | Influence of the Supporting Electrolyte on the Electrochemical Polymerization of 3,4-Ethylenedioxythiophene. Effect on p-and n-Doping/Undoping, Conductivity and Morphology[END_REF][START_REF] Ramírez | Electrochemical in situ synthesis of polypyrrole nanowires[END_REF]; 10.1007/s11581-016-1796-9) as a solution for controlling the deposition process and electrode morphology, suitable for the reproducible construction of nanostructured semiconducting polymer layers.

With respect to CP application in solar cells, most successful outcome corresponds to the incorporation of a doped poly-3,4-ethylenedioxythiophene (PEDOT) coating in a multiple-layer organic solar cell configuration. PEDOT is recognized as an excellent buffer layer material and some studies have revealed that it is possible to use it as an anode in a multiple-layer solar cell configuration [START_REF] Rahman | ITO-free low-cost organic solar cells with highly conductive poly(3,4 ethylenedioxythiophene): P-toluene sulfonate anodes[END_REF]. Nevertheless, the performance of cells using this type of material, and other CPs, is limited by the imperfect connections (empty spaces) of a multiple-layer configuration. Short cuts, misguided excitons, and energy loss due to dissipative forces are some of the failure sources encountered when assembling these types of device [START_REF] Krebs | Degradation and stability of polymer and organic solar cells[END_REF][START_REF] Jørgensen | Stability/degradation of polymer solar cells[END_REF]. A way to solve this problem is the incorporation of a nanostructured heterojunction assembly; nanostructured or nanowired (nw) assembly provides an enhanced surface-contact area while avoiding empty spaces between layers, and directs exciton movement correctly [START_REF] Günes | Conjugated Polymer-Based Organic Solar Cells[END_REF].

In previous studies, we have verified that PEDOT-nw displays better performance on other types of device, such as fuel cells [START_REF] Valle | Nanowires and Platinum Nanoparticles Modified Electrodes to be Assayed in Formic Acid Electro-oxidation[END_REF]. Thus, it seems convenient to further test PEDOT-nw incorporation in the design of anodes for solar cells. In addition, some reports indicate that the previous addition of a semiconducting oxide layer as anatase (TiO 2 ) followed by an appropriate sensitizer dye can enhance multiple-layer solar cell performance [START_REF] Karuppuchamy | Cathodic electrodeposition of oxide semiconductor thin films and their application to dye-sensitized solar cells[END_REF].

In the present study, transparent indium-doped tin oxide (ITO) electrodes are sequentially modified with layers of TiO 2 , sensitizer dye, mesoporous silica template, and nanowired PEDOT. Then, these electrodes are employed in the design of multiple-layer photovoltaic cells [START_REF] El Jouad | Ca/Alq3 hybrid cathode buffer layer for the optimization of organic solar cells based on a planar heterojunction[END_REF][START_REF] Barkat | Efficient hole-transporting layer MoO 3 :CuI deposited by co-evaporation in organic photovoltaic cells[END_REF]. It is worth noting that most preparative methods are based on electrochemical techniques which ensures low cost and reproducible results. The main objective of the present report is to demonstrate that the electrochemical method enables sufficient control to produce a nanostructured conducting polymer layer over electrodes and to check if these deposits have advantages in terms of the performance of photovoltaic cells constructed with them [START_REF] El Jouad | Improving the efficiency of subphthalocyanine based planar organic solar cells through the use of MoO 3 /CuI double anode buffer layer[END_REF].

Materials and Methods

Electrode Modification

Electrochemical studies were carried out in a high-purity Ar atmosphere at room temperature (20 • C), in a three-compartment anchor cell, using a Pt wire with an area 20 times greater than that of the respective working electrodes. A reference wire of Ag|AgCl in tetramethylammonium chloride solution, with potential adjustment to that of the saturated calomel electrode (SCE) was used as the reference electrode [START_REF] East | Easy-to-Make Ag/AgCl Reference Electrode[END_REF]. The working electrode was glass coated with indium-doped tin oxide (ITO) of 0.21 cm 2 geometric area and sheet resistance of ≤10 Ω sq -1 .

ITO modification with TiO 2 was done in a single compartment cell, from titanium oxysulfate 0.020 mol L -1 (TiOSO 4 99.9%, Aldrich, Santiago, Chile), as a precursor to titanium oxide; hydrogen peroxide 0.030 mol L -1 (H 2 O 2 30% v/v, Merck, Santiago, Chile) and potassium nitrate (KNO 3 , 99.0%, Merck), as a supporting electrolyte, in Milli-Q water, at pH 1.8 at 10 • C. The electro-obtaining of TiO 2 was carried out by potentiostatic perturbance at -1.1 V for 300 s. Subsequently, the modified electrode was heat-treated at 500 • C for 1 h, following the heating ramp at 8 • C min -1 . Then, the ITO|TiO 2 electrodes were modified by immersing the electrode in a 1.0 × 10 -4 mol L -1 N3 dye solution, for 24 h and then washed with acetone. N3 solutions corresponded to commercial cisbis(isothiocyanate)-bis(2,2 -bipyridyl-4,4 -dicarboxylate)ruthenium(II) (C 26 H 16 N 6 O 8 RuS 2 , N3) in ethanol. Thus, ITO|TiO 2 |N3 electrodes were obtained.

Incorporation of nanowired (PEDOT-nw) conducting polymer requires an early silica template preparation stage [10.1016/j.elecom.2020.106896] over the ITO|TiO 2 |N3 electrodes. Precursor solution for the silica template was prepared as follows: sodium nitrate 0.1 mol L -1 (NaNO 3 99.0%, Merck) as supporting electrolyte, tetraethyl orthosilicate 0.0034 mol L -1 ((C 2 H 5 O) 4 Si, 99.999%, Aldrich) as a precursor to silicon oxide and hexadecyltrimethylammonium bromide 0.115 mol L -1 as surfactant (CTAB, C 19 H 42 BrN, 95%, Aldrich), in ethanol 50% v/v (ethanol/Milli-Q = 1:1) under vigorous stirring for 2.5 h. Mesoporous silica template was prepared by immersing the ITO|TiO 2 |N3 electrodes in this solution and application of a potential step between -1.100 and -1.400 V. This modified electrode was washed with abundant Milli-Q water and dried in an oven for 24 h at 130 • C, to generate a thin film of SiO 2 . Next, the CTAB micelles were removed by immersing the electrodes for 15 min in acidified ethanolic solution under stirring. Then, the electrochemical growth of PEDOT nanowires took place inside the nano-channels of this template-modified electrode ( [START_REF] Valle | Electrosynthesis of Polymer Nanowires Directly onto Solid Surfaces (Electrodes)[END_REF][START_REF] Valle | Electrosynthesis of polythiophene nanowires via mesoporous silica thin film templates[END_REF][START_REF] Valle | Electrosynthesis and Characterization of Poly(3,4-ethylenedioxythiophene) Nanowires[END_REF][START_REF] Valle | Influence of the Supporting Electrolyte on the Electrochemical Polymerization of 3,4-Ethylenedioxythiophene. Effect on p-and n-Doping/Undoping, Conductivity and Morphology[END_REF][START_REF] Ramírez | Electrochemical in situ synthesis of polypyrrole nanowires[END_REF]; 10.1007/s11581-016-1796-9). The electrochemical polymerization of 3,4-ethylenedioxythiophene (EDOT) was performed in a working solution containing monomer 0.010 mol L -1 (Aldrich) and support electrolyte 0.100 mol L -1 (tetrabutylammonium hexafluorophosphate, TBAPF 6 , Aldrich 99%), in acetonitrile (CH 3 CN 99.9%, Merck); the technique employed in this case was cyclic voltammetry (CV). Successive potentiodynamic scans were applied between -1.000 and 1.600 V on electrodes with and without the silica template for preparation of bulk and nanowired polymeric deposits. A scan rate of 0.1 V s -1 was used considering 5 and 1 potentiodynamic cycles for production of bulk PEDOT and PEDOT-nw, respectively. To remove the silica template and expose the nanowires, electrodes were immersed in 0.5 mol L -1 NaOH solution for 15 min, rinsed with 5% m/v NaHCO 3 and finally with distilled water. Therefore, the ITO|TiO 2 |N3|PEDOT and ITO|TiO 2 |N3|PEDOT-nw electrodes were obtained. A schematic summary of the preparative methods can be seen in Figure 1.

Characterization

Surface morphology of the prepared electrodes was studied using scanning electron microscopy (SEM) Inspect F50 SEM or JOEL model 7600F (Nantes, France).

Identification of TiO 2 deposit in its anatase form was confirmed by X-ray diffractometry (XRD) obtained on a Siemens D5000 spectrometer (Nantes, France) using Cu radiation (λKα 0.15406 nm) in an interval of 20 to 60 2θ and X-ray photoelectron spectroscopy using a Kratos Analytical AXIS Nova spectrometer, with an Al excitation line (Kα 14.866 eV) in an interval between 0 and 1.200 eV, analyzing the data with CasaXPS software (Nantes, France).

Electrochemical modifications and characterization of electrodes were made using a CH Instruments potentiostat/galvanostat controlled by CH750D software. UV-Vis spectra were recorded on a Specord 40 spectrophotometer (Analytik Jena, Thuringia, Germany), between 300 and 800 nm.

Solar cells were assembled following the methodology proposed by Bernéde et al. [START_REF] Barkat | Efficient hole-transporting layer MoO 3 :CuI deposited by co-evaporation in organic photovoltaic cells[END_REF][START_REF] El Jouad | Improving the efficiency of subphthalocyanine based planar organic solar cells through the use of MoO 3 /CuI double anode buffer layer[END_REF]. The photovoltaic characterization of the solar cells was carried out in an unautomated I-V under darkness and lighting, using a global solar simulator AM1.5 (Oriel 300 W, Nantes, France), with an intensity of 100 mW cm -2 , which was adjusted with a reference photovoltaic cell (CIGS 0.5 cm 2 PV, calibrated in NREL, Denver, CO, USA).

Results and Discussion

Before template and nanowire deposition, a layer of TiO 2 in its anatase form was required to enhance the photocell performance. Morphological characterization is presented in Figure 2. Morphological characterization revealed rod-like formations of TiO 2 over ITO surface after 300 s electrolysis time. From the pictures (Figure 2A,B), the rods were on average 50 and 300 nm in width and height, respectively, and rod density was calculated as being near 2.1 × 10 7 per mm 2 .

Other characterizations were considered. XRD characterization (Figure S1 in Supplementary Materials) showed expected results for the formation of anatase after 60 s deposition time displaying typical crystallographic signals [START_REF] Natarajan | Cathodic Electrodeposition of Nanocrystalline Titanium Dioxide Thin Films[END_REF], and the (101) phase became favored with electrolysis time. There was a small shift of TiO 2 signals at the diffractograms, attributed in the literature to a strain resulting from planar stress very likely in thin-layer electrochemical deposits [START_REF] Cullity | Elements of X-ray Diffraction[END_REF]. XPS analysis of the samples (Figure S2 in Supplementary Materials) showed signals of around 459.5 (Ti 2p 1/2 ) and 465.5 (Ti 2p 3/2 ) eV from the Ti-O interaction.

Afterwards, these electrodes were further modified with a dye to improve contact between TiO 2 and the subsequent PEDOT layers. Bulk PEDOT and PEDOT nanowires were then electrochemically polymerized using a methodology published in past reports [START_REF] Valle | Nanowires and Platinum Nanoparticles Modified Electrodes to be Assayed in Formic Acid Electro-oxidation[END_REF][START_REF] Ramírez | Enhancement of electrodes modified by electrodeposited PEDOT-nanowires with dispersed Pt nanoparticles for formic acid electro-oxidation[END_REF][START_REF] Valle | Electrosynthesis of Polymer Nanowires Directly onto Solid Surfaces (Electrodes)[END_REF][START_REF] Valle | Electrosynthesis and Characterization of Poly(3,4-ethylenedioxythiophene) Nanowires[END_REF] (Figure 3). From the micrographs (Figure 3A,B), it can be seen that the polymer grows between the TiO 2 structures with excellent cohesion for the hetero junction. Bulk PEDOT (Figure 3A) displays a homogeneous morphology, fills gaps between the TiO 2 rods, and finishes with a smooth surface. On the other hand, nanostructured PEDOT, or PEDOT-nw (Figure 3B), displays nanometric wire morphology. PEDOT-nw shows wires with an average 30-nm width and, from micrograph analysis, a nanowire density of approximately 90,000 wires per µm 2 can be calculated. To predict the behavior of the photocells, the energy diagrams of the respective modified electrodes, ITO|TiO 2 |PEDOT and ITO|TiO 2 |PEDOT-nw, were constructed (Figure S3 in Supplementary Materials) [START_REF] Gelderman | Flat-Band Potential of a Semiconductor: Using the Mott-Schottky Equation[END_REF]. Electrochemical impedance spectroscopy measurements were made on electrodes in 0.1 mol L -1 LiCl solution, at 1 kHz to obtain Mott-Schottky graphs where flat band potential, Vfb, was calculated for TiO 2 , PEDOT and PEDOT-nw, finding values of -0.58, 0.674 and 0.113 V vs. SCE, respectively, which are consistent with those reported in the literature [START_REF] Chettah | Electrosynthesis of TiO 2 oxide film on ITO substrate and electrochemical comparative study of the oxide with its hydrated gel[END_REF][START_REF] Boix | Open-Circuit Voltage Limitation in Low-Bandgap Diketopyrrolopyrrole-Based Polymer Solar Cells Processed from Different Solvents[END_REF][START_REF] Gomes | Schottky barrier diodes from semiconducting polymers[END_REF]. Thus, TiO 2 showed a positive slope, which indicates the presence of an n-type semiconductor. On the other hand, PEDOT and PEDOT-nw negative slopes were found, accounting for a p-type semi-conductor. From these slopes, using Equations ( 1) and ( 2) [START_REF] Gelderman | Flat-Band Potential of a Semiconductor: Using the Mott-Schottky Equation[END_REF], it is possible to calculate the apparent density of carriers, for the different semi-conductors, where N D and N A are the number of donors and acceptors for n-type and p-type semi-conductors, respectively.

N D = 2 ε•ε 0 •e• A 2 •P MS (1)
N A = - 2 ε•ε 0 •e• A 2 •P MS (2)
Here, P MS is the value of the slope, e is the charge of the electron, ε 0 and ε are the dielectric constant in vacuum and the dielectric constant of the semiconductor, considering values of 100 and 600,000 for TiO 2 [START_REF] Kim | High dielectric constant TiO 2 thin films on a Ru electrode grown at 250 • C by atomic-layer deposition[END_REF] and PEDOT [START_REF] Basavaraja | Morphology and electrical properties of poly(3,4-ethylenedioxythiophene)/titanium dioxide nanocomposites[END_REF], respectively, and A is the area. Therefore, the calculated values of 6.057 × 10 19 , 8.246 × 10 17 and 1.107 × 10 17 cm -3 are obtained for the respective TiO 2 , PEDOT and PEDOT-nw electrodes. These values are also consistent with those reported for these semiconductors [START_REF] Wu | Photoelectrocatalytic degradation Rhodamine B over highly ordered TiO2 nanotube arrays photoelectrode[END_REF][START_REF] Kirchartz | Sensitivity of the Mott-Schottky Analysis in Organic Solar Cells[END_REF][START_REF] Boix | Determination of gap defect states in organic bulk heterojunction solar cells from capacitance measurements[END_REF]. Using the Tauc transformation [START_REF] Tauc | Optical properties and electronic structure of amorphous Ge and Si[END_REF], from the UV-Vis spectra (Figure S3, inserts at D,E,F in Supplementary Materials) the band gaps of the respective modified electrodes are determined, obtaining values of 3.65, 2.31 and 2.56 eV for TiO 2 , PEDOT and PEDOT-nw, respectively. The increase in the band gap of PEDOT-nw with respect to PEDOT is attributed or accounts for the quantum confinement of the nano-structured material.

As has been proven in past reports [START_REF] Brovelli | Electrochemical and optical studies of 1,4diaminoanthraquinone for solar cell applications[END_REF], direct electro-synthesized conducting polymer deposit may show an imperfect connection between the semiconducting layers (short circuit). To improve cell performance, a layer of N3 dye was placed between the TiO 2 and conducting polymer; this dye would also inject a significant amount of electron-hole pairs into the system, generating better efficiency as described in the literature [START_REF] O'regan | A low-cost, high-efficiency solar cell based on dye-sensitized colloidal TiO 2 films[END_REF]. The V values for each layer were transformed into eV in vacuum [START_REF] Trassatti | The absolute electrode potential: An explanatory note[END_REF]. It should be noted here that organic semiconductors have flat band potential, corresponding to the bipolaron band, 0.70 eV above the HOMO level, unlike inorganic semiconductors, which have flat bands at 0.06 eV [START_REF] Gelderman | Flat-Band Potential of a Semiconductor: Using the Mott-Schottky Equation[END_REF][START_REF] Yang | Evolution of polypyrrole band structure: A scanning tunneling spectroscopy study[END_REF]. The energy level for N3 was taken from the literature [START_REF] Furube | Near-IR transient absorption study on ultrafast electroninjection dynamics from a Ru-complex dye into nanocrystalline In2O3 thin films: Comparison with SnO 2 , ZnO, and TiO 2 films[END_REF], with -5.89 and -5.22 eV for HOMO and LUMO levels, respectively. With this information, band diagrams were constructed (Figure S4 in Supplementary Materials). These cells were then characterized based on their J-V performance, as shown in Figure 4.

At first sight, ITO|TiO 2 |N3|PEDOT-nw|Al electrodes show a higher current density than the modified ITO|TiO 2 |N3|PEDOT|Al electrodes. Table 1 summarizes the values corresponding to the photovoltaic characterization of these cells. The values in Table 1 show that nanowired PEDOT-based photovoltaic devices are practically twice as efficient as bulk polymer. Therefore, the selection of nanostructured presents advantages over bulk PEDOT deposits. Despite the fact that solar cell performance was not good, further studies will attempt optimizing through variation of nanowire length and/or diameter.

Conclusions

Electrochemical techniques are useful for the construction of nanostructured layers of photovoltaic cells such as TiO 2 and PEDOT. The TiO 2 layer was identified in its anatase form and showed a nanorod-ordered formation. Bulk and nanowired PEDOT deposits were successfully prepared over the initial TiO 2 layer. In particular, PEDOT nanowire showed expected morphology and disposition as presented in past reports.

To use these electrodes in photovoltaics, a layer of N3 dye was added between the TiO 2 layer and the conducting polymer. The photocell architecture ITO|TiO 2 |N3|PEDOT-nw|Al showed the best current density-potential performance during characterization, meaning that the use of a nanostructured heterojunction in multiple-layer solar cells improves the overall performance.

Patents

The authors applied for an international patent called "Electrosynthesis of polymeric nanowires directly on solid surfaces (electrodes)", with application numbers PCT/CL2018/ 050116 and reference 273176-WO.

Figure 1 .

 1 Figure 1. Schematic representation of preparative methods.

Figure 2 .

 2 Figure 2. Scanning electron microscopy (SEM) micrographs of indium-doped tin oxide (ITO)|TiO 2 after 300 s electrosynthesis time (A) top view and (B) cross section.

Figure 3 .

 3 Figure 3. Electrodes' morphological characterization. (A) ITO|TiO 2 |PEDOT and (B) ITO|TiO 2 |PEDOT-nw.

Figure 4 .

 4 Figure 4. Solar cell J-V characterization of (A) ITO|TiO 2 |N3|PEDOT|Al and (B) ITO|TiO 2 |N3|PEDOT-nw|Al.

Supplementary Materials:

  The following are available online at https://www.mdpi.com/2079-4 991/11/1/107/s1, Figure S1: X-Ray diffractograms of ITO|TiO2 electrodes prepared by potential step of -1.100 during: (A) 60; (B) 180; (C) 300, and (D) 600 s; Figure S2: XPS analysis of ITO|TiO2 electrodes prepared by potential step of -1.100 V during 300 s: (A) Scan interval; (B) Maximum level of Ti 2p, and (C) Core level; Figure S3: Mott-Schottky graphics measured at 1 kHz: (A) TiO2; (B) PEDOT, and (C) PEDOT-nw obtained in absence of light. Graphics of (hν α L)2 vs. hν of: (D) TiO2; (E) PEDOT, and (F) PEDOT-nw; Figure S4: Energy diagram of (A) ITO|TiO2|N3|PEDOT and (B) ITO|TiO 2 |N3|PEDOT|PEDOT-nw.

Table 1 .

 1 Current-voltage (J-V) characterization photocells using bulk and nanowired PEDOT layers.

	Deposited Layer	V OC /V	J SC /mA cm -2	% FF	% η
	PEDOT	0.48	6.0 × 10 -3	16.1	4.9 × 10 -4
	PEDOT-nw	0.39	1.0 × 10 -2	25.7	1.0 × 10 -3

Funding: This research was funded by ANID-Chile through Fondecyt, grant number Project N. 1190011.

Conflicts of Interest:

The authors declare no conflict of interest.

Author Contributions: Methodology, formal analysis, investigation, and writing-original draft preparation, A.M.R.; supervision, formal analysis, and investigation, L.C., J.-C.B. and F.R.D.; formal analysis, data curation, and writing-original draft preparation, M.A.G.; conceptualization, investigation, writing-review and editing, funding adquisition, and project administration, M.A.d.V. All authors have read and agreed to the published version of the manuscript.