Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Electronic Research Announcements
Electronic Research Announcements
ISSN 1079-6762

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
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.


References [Enhancements On Off] (What's this?)

  • 1. 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 (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 IT-22 (1976), no. 1, 75–81. MR 0389403 (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

En-hui Yang
Affiliation: Department of Mathematics, Nankai University, Tianjin 300071, P. R. China
Email: ehyang@irving.usc.edu

DOI: http://dx.doi.org/10.1090/S1079-6762-97-00018-8
PII: S 1079-6762(97)00018-8
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