## 2 Hierarchical Sources
### _Finitary Hierarchical Sources_  
If \(\lambda=(n_{1},n_{2},\cdots,n_{m})\) is a type in \(\Lambda(m,k)^{+}\), define  
\[r(\lambda)\stackrel{{\Delta}}{{=}}(\mathrm{mod}(n_{1},k), \mathrm{mod}(n_{2},k),\cdots,\mathrm{mod}(n_{m},k))\]  
where \(\mathrm{mod}(n,k)\in\{0,1,\cdots,k-1\}\) is the remainder upon division of \(n\) by \(k\). Each entry of \(r(\lambda)\) belongs to the set \(\{0,1,\cdots,k-1\}\) and the sum of the entries of \(r(\lambda)\) is an integer multiple of \(k\). _Definitions._  
* \(\mathcal{R}(m,k)\) is defined to be the set of all \(m\)-tuples whose entries come from \(\{0,1,\cdots,k-1\}\) and sum to an integer multiple of \(k\). * \(\Psi(m,k)\) is defined to be the set of all mappings \(\psi\) from \(\mathcal{R}(m,k)\) to the set of binary \(k\times m\) matrices such that if \(r=(r_{1},\cdots,r_{m})\) belongs to \(\mathcal{R}(m,k)\), then \(\psi(r)\) has left-to-right column sums \(r_{1},r_{2},\cdots,r_{m}\) and row sums all equal to \((r_{1}+r_{2}+\cdots+r_{m})/k\). The set \(\Psi(m,k)\) is nonempty for each choice of parameters \(m,k\geq 2\)[4, 5]. * If \(\psi\in\Psi(m,k)\), define \(\psi^{*}\) to be the unique mapping in \(\Phi(m,k)\) which does the following. If \(\lambda=(n_{1},n_{2},\cdots,n_{m})\) belongs to \(\Lambda(m,k)^{+}\), let \(A=\psi(r(\lambda))\). Then \(\psi^{*}(\lambda)=(\lambda_{1},\lambda_{2},\cdots,\lambda_{k}),\) where \[\lambda_{i}=(\lfloor n_{1}/k\rfloor,\lfloor n_{2}/k\rfloor,\cdots,\lfloor n_{ m}/k\rfloor)+A(i,1:m),\ \ i=1,2,\cdots,k\] with \(A(i,1:m)\) denoting the \(i\)-th row of \(A\). * Suppose \(\psi\in\Psi(m,k)\) and let \(\phi=\psi^{*}\). The \(\Lambda(m,k)\)-indexed hierarchical source \(\{S^{\phi}:\lambda\in\Lambda(m,k)\}\) defines a _finitary source_. For each choice of parameters \(m,k\geq 2\), since \(\Psi(m,k)\) is nonempty, there is at least one finitary \(\Lambda(m,k)\)-indexed hierarchical source. The word \"finitary\" is used to describe these sources because they are each definable in finite terms by the specification of \(mk|\mathcal{R}(m,k)|\) bits (the elements of a number of \(k\times m\) binary matrices). _Example 2._ Note that \((1122)\) belongs to \(\mathcal{R}(4,3)\). Suppose  
\[\psi(1122)=\left[ \begin{array}{c}1100\\ 0011\\ 0011\end{array} \right]\]  
Note that \((7758)\in\Lambda^{+}(4,3)\), and that  
\[r(7758)=\mathrm{mod}((7758),3)=(1122)\]Since \(\lfloor(7758)/3\rfloor=(2212),\) we see that \(\psi^{*}(7758)=(\lambda_{1},\lambda_{2},\lambda_{3}),\) where  
\[\lambda_{1} =(2212)+(1100)=(3312)\] \[\lambda_{2} =(2212)+(0011)=(2223)\] \[\lambda_{3} =(2212)+(0011)=(2223)\]  
Note that the splitting up of \((7758)\) into the three types \((3312),(2223),(2223)\) indeed does make sense because these latter three types sum to \((7758)\) and are of order \(2\), one less than the order of \((7758)\). _Example 3._ Fix the alphabet cardinality parameter to be \(2\), and fix the partitioning parameter \(k\) to be any integer \(\geq 2\). Let \((r_{1},r_{2})\) belong to \(\mathcal{R}(2,k)\). Then either (a) \((r_{1},r_{2})=(0,0)\) or (b) \(r_{1}+r_{2}=k\). In case (a), we define \(\psi(r_{1},r_{2})\) to be the \(k\times 2\) zero matrix. In case (b), we define \(\psi(r_{1},r_{2})\) to be the \(k\times 2\) matrix whose first \(r_{1}\) rows are \((1,0)\) and whose last \(r_{2}\) rows are \((0,1)\). Letting \(\phi=\psi^{*}\), we obtain finitary \(\Lambda(2,k)\)-indexed hierarchical source \(\mathcal{S}^{\phi}\). _Example 4._ Now fix the alphabet cardinality parameter to be \(3\), and fix the partitioning parameter \(k\) to be any integer \(\geq 2\). Let \((r_{1},r_{2},r_{3})\) belong to \(\mathcal{R}(3,k)\). Then either (a) \((r_{1},r_{2},r_{3})=(0,0,0)\); (b) \(r_{1}+r_{2}+r_{3}=k\); or (c) \(r_{1}+r_{2}+r_{3}=2k\). In case (a), we define \(\psi(r_{1},r_{2},r_{3})\) to be the \(k\times 3\) zero matrix. In case (b), we define \(\psi(r_{1},r_{2},r_{3})\) to be the \(k\times 3\) matrix whose first \(r_{1}\) rows are \((100)\), whose next \(r_{2}\) rows are \((010)\), and whose last \(r_{3}\) rows are \((001)\).