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