Mutual dimension, data processing inequalities, and randomness

Abstract

<p>This dissertation makes progress in the area of constructive dimension, an effectivization of classical Hausdorff dimension. Using constructive dimension, one may assign a non-zero number to the dimension of individual sequences and individual points in Euclidean space. The primary objective of this dissertation is to develop a framework for mutual dimension, i.e., the density of algorithmic mutual information between two infinite objects, that has similar properties as those of classical Shannon mutual information.</p> <p>Chapter 1 presents a brief history of the development of constructive dimension along with its relationships to algorithmic information theory, algorithmic randomness, and classical Hausdorff dimension. Some applications of this field are discussed and an overview of each subsequent chapter is provided.</p> <p>Chapter 2 defines and analyzes the mutual algorithmic information between two points x and y at a given precision r. In fact, we describe two plausible definitions for this quantity, I_r(x:y) and J_r(x:y), and show that they are closely related. In order to do this, we prove and make use of a generalization of Levin's coding theorem.</p> <p>Chapter 3 defines the lower and upper mutual dimensions between two points in Euclidean space and presents results on its basic properties. A large portion of this chapter is dedicated to studying data processing inequalities for points in Euclidean space. Generally speaking, a data processing inequality says that the amount of information between two objects cannot be significantly increased when one of the objects is processed by a particular type of transformation. We show that it is possible to derive several kinds of data processing inequalities for points in Euclidean space depending on the continuity properties of the computable transformation that is used.</p> <p>Chapter 4 focuses on extending mutual dimension to sequences over an arbitrary alphabet. First, we prove that the mutual dimension between two sequences is equal to the mutual dimension between the sequences' real representations. Using this result, we show that the lower and upper mutual dimensions between sequences have nice properties. We also provide an analysis of data processing inequalities for sequences where transformations are represented by Turing functionals whose use and yield are bounded by computable functions.</p> <p>Chapter 5 relates mutual dimension to the study of algorithmic randomness. Specifically, we show that a particular class of coupled random sequences, i.e., sequences generated by independent tosses of coins whose biases may or may not be correlated, can be characterized by classical Shannon mutual information. We also prove that any two sequences that are independently random with respect to computable probability measures have zero mutual dimension and that the converse of this statement is not true. We conclude this chapter with some initial investigations on Billingsley mutual dimension, i.e., mutual dimension with respect to probability measures, and prove the existence of a mutual divergence formula.</p>