Ergodic behavior of graph entropy

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.