Geodesic
Ergodic behavior of graph entropy
Kieffer, John1 ; Yang, En-hui2
1Department of Electrical Engineering, University of Minnesota, 200 Union Street SE, Minneapolis, MN 55455
2Department of Mathematics, Nankai University, Tianjin 300071, P. R. China
Electronic research announcements of the American Mathematical Society, Tome 03 (1997), pp. 11-16
Cet article a éte moissonné depuis la source American Mathematical Society

Voir la notice de l'article

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.
DOI : 10.1090/S1079-6762-97-00018-8

Kieffer, John  1   ; Yang, En-hui  2

1 Department of Electrical Engineering, University of Minnesota, 200 Union Street SE, Minneapolis, MN 55455
2 Department of Mathematics, Nankai University, Tianjin 300071, P. R. China 
@article{10_1090_S1079_6762_97_00018_8,
     author = {Kieffer, John and Yang, En-hui},
     title = {Ergodic behavior of graph entropy},
     journal = {Electronic research announcements of the American Mathematical Society},
     pages = {11--16},
     year = {1997},
     volume = {03},
     doi = {10.1090/S1079-6762-97-00018-8},
     url = {http://geodesic.mathdoc.fr/articles/10.1090/S1079-6762-97-00018-8/}
}
TY  - JOUR
AU  - Kieffer, John
AU  - Yang, En-hui
TI  - Ergodic behavior of graph entropy
JO  - Electronic research announcements of the American Mathematical Society
PY  - 1997
SP  - 11
EP  - 16
VL  - 03
UR  - http://geodesic.mathdoc.fr/articles/10.1090/S1079-6762-97-00018-8/
DO  - 10.1090/S1079-6762-97-00018-8
ID  - 10_1090_S1079_6762_97_00018_8
ER  - 
%0 Journal Article
%A Kieffer, John
%A Yang, En-hui
%T Ergodic behavior of graph entropy
%J Electronic research announcements of the American Mathematical Society
%D 1997
%P 11-16
%V 03
%U http://geodesic.mathdoc.fr/articles/10.1090/S1079-6762-97-00018-8/
%R 10.1090/S1079-6762-97-00018-8
%F 10_1090_S1079_6762_97_00018_8
Kieffer, John; Yang, En-hui. Ergodic behavior of graph entropy. Electronic research announcements of the American Mathematical Society, Tome 03 (1997), pp. 11-16. doi: 10.1090/S1079-6762-97-00018-8

[1] Cover, Thomas M., Thomas, Joy A. Elements of information theory 1991

[2] Lempel, Abraham, Ziv, Jacob On the complexity of finite sequences IEEE Trans. Inform. Theory 1976 75 81

Cité par Sources :