Information Theory of Random Composition Trees
Abstract
Random composition trees model the hierarchical semantic structures of meaningful texts as a statistical ensemble generated by recursively splitting texts into coherent chunks. A recent study shows that different text types can be described by random composition trees with distinct branching factors, and that the entropy rates of these trees exhibit a similar dependence across text types as the entropy rates of the actual texts. Motivated by this correspondence, we analyze information-theoretic properties of this stochastic splitting model. First, we demonstrate that the entropy of random composition trees grows linearly with the root size, and we derive an analytical expression for the entropy rate as a function of the branching factor. Second, we prove that large trees exhibit typicality: with high probability, they belong to a typical set in which each tree is approximately equally likely. Our analysis reveals that the random composition tree model shares two key information-theoretic properties of language when modeled as a stationary and ergodic stochastic process: linear entropy growth and typicality.
Related
- Compactness of composition operators on Hardy spaces of homogeneous rooted trees
- Random walk in a non-homogeneous random environment on some random trees and the non-negative integers
- Uniform integrability of the distance to the nearest leaf in random trees
- Infinite-mean Galton-Watson trees have zero random-interchange threshold
- On the limiting distribution of the number of improper edges for random trees
BibTeX
@misc{sivan2026information,
title = {{Information Theory of Random Composition Trees}},
author = {Doron Sivan and Weishun Zhong and Tankut Can and Mikhail Katkov and Misha Tsodyks},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.24788},
eprint = {2610.24788},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.24788},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Information Theory of Random Composition Trees
AU - Doron Sivan
AU - Weishun Zhong
AU - Tankut Can
AU - Mikhail Katkov
AU - Misha Tsodyks
PY - 2026
DA - 2026/10/17
PB - arXiv
DO - 10.48550/arxiv.2610.24788
UR - https://arxiv.org/abs/2610.24788
AB - Random composition trees model the hierarchical semantic structures of meaningful texts as a statistical ensemble generated by recursively splitting texts into coherent chunks. A recent study shows that different text types can be described by random composition trees with distinct branching factors, and that the entropy rates of these trees exhibit a similar dependence across text types as the entropy rates of the actual texts. Motivated by this correspondence, we analyze information-theoretic properties of this stochastic splitting model. First, we demonstrate that the entropy of random composition trees grows linearly with the root size, and we derive an analytical expression for the entropy rate as a function of the branching factor. Second, we prove that large trees exhibit typicality: with high probability, they belong to a typical set in which each tree is approximately equally likely. Our analysis reveals that the random composition tree model shares two key information-theoretic properties of language when modeled as a stationary and ergodic stochastic process: linear entropy growth and typicality.
ER -