Hierarchical Type Classes and Their Entropy Functions
John C. Kieffer · 2011
For each j ≥ 1, if Tjis the finite rooted binary tree with 2jleaves, the hierarchical type class of binary string x of length 2jis obtained by placing the entries of x as labels on the leaves of Tjand then forming all permutations of x according to the permutations of the leaf labels under all isomorphisms of tree Tjinto itself. The set of binary strings of length 2jis partitioned into hierarchical type classes, and in each such class, all of the strings have the same type (n0j,n1j), where n0j,n1jare respectively the numbers of zeroes and ones in the strings. Let p(n0j,n1j) be the probability vector (n0j/2j, n1j/2j) belonging to the set P2of all two-dimensional probability vectors. For each j ≥ 1, and each of the 2j+ 1 possible types (n0j,n1j), a hierarchical type class S(n0j,n1j) is specified. Conditions are investigated under which there will exist a function h : P2→ [0, ∞) such that for each p ∈ P2, if {(n0j,n1j) : j ≥ 1} is any sequence of types for which p(n0j,n1j) → p, then the sequence {2-jlog2(card(S(n0j,n1j))) : j ≥ 1} converges to h(p). Such functions h, called hierarchical entropy functions, play the same role in hierarchical type class coding theory that the Shannon entropy function on P2does in traditional type class coding theory, except that there are infinitely many hierarchical entropy functions but only one Shannon entropy function. One of the hierarchical entropy functions h that is studied is a self-affine function for which a closed-form expression is obtained making use of an iterated function system whose attractor is the graph of h.