Average profile of the Lempel-Ziv scheme for a Markovian source

We consider the Lempel-Ziv (1978) parsing scheme (LZ´78) which parses a sequence into phrases such that the next phrase is the shortest phrase not seen in the past. Two models called further digital tree model and Lempel-Ziv model are of interest. The former asks for the length of the Lempel-Ziv string composed of m phrases. The latter assumes that the string is of fixed length, say n, and investigates the number of phrases generated by the scheme. We are interested in the average profile which is defined as the average number of phrases of a given size. The average profile is related to the length of a randomly selected phrase which we denote either as D_m, for the digital tree model or as D_n^LZ for the Lempel-Ziv model. Thus, we concentrate on studying D_m, and D_n^LZ . More precisely, we investigate the fine structure (i.e., second-order properties) of these parameters for a Markovian source over a finite alphabet Σ of size V