ELECTRONIC RESEARCH ANNOUNCEMENTS OF THE AMERICAN MATHEMATICAL SOCIETY Volume 3, Pages 11–16 (March 12, 1997) S 1079-6762(97)00018-8

ERGODIC BEHAVIOR OF GRAPH ENTROPY

JOHN KIEFFER AND EN-HUI YANG

(Communicated by Douglas Lind)

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.

1. Introduction

In the hierarchical approach to data compression developed by the authors [2], [3], [4], finite rooted acyclic directed graphs can be used to represent the data strings that are to be compressed. To see how this representation works, let us determine the data string x represented by the graph in Figure 1. This graph contains ten edges labelled 1 through 10 and two terminal vertices labelled 0 and 1. If we list the paths in this graph that go from root vertex to a terminal vertex, we obtain the ten paths

(1), (2, 5), (2, 6), (3, 7, 5), (3, 7, 6), (3, 8), (4, 9, 7, 5), (4, 9, 7, 6), (4, 9, 8), (4, 10).

(The paths are listed in lexicographical order.) The string x is then obtained by replacing each path in this list with the label on the terminal vertex for that path. We see that x = 0010110111.

Let G = (V, E) denote an arbitrary finite rooted acyclic directed graph, where V is the set of vertices and E is the set of edges. Let |V |, |E| denote the number of vertices and the number of edges, respectively. (In general, let |S| denote the cardinality of any finite set S.) For each v ∈ V, let i(v) be the number of edges

Received by the editors December 12, 1996. 1991 Mathematics Subject Classification. Primary 28D99; Secondary 60G10, 94A15. Key words and phrases. Graphs, entropy, compression, stationary ergodic process. This work was supported in part by the National Science Foundation under Grants NCR-

9304984 and NCR-9627965.

\begin{matrix}c \\ ◯ \end{matrix}1997 American Mathematical Society

[figure: 1; 2; 4; 3; 5; 6; 7; 8; 10; 9; 0; 1] Figure 1

that terminate at v. Following [2], the entropy H(G) of the graph G is defined by

H(G) = ∑_{v∈V, i(v)≥2}(i(v) − 1) log (\frac{|E| − |V | + 1}{i(v) − 1}) ,

where the logarithm throughout shall be to base two. The entropy of the graph in Figure 1 is 3 log 5 + 2 log(5/2) = 9.61.

Suppose we are given an infinite finite-alphabet sequence (x_{1}, x_{2}, …), and let x^{n} = (x_{1}, x_{2}, …, x_{n}), n ≥ 1. For each n, a graph G_{n} is selected to represent the data string x^{n}. One then compresses x^{n} by assigning a binary codeword to G_{n} that allows one to reconstruct G_{n} and therefore x^{n}. The length of this codeword is approximately equal to H(G_{n}). (See Lemma 1.) A natural question is the behavior of the entropies {H(G_{n})} as n → ∞ when the sequence (x_{1}, x_{2}, …) is generated by a stationary ergodic process. In this case, our main result (Theorem 1) states that {H(G_{n})/n} converges almost surely to the entropy of the process, provided only that the number of edges of G_{n} is o(n). Some of the many applications of this result shall be discussed.

2. Main result

If B is a finite set, let B^{∗} denote the set of all strings of finite length formed from symbols in B. Suppose s_{1}, s_{2}, …, s_{n} are strings in a set B^{∗}. Let s_{1} ∗ s_{2} ∗ ⋯ ∗ s_{n} denote the string in B^{∗} obtained by concatenating together the strings s_{1}, s_{2}, …, s_{n} in the indicated order.

Let G = (V, E) be a finite rooted acyclic directed graph. Let V_{t} denote the set of terminal vertices of G. For each v ∈ V, v ∉ V_{t}, let E^{+}(v) denote the set of all edges emanating from v. For each v ∈ V, v ≠ root vertex, let E^{−}(v) denote the set of all edges which terminate at v. We say that G is a canonical graph if

(i): V = {1, 2, …, |V |} and 1 ∈ V is the root vertex.

(ii): E = {1, 2, …, |E|}.

(iii): If v_{1}, v_{2} ∈ {2, …, |V |} and v_{1} < v_{2}, then min E^{−}(v_{1}) < min E^{−}(v_{2}).

(iv): If v_{1}, v_{2} ∈ {v ∈ V : v ∉ V_{t}} and v_{2} > v_{1}, then min E^{+}(v_{2}) > max E^{+}(v_{1}).

Every finite acyclic rooted directed graph is isomorphic to a canonical graph, and graph entropy is an isomorphism invariant; therefore, we concentrate on canonical graphs from now on.

