Dimension spectra of random subfractals of self-similar fractals

The dimension of a point x   in Euclidean space (meaning the constructive Hausdorff dimension of the singleton set {x}{x}) is the algorithmic information density of x  . Roughly speaking, this is the least real number dim(x)dim(x) such that r×dim(x)r×dim(x) bits suffice to specify x   on a general-purpose computer with arbitrarily high precision 2−r2−r. The dimension spectrum of a set X   in Euclidean space is the subset of [0,n][0,n] consisting of the dimensions of all points in X.The dimensions of points have been shown to be geometrically meaningful (Lutz 2003 [16], Hitchcock 2005 [12]), and the dimensions of points in self-similar fractals have been completely analyzed (Lutz and Mayordomo 2008 [18]). Here we begin the more challenging task of analyzing the dimensions of points in random fractals. We focus on fractals that are randomly selected subfractals of a given self-similar fractal. We formulate the specification of a point in such a subfractal as the outcome of an infinite two-player game between a selector that selects the subfractal and a coder that selects a point within the subfractal. Our selectors are algorithmically random with respect to various probability measures, so our selector–coder games are, from the coder's point of view, games against nature.We determine the dimension spectra of a wide class of such randomly selected subfractals. We show that each such fractal has a dimension spectrum that is a closed interval whose endpoints can be computed or approximated from the parameters of the fractal. In general, the maximum of the spectrum is determined by the degree to which the coder can reinforce the randomness in the selector, while the minimum is determined by the degree to which the coder can cancel randomness in the selector. This constructive and destructive interference between the players' randomnesses is somewhat subtle, even in the simplest cases. Our proof techniques include van Lambalgen's theorem on independent random sequences, measure preserving transformations, an application of network flow theory, a Kolmogorov complexity lower bound argument, and a nonconstructive proof that this bound is tight.