Exact analysis of the Lempel-Ziv algorithm for unifilar Markov source

We find an exact formula of the expected length of the i-th parsed segment on a state dependent parsing tree which results from the state dependent Lempel-Ziv incremental parsing algorithm applied to a unifilar Markov source, Our expectation appears in the formulation of the rate of a variable-to-variable length Lempel-Ziv scheme. We argue its asymptotic behavior and prove a universal source coding theorem