Let G = (V, E) be a finite rooted acyclic directed canonical graph. There is a unique mapping ψ_{G} : V → V_{t}^{∗} satisfying the following two rules:

(i): ψ_{G}(v) = v, v ∈ V_{t}.

(ii): If v ∈ V, v ∉ V_{t}, r = min E^{+}(v), and s = max E^{+}(v), then

ψ_{G}(v) = ψ_{G}(v(r)) ∗ ψ_{G}(v(r + 1)) ∗ ⋯ ∗ ψ_{G}(v(s)),

where v(e) denotes the vertex at which edge e terminates. Let (v_{1}, v_{2}, …, v_{k}) be the string ψ_{G}(1). If (x_{1}, x_{2}, …, x_{k}) is a string of the same length, whose symbols {x_{i}} are selected from any set whatsoever, we write G → x if there is a one-to-one mapping f : V_{t} → {x_{1}, x_{2}, …, x_{k}} such that x_{i} = f(v_{i}) for 1 ≤ i ≤ k. Let G denote the set of all finite rooted acyclic directed canonical graphs G such that ψ_{G} is one-to-one.

We fix a finite nonempty set A for the rest of the paper.

Theorem 1. For each x ∈ A^{∗}, let G(x) = (V (x), E(x)) be a graph in G such that G(x) → x. Let (X_{1}, X_{2}, …) be an A-valued stationary ergodic process with entropy H. Assume that

|E(X_{1}, X_{2}, …, X_{n})|/n → 0 almost surely as n → ∞.

Then

H(G(X_{1}, X_{2}, …, X_{n}))/n → H almost surely as n → ∞.

3. Applications

1. For each x ∈ A^{∗}, let G(x) = (V (x), E(x)) be a graph in G such that G(x) → x. Suppose that max{|E(x)| : x ∈ A^{n}} = o(n). As shown in [2], there is a computationally attractive data compression algorithm that assigns to each sufficiently long x ∈ A^{∗} a binary codeword of length approximately equal to H(G(x)). Theorem 1 tells us that this algorithm optimally compresses the first n data samples generated by any stationary ergodic A-valued process, asymptotically as n → ∞. (“Optimally compresses” refers to the well-known fact [1] that no compression algorithm can achieve an asymptotic compression rate in code bits per data sample less than the entropy of the process generating the data samples.)

2. The well-known Lempel-Ziv parsing rule [5] partitions each string x ∈ A^{∗} into t = t(x) phrases such that

(i): Each phrase is either a singleton or is obtained by adjoining a symbol to

the end of a preceding phrase. (ii): The first t − 1 phrases are distinct.

For example, the Lempel-Ziv parsing of the data string 0010110111 is (0), (01), (011), (0111). Let (X_{1}, X_{2}, …) be an A-valued stationary ergodic process with entropy H. Theorem 1 can be used to deduce the asymptotic expansion

t(X_{1}, X_{2}, …, X_{n}) = \frac{Hn}{log n} + o (\frac{n}{log n}) almost surely.

(One defines a graph G(x) → x such that H(G(x)) is approximately equal to t(x) log n whenever x ∈ A^{n} and n is large.)

3. Let ϕ : [0, ∞) → (−∞, ∞) be the function such that ϕ(0) = 0 and ϕ(x) = x log x for x > 0. Let n > 1 be an integer and let x ∈ A^{2^{n}}. For each integer k such that 0 ≤ k ≤ n, let S_{k}(x) be the set of all y ∈ A^{2^{k}} that appear in the partitioning of x into substrings of length 2^{k}. If y ∈ A^{2^{k}} for 0 ≤ k < n, let N_{l}(y|x) be the number of z such that y ∗ z ∈ S_{k+1}(x) and let N_{r}(y|x) be the number of z such that z ∗ y ∈ S_{k+1}(x). Define Q_{k}(x) to be the number

Q_{k}(x) = ϕ ( ∑_{y∈A^{2^{k}}}{N_{l}(y|x) + N_{r}(y|x) − 1}) − ∑_{y∈A^{2^{k}}} ϕ (N_{l}(y|x) + N_{r}(y|x) − 1) .

Let (X_{1}, X_{2}, …) be an A-valued stationary ergodic process with entropy H. Using Theorem 1 one can deduce the following limit formula for H:

\frac{1}{2^{n}} ∑_{k=0}^{n−1} Q_{k}(X_{1}, X_{2}, …, X_{2^{n}}) → H almost surely as n → ∞.

Each string y lying in the union of the S_{k}(x), 0 ≤ k ≤ n, generates a vertex v(y) of a graph G(x). If the length of y is at least two, two edges emanate from v(y), one going to v(y_{1}) and one going to v(y_{2}), where y_{1} and y_{2} are the right and left halves of y. One then applies Theorem 1 to the graphs {G(x)}.

