We show that the Lempel Ziv'78 redundancy rate tends to a Gaussian distribution for memoryless sources. We accomplish it by extending findings from our 1995 paper [3]. We present a new simplified proof of the Central Limit Theorem for the number of phrases in the LZ'78 algorithm. As in our 1995 paper, here we first analyze the asymptotic behavior of the total path length in a digital search tree (a DST) built from independent sequences. Then we present simplified proofs and extend our analysis of LZ'78 algorithm to include new results on the convergence of moments, moderate and large deviations, and redundancy analysis.
Authors
- Philippe Jacquet,
- prof. dr inż. Wojciech Szpankowski link open in new tab
Additional information
- DOI
- Digital Object Identifier link open in new tab 10.1109/isit.2011.6033794
- Category
- Aktywność konferencyjna
- Type
- publikacja w wydawnictwie zbiorowym recenzowanym (także w materiałach konferencyjnych)
- Language
- angielski
- Publication year
- 2011
Source: MOSTWiedzy.pl - publication "Limiting distribution of Lempel Ziv'78 redundancy" link open in new tab