Information Theoretical Analysis of Self-Similar Trees

Tree-like patterns are ubiquitous in nature. Botanical trees, river networks, and blood systems are the most well-known examples of complex hierarchical systems met in observations. Interestingly, many of such systems exhibit statistical self-similarity. There are two main types of self-similarity: Horton self-similarity and Tokunaga self-similarity. Although there is an increased attention to the topic of trees' self-similarity, there is still a lack of theory that would allow to measure the information content embodied in vast variety of complex self-similar systems. In this work, we address the question of information quantification in tree-like self-similar structures. We start with combinatorial results that provide cardinality of several spaces of binary trees with given structural characteristics. Then, using the notions of entropy we study the structural complexity of uniformly distributed binary trees. Furthermore, we consider classes of Horton self-similar and Tokunaga self-similar uniformly distributed trees and, using the notion of entropy rate, analyze how the structural complexity of such trees changes as the number of vertices of the tree grows to infinity.

Major Advisor: Juan Restrepo
Minor Advisor: David Koslicki
Committee: Bella Bose
Committee: Eric Walkingshaw
GCR: Merrick Haller