DocumentCode :
3503739
Title :
Limiting distribution of Lempel Ziv´78 redundancy
Author :
Jacquet, Philippe ; Szpankowski, Wojciech
Author_Institution :
INRIA, Le Chesnay, France
fYear :
2011
fDate :
July 31 2011-Aug. 5 2011
Firstpage :
1509
Lastpage :
1513
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.
Keywords :
Gaussian distribution; memoryless systems; source coding; tree searching; DST; Gaussian distribution; Lempel Ziv´78 redundancy rate analysis; central limit theorem; digital search tree; independent sequence; limiting distribution; memoryless source; path length; Algorithm design and analysis; Convergence; Gaussian distribution; Information theory; Limiting; Manganese; Redundancy;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Information Theory Proceedings (ISIT), 2011 IEEE International Symposium on
Conference_Location :
St. Petersburg
ISSN :
2157-8095
Print_ISBN :
978-1-4577-0596-0
Electronic_ISBN :
2157-8095
Type :
conf
DOI :
10.1109/ISIT.2011.6033794
Filename :
6033794
Link To Document :
بازگشت