Information theory of random trees induced by stochastic grammars.
2012-05
Loading...
View/Download File
Persistent link to this item
Statistics
View StatisticsJournal Title
Journal ISSN
Volume Title
Title
Information theory of random trees induced by stochastic grammars.
Authors
Published Date
2012-05
Publisher
Type
Thesis or Dissertation
Abstract
Previous research has been done on the information theory of binary random rooted tree models in which every nonleaf vertex in a tree has exactly two children. Let α be a positive integer parameter > 2. The main contribution of this thesis is to extend the information theory results for binary random tree models to α-random tree models, which are random tree models in which up to α children per each nonleaf vertex are allowed. An α-random random tree model consists of a sequence {Tn : n = 2, 3, · · · }, in which each Tn is an α-random tree having n leaves, and there is a context-free grammar describing how each Tn is randomly generated. In particular, balanced α-random tree models are examined, meaning that the context-free grammars which are employed satisfy a type of balance condition. We obtain three types of results for α-random tree models, described as follows.
First, given a general α-random tree model {Tn}, the entropy H(Tn) of each tree Tn is expressed as a recursive formula relating H(Tn) to the entropies of its subtrees. This recursion can be explicitly solved for some random tree models, and we show how this can be done for the binary random search tree model.
Our second set of results, which are our main results, concern the balanced α-random tree model {Tn}. Defining the entropy rate of Tn as the ratio H(Tn)/n, we examine the asymptotic behavior of the entropy rate as n grows without bound. This asymptotic behavior is described via a continuous non-constant periodic function P#11; → [0,∞), having period one, satisfying the property that H(Tn)/n = P#11;(log#11; n) for every n. The graph of P#11; is seen as a fractal and its fractal properties along with its fractal dimension are investigated. We develop a direct and indirect way of describing P#11;. The direct way expresses the graph of P#11; as the attractor of an iterated function system which is explicitly given. The indirect way obtains P#11; via a change of variable on a hierarchical entropy function discovered by J. Kieffer.
Our third and final set of results concern the development of compression methods for some α-random tree models {Tn}. In the case in which each random tree Tn is not equiprobable over the ensemble of trees in which it takes it values, we develop a encoding method via which Tn is uniquely represented by a variable-length binary codeword, so that the expected codeword length is roughly equal to the entropy H(Tn). In the case of the balanced α-random tree model, each Tn is equiprobable, which allows us to develop encoding methods via which each Tn is uniquely represented by a fixed-length binary codeword of minimal length ⌈H(Tn)⌉. One of the encoding methods discussed employs an one-to-one mapping of the ensemble of Tn into one of the hierarchical type classes discovered by J. Kieffer, allowing Kieffer’s method for encoding hierarchical type classes to be adapted to an encoding method for balanced α-random trees.
Description
University of Minnesota Ph.D. dissertation. May 2012. Major: Electrical Engineering. Advisor: John C. Kieffer. 1 computer file (PDF); vi, 97 pages, appendix A.
Related to
Replaces
License
Collections
Series/Report Number
Funding information
Isbn identifier
Doi identifier
Previously Published Citation
Suggested citation
Oh, Sang-youn. (2012). Information theory of random trees induced by stochastic grammars.. Retrieved from the University Digital Conservancy, https://hdl.handle.net/11299/129866.
Content distributed via the University Digital Conservancy may be subject to additional license and use restrictions applied by the depositor. By using these files, users agree to the Terms of Use. Materials in the UDC may contain content that is disturbing and/or harmful. For more information, please see our statement on harmful content in digital repositories.