## 1 Introduction
Then \(\mathcal{S}_{m,k}(\lambda)\) forms a partition of the set of all strings of type \(\lambda\). * **Prop. 4:** Let \(S\in\mathcal{S}_{m,k}\) be a hierarchical type class of order \(j\geq 1\). Then there is a \(k\)-tuple \((S_{1},S_{2},\cdots,S_{k})\), unique up to permutation, such that each \(S_{i}\) is a hierarchical type class of order \(j-1\) and \(S\) is expressible as Expression (1). **Global Hierarchical Entropy Function. ** The _global hierarchical entropy function_ is the function \(H:\mathcal{S}_{m,k}\rightarrow[0,\infty)\) such that  
\[H(S)\stackrel{{\Delta}}{{=}}\log_{2}|S|,\ \ S\in\mathcal{S}_{m,k}\]  
where, in this paper, if \(S\) is a finite set, \(|S|\) shall denote the cardinality of \(S\). \(H(S)\) shall be called the entropy of \(S\). Given a hierarchical type class \(S\), its entropy \(H(S)\) has the following interpretation. Suppose \(H(S)>0\), and we losslessly encode the strings in \(S\) into fixed-length binary codewords of minimal length (as discussed in Example 1 and in [3]). Then this minimal length is \(\lceil H(S)\rceil\). **Lemma 1. ** Let \(S\) be a hierarchical type class of order \(j\geq 1\). Let \((S_{1},S_{2},\cdots,S_{k})\) be the \(k\)-tuple of hierarchical type classes of order \(j-1\) associated with \(S\) according to Prop. 4, and let \(N(S)\) be the number of distinct permutations of this \(k\)-tuple. Then,  
\[H(S)=[\sum_{i=1}^{k}H(S_{i})]+\log_{2}N(S) \tag{2}\]  
_Proof._ Represent \(S\) as the Expression (1). Formula (2) follows easily from this expression. _Remark._ We see now how to inductively compute entropy values \(H(S)\), as follows. If \(S\) is of order \(0\), then \(|S|=1\) and so \(H(S)=0\). If \(S\) is of order \(j\geq 1\), assume all entropy values for hierarchical type classes of smaller order have been computed. Then Equation (2) is used to compute \(H(S)\). _Discussion._ Let \(\{S_{j}:j\geq 1\}\) be a sequence of hierarchical type classes from \(\mathcal{S}_{m,k}\) such that \(S_{j}\) is of order \(j\) (\(j\geq 1\)). Consider the sequence of normalized entropies \(\{H(S_{j})/k^{j}:j\geq 1\}\). As \(j\) becomes large, the normalized entropy \(H(S_{j})/k^{j}\) approximates more and more closely the compression rate in bits per data sample that results from the compression scheme on \(S_{j}\). It is therefore of interest to determine circumstances under which such a sequence of normalized entropies will have a limit that we can compute. We discuss our approach to this problem, which will be pursued in the rest of this paper. A _hierarchical source_ is defined to be a family \(\{S(\lambda):\lambda\in\Lambda(m,k)\}\) in which each \(S(\lambda)\) is a hierarchical type class selected from \(\mathcal{S}_{m,k}(\lambda)\). (We will also impose a natural consistency condition on how these selections are made in our formal hierarchical source definition to be given in the next section.) Let \(\mathbb{R}\) denote the real line, and let \(\mathbb{P}_{m}\) be the subset of \(\mathbb{R}^{m}\) consisting of all \(m\)-dimensional probability vectors. We consider \(\mathbb{P}_{m}\) to be a metric space with the Euclidean metric. For each \(\lambda\in\Lambda(m,k)\), let \(p_{\lambda}\) be the probability vector \(\lambda/\|\lambda\|\) in \(\mathbb{P}_{m}\). Suppose there exists a (necessarily unique) continuous function \(h:\mathbb{P}_{m}\rightarrow[0,\infty)\) such that for each \(p\in\mathbb{P}_{m}\), and each sequence \(\{\lambda_{j}:j\geq 0\}\) for which \(\lambda_{j}\in\Lambda_{j}(m,k)\) (\(j\geq 0\)) and \(\lim_{j\rightarrow\infty}p_{\lambda_{j}}=p\), the limit property  
\[h(p)=\lim_{j\rightarrow\infty}H(S(\lambda_{j}))/k^{j}\]  
holds. Then we call the function \(h\) the _hierarchical entropy function induced by the source_\(\{S(\lambda):\lambda\in\Lambda(m,k)\}\). A _hierarchical entropy function_ is defined to be any function on \(\mathbb{P}_{m}\) which is the hierarchical entropy function induced by some hierarchical source. One of the goals of hierarchical data compression theory is to identify hierarchical entropy functions and to learn about their properties.