Ergodic behavior of graph entropy
Authors:
John Kieffer and Enhui Yang
Journal:
Electron. Res. Announc. Amer. Math. Soc. 3 (1997), 1116
MSC (1991):
Primary 28D99; Secondary 60G10, 94A15
Published electronically:
March 12, 1997
MathSciNet review:
1433180
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: For a positive integer , let be the vector formed by the first samples of a stationary ergodic finite alphabet process. The vector is hierarchically represented via a finite rooted acyclic directed graph . Each terminal vertex of carries a label from the process alphabet, and can be reconstituted as the sequence of labels at the ends of the paths from root vertex to terminal vertex in . The entropy of the graph is defined as a nonnegative real number computed in terms of the number of incident edges to each vertex of . An algorithm is given which assigns to a binary codeword from which can be reconstructed, such that the length of the codeword is approximately equal to . It is shown that if the number of edges of is , then the sequence converges almost surely to the entropy of the process.
 1.
Thomas
M. Cover and Joy
A. Thomas, Elements of information theory, Wiley Series in
Telecommunications, John Wiley & Sons Inc., New York, 1991. A
WileyInterscience Publication. MR 1122806
(92g:94001)
 2.
J. Kieffer and E.H. Yang, ``A complexity reduction method for lossless source code design,'' Technical Report, Dept. of Electrical Engineering, University of Minnesota Twin Cities, 1995 (http://www.ee.umn.edu/users/kieffer).
 3.
J. Kieffer, E.H. Yang, G. Nelson, and P. Cosman, ``Lossless compression via bisection trees,'' Technical Report, Dept. of Electrical Engineering, University of Minnesota Twin Cities, 1996 (http://www.ee.umn.edu/users/kieffer).
 4.
J. Kieffer, G. Nelson, and E.H. Yang, ``Tutorial on the quadrisection method for lossless data compression,'' Technical Report, Dept. of Electrical Engineering, University of Minnesota Twin Cities, 1996 (http://www.ee.umn.edu/users/kieffer).
 5.
Abraham
Lempel and Jacob
Ziv, On the complexity of finite sequences, IEEE Trans.
Information Theory IT22 (1976), no. 1, 75–81.
MR
0389403 (52 #10234)
 1.
 T. M. Cover and J. A. Thomas, Elements of information theory, Wiley, New York, 1991. MR 92g:94001
 2.
 J. Kieffer and E.H. Yang, ``A complexity reduction method for lossless source code design,'' Technical Report, Dept. of Electrical Engineering, University of Minnesota Twin Cities, 1995 (http://www.ee.umn.edu/users/kieffer).
 3.
 J. Kieffer, E.H. Yang, G. Nelson, and P. Cosman, ``Lossless compression via bisection trees,'' Technical Report, Dept. of Electrical Engineering, University of Minnesota Twin Cities, 1996 (http://www.ee.umn.edu/users/kieffer).
 4.
 J. Kieffer, G. Nelson, and E.H. Yang, ``Tutorial on the quadrisection method for lossless data compression,'' Technical Report, Dept. of Electrical Engineering, University of Minnesota Twin Cities, 1996 (http://www.ee.umn.edu/users/kieffer).
 5.
 A. Lempel and J. Ziv, On the complexity of finite sequences, IEEE Trans. Inform. Theory, 22 (1976), 7581. MR 52:10234
Similar Articles
Retrieve articles in Electronic Research Announcements of the American Mathematical Society
with MSC (1991):
28D99,
60G10,
94A15
Retrieve articles in all journals
with MSC (1991):
28D99,
60G10,
94A15
Additional Information
John Kieffer
Affiliation:
Department of Electrical Engineering, University of Minnesota, 200 Union Street SE, Minneapolis, MN 55455
Email:
kieffer@ee.umn.edu
Enhui Yang
Affiliation:
Department of Mathematics, Nankai University, Tianjin 300071, P. R. China
Email:
ehyang@irving.usc.edu
DOI:
http://dx.doi.org/10.1090/S1079676297000188
PII:
S 10796762(97)000188
Keywords:
Graphs,
entropy,
compression,
stationary ergodic process
Received by editor(s):
December 12, 1996
Published electronically:
March 12, 1997
Additional Notes:
This work was supported in part by the National Science Foundation under Grants NCR9304984 and NCR9627965
Communicated by:
Douglas Lind
Article copyright:
© Copyright 1997 American Mathematical Society
