Ergodic behavior of graph entropy
Authors:
John Kieffer and En-hui Yang
Journal:
Electron. Res. Announc. Amer. Math. Soc. 3 (1997), 11-16
MSC (1991):
Primary 28D99; Secondary 60G10, 94A15
DOI:
https://doi.org/10.1090/S1079-6762-97-00018-8
Published electronically:
March 12, 1997
MathSciNet review:
1433180
Full-text PDF Free Access
Abstract |
References |
Similar Articles |
Additional Information
Abstract: For a positive integer $n$, let $X^n$ be the vector formed by the first $n$ samples of a stationary ergodic finite alphabet process. The vector $X^n$ is hierarchically represented via a finite rooted acyclic directed graph $G_n$. Each terminal vertex of $G_n$ carries a label from the process alphabet, and $X^n$ can be reconstituted as the sequence of labels at the ends of the paths from root vertex to terminal vertex in $G_n$. The entropy $H(G_n)$ of the graph $G_n$ is defined as a nonnegative real number computed in terms of the number of incident edges to each vertex of $G_n$. An algorithm is given which assigns to $G_n$ a binary codeword from which $G_n$ can be reconstructed, such that the length of the codeword is approximately equal to $H(G_n)$. It is shown that if the number of edges of $G_n$ is $o(n)$, then the sequence $\{H(G_n)/n\}$ converges almost surely to the entropy of the process.
- Thomas M. Cover and Joy A. Thomas, Elements of information theory, Wiley Series in Telecommunications, John Wiley & Sons, Inc., New York, 1991. A Wiley-Interscience Publication. MR 1122806
- 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).
- 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).
- 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).
- Abraham Lempel and Jacob Ziv, On the complexity of finite sequences, IEEE Trans. Inform. Theory IT-22 (1976), no. 1, 75–81. MR 389403, DOI https://doi.org/10.1109/tit.1976.1055501
- T. M. Cover and J. A. Thomas, Elements of information theory, Wiley, New York, 1991.
- 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).
- 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).
- 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).
- A. Lempel and J. Ziv, On the complexity of finite sequences, IEEE Trans. Inform. Theory, 22 (1976), 75–81.
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
En-hui Yang
Affiliation:
Department of Mathematics, Nankai University, Tianjin 300071, P. R. China
Email:
ehyang@irving.usc.edu
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 NCR-9304984 and NCR-9627965
Communicated by:
Douglas Lind
Article copyright:
© Copyright 1997
American Mathematical Society