4. Ancillary results

Lemma 1. Let k be a positive integer. Let G_{k} = {G = (V, E) ∈ G : |E| ≤ k}. The members of G_{k} can be assigned distinct binary codewords so that

(i): The codeword assigned to G ∈ G_{k} is of length no greater than H(G)+6k+1. (ii): No codeword is a prefix of any other codeword.

Lemma 2. For 0 < ϵ < 1, and n sufficiently large, define h_{ϵ}(x) for x ∈ A^{n} by

h_{ϵ}(x) = min{H(G) : G = (V, E) ∈ G, G → x, |E| < nϵ}.

Then

lim_{ϵ→0} lim sup_{n→∞} \frac{1}{n} log ( ∑_{x∈A^{n}} 2^{−h_{ϵ}(x)}) = 0.

Lemma 3. Let k be a positive integer. Then there exists a function f_{k} : (0, ∞) → (−∞, ∞) satisfying lim_{t→0^{+}} f_{k}(t) = 0 for which

H(G)/n ≤ f_{k} (|E|/n) − \frac{1}{nk} ∑_{i=0}^{n−k+1} log μ(x_{i}, x_{i+1}, …, x_{i+k−1}) (4.1)

whenever n ≥ k, μ is a probability distribution on A^{k}, x ∈ A^{n}, and G = (V, E) ∈ G with G → x.

5. Proofs

Proof of Lemma 1. We call the binary symbols in the codeword for G = (V, E) ∈ G_{k} “codebits”. The first 6k codebits in the codeword serve to identify each of the following six entities concerning G:

(i): |E|.

(ii): |V |.

(iii): V_{t}.

(iv): The cardinalities of the sets E^{+}(v), v ∈ V, v ∉ V_{t}.

(v): The cardinalities of the sets E^{−}(v), v ∈ V, v ≠ 1.

(vi): The positions in the vector (v(1), v(2), …, v(|E|)) where each vertex v ≠

1 ∈ V first appears. Let s_{G} be the string obtained from (v(1), v(2), …, v(|E|)) by deleting the first appearance of each vertex v ≠ 1 ∈ V. The J remaining codebits identify the string s_{G}, and one then identifies G from s_{G} and items (i)–(vi). The string s_{G} lies in the set S_{G} of all strings of length |E| − |V | + 1 in which each v ≠ 1 ∈ V appears |E^{−}(v)| − 1 times. Taking J = ⌈log |S_{G}|⌉, J ≤ H(G) + 1.

Proof of Lemma 2. Fix n so large that h_{ϵ}(x) is defined for each x ∈ A^{n}. For each such x, pick a G_{x} = (V_{x}, E_{x}) ∈ G such that H(G_{x}) = h_{ϵ}(x), G_{x} → x, and |E_{x}| < nϵ. According to Lemma 1, we can assign to each G ∈ G_{n} = {G_{x} : x ∈ A^{n}} a binary codeword of length L(G) ≤ H(G) + 6nϵ + 1. Kraft’s inequality from information theory ([1], page 82) tells us that ∑_{G∈G_{n}} 2^{−L(G)} ≤ 1. From this and the fact that there are ≤ |A|^{nϵ} strings x ∈ A^{n} such that G → x for each G ∈ G_{n}, it follows that

∑_{x∈A^{n}} 2^{−L(G_{x})} ≤ |A|^{nϵ},

and therefore

∑_{x∈A^{n}} 2^{−h_{ϵ}(x)} ≤ 2^{6nϵ+1}|A|^{nϵ}.

Proof of Lemma 3. Fix k and a probability distribution μ on A^{k}. For each pair j, n in which 0 ≤ j < k and n ≥ k, let W_{j,n} = {1 ≤ i ≤ n − k + 1 : i ≡ j mod k}. For each string s = (s_{1}, s_{2}, …, s_{n}) ∈ A^{∗}, define λ(s) as follows:

(i): λ(s) = 1, n < k.

(ii): λ(s) = max_{0≤j<k} [∏_{i∈W_{j,n}} μ(s_{i}, s_{i+1}, …, s_{i+k−1})] , n ≥ k,

where an empty product is taken to be one. For each s ∈ A^{∗}, define λ^{∗}(s) = C^{−1}|s|^{−2}λ(s), where |s| denotes the length of s and C is the positive real constant (depending on k) that makes the numbers {λ^{∗}(s) : s ∈ A^{∗}} sum to one. Fix n ≥ k, x = (x_{1}, …, x_{n}) ∈ A^{n}, and G = (V, E) ∈ G such that G → x. Let r = |E| − |V | + |V_{t}| + 1. The function which carries ψ_{G}(1) into x also carries each ψ_{G}(v) into a string ψ_{G}^{∗}(v) (v ∈ V, v ≠ 1). There exist strings {s_{i} : 1 ≤ i ≤ r} such that

