Geodesic
Ergodic behavior of graph entropy
Kieffer, John1 ; Yang, En-hui2
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
Electronic research announcements of the American Mathematical Society, Tome 03 (1997), pp. 11-16

Voir la notice de l'article provenant de la source American Mathematical Society

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},
     publisher = {mathdoc},
     volume = {03},
     year = {1997},
     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
PB  - mathdoc
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
%I mathdoc
%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 :