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 , 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 Wiley-Interscience Publication. MR**1122806****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**

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

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