(i): {s_{i} : |E| − |V | + 1 < i ≤ r} = {x_{1}, x_{2}, …, x_{n}}.

(ii): |{1 ≤ i ≤ |E| − |V | + 1 : s_{i} = ψ_{G}^{∗}(v)}| = |E^{−}(v)| − 1, v ∈ V, v ≠ 1.

(iii): x = s̃_{1} ∗ s̃_{2} ∗ ⋯ ∗ s̃_{r}, for some permutation {s̃_{i}} of {s_{i}}. Note that

∏_{i=1}^{n−k+1} μ(x_{i}, …, x_{i+k−1}) ≤ [∏_{i=1}^{r} λ(s_{i})]^{k} .

Replacing λ(s_{i}) by C|s_{i}|^{2}λ^{∗}(s_{i}), and taking the logarithm of both sides,

− ∑_{i=1}^{|E|−|V |+1} log λ^{∗}(s_{i}) ≤ 2 ∑_{i=1}^{r} log |s_{i}| + r log C − \frac{1}{k} ∑_{i=1}^{n−k+1} log μ(x_{i}, …, x_{i+k−1}).

Concavity of the logarithm function yields the bound

2 ∑_{i=1}^{r} log |s_{i}| ≤ 2r log (\frac{n}{r}) .

For each s = ψ_{G}^{∗}(v), v ∈ V, v ≠ 1, define σ(s) = (|E^{−}(v)| − 1)/(|E| − |V | + 1). Then

H(G) = − ∑_{i=1}^{|E|−|V |+1} log σ(s_{i}) ≤ − ∑_{i=1}^{|E|−|V |+1} log λ^{∗}(s_{i}).

Condition (4.1) is true with f_{k}(t) = sup_{0<δ≤t}{δ log C − 2δ log δ}.

Proof of Theorem 1. Let (X_{1}, X_{2}, …) be a stationary ergodic A-valued process with entropy H. For n ≥ 1, let X^{n} = (X_{1}, X_{2}, …, X_{n}). If x ∈ A^{∗} has length n, define μ(x) = Pr[X^{n} = x]. From (4.1) we see that lim sup_{n→∞} H(G(X^{n}))/n ≤ H almost surely.

Fix δ > 0. By Lemma 2, there exists ϵ such that for n sufficiently large,

Pr [log (\frac{2^{−h_{ϵ}(X^{n})}}{μ(X^{n})} ) ≥ nδ] < 2^{−nδ/2}.

Applying the Borel-Cantelli lemma,

(5.1)  lim sup_{n→∞} \frac{1}{n} log (\frac{2^{−h_{ϵ}(X^{n})}}{μ(X^{n})} ) ≤ δ almost surely.

Replacing h_{ϵ}(X^{n}) by H(G(X^{n})) in (5.1), and then using the fact that

−n^{−1} log μ(X^{n}) → H a.s.

(Shannon-McMillan-Breiman Theorem), one concludes that

lim inf_{n→∞} H(G(X^{n}))/n ≥ H − δ almost surely,

for an arbitrary δ > 0.

References

[1] T. M. Cover and J. A. Thomas, Elements of information theory, Wiley, New York, 1991. MR 92g:94001

[2] J. Kieffer and E.-H. Yang, “A complexity reduction method for lossless source code design,” Technical Report, Dept. of Electrical Engineering, University of Minnesota Twin Cities, 1995 (http://www.ee.umn.edu/users/kieffer).

[3] J. Kieffer, E.-H. Yang, G. Nelson, and P. Cosman, “Lossless compression via bisection trees,” Technical Report, Dept. of Electrical Engineering, University of Minnesota Twin Cities, 1996 (http://www.ee.umn.edu/users/kieffer).

[4] J. Kieffer, G. Nelson, and E.-H. Yang, “Tutorial on the quadrisection method for lossless data compression,” Technical Report, Dept. of Electrical Engineering, University of Minnesota Twin Cities, 1996 (http://www.ee.umn.edu/users/kieffer).

[5] A. Lempel and J. Ziv, On the complexity of finite sequences, IEEE Trans. Inform. Theory, 22 (1976), 75–81. MR 52:10234

Department of Electrical Engineering, University of Minnesota, 200 Union Street SE, Minneapolis, MN 55455

E-mail address: kieffer@ee.umn.edu

Department of Mathematics, Nankai University, Tianjin 300071, P. R. China

E-mail address: ehyang@irving.usc.edu