Limiting distribution of Lempel Ziv'78 redundancy

Philippe Jacquet; Wojciech Szpankowski

doi:10.1109/isit.2011.6033794

Limiting distribution of Lempel Ziv'78 redundancy

Abstract

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.

Citations

3

CrossRef
0

Web of Science
4

Scopus

Authors (2)

Philippe Jacquet
- . .
Wojciech Szpankowski prof. dr inż.
- Purdue University Department of Computer Science

Cite as

Full text

full text is not available in portal

full content of the article see on external site open in new tab

Keywords

Details

Category:: Conference activity
Type:: publikacja w wydawnictwie zbiorowym recenzowanym (także w materiałach konferencyjnych)
Title of issue:: Information Theory Proceedings (ISIT), 2011 IEEE International Symposium on strony 1509 - 1513
Language:: English
Publication year:: 2011
Bibliographic description:: Jacquet P., Szpankowski W.: Limiting distribution of Lempel Ziv'78 redundancy// Information Theory Proceedings (ISIT), 2011 IEEE International Symposium on/ : IEEE, 2011, s.1509-1513
DOI:: Digital Object Identifier (open in new tab) 10.1109/isit.2011.6033794
Verified by:: Gdańsk University of Technology