arXiv preprint ·
Information Theory of Random Composition Trees
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Information Theory
Private Evaluation of High-Dimensional Functions
Dimension-free comparison inequalities between $f$-divergences for Gaussian location mixtures
Pre-Query Retention with Bounded Bit and Word Retrieval
Query-Dependent Reading for Quantized Inner-Product Estimation: A Minimax Separation
LiftDiff: Guided Discrete Diffusion for Quantum Code Construction
Get the few papers worth your time in Information Theory every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.