Archival Version
These pages are not updated anymore.
They reflect the state of
.
For the current production of this journal, please refer to
http://www.math.psu.edu/era/.
Ergodic behavior of graph entropy
This journal is archived by the American Mathematical
Society. The master copy is available at
http://www.ams.org/era/
Ergodic behavior of graph entropy
John Kieffer and En-hui Yang
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.
Copyright 1997 American Mathematical Society
Retrieve entire article
Article Info
- ERA Amer. Math. Soc. 03 (1997), pp. 11-16
- Publisher Identifier: S 1079-6762(97)00018-8
- 1991 Mathematics Subject Classification. Primary 28D99; Secondary 60G10, 94A15
- Key words and phrases. Graphs, entropy, compression, stationary ergodic process
- Received by the editors December 12, 1996
- Posted on March 12, 1997
- Communicated by Douglas Lind
- Comments (When Available)
John Kieffer
Department of Electrical Engineering, University of Minnesota,
200 Union Street SE, Minneapolis, MN 55455
E-mail address: kieffer@ee.umn.edu
En-hui Yang
Department of Mathematics, Nankai University, Tianjin 300071,
P. R. China
E-mail address: ehyang@irving.usc.edu
This work was supported in part by the National Science
Foundation under Grants
NCR-9304984 and NCR-9627965
Electronic Research Announcements of the AMS Home page