Energy randomness

Joseph S. Miller, Jason RutearXiv 2015 · arXiv

Abstract

This research establishes a fundamental link between potential theory and algorithmic information theory by providing a precise characterization of "energy randomness." By utilizing a priori complexity ($KM$), the authors demonstrate that a sequence is $s$-energy random if and only if a specific infinite sum involving its initial segment complexity converges. This result provides a theoretical analogue to the Ample Excess Lemma and offers a new framework for understanding the behavior of Martin-Löf random closed sets and Brownian motion.

Introduction

In the field of computability theory, algorithmic randomness has traditionally been defined using the standard fair-coin (Lebesgue) measure on infinite binary sequences. However, as the field has matured, researchers have sought to characterize more complex probabilistic objects, such as Martin-Löf random closed sets and the zero sets of Martin-Löf random Brownian motion.

To analyze these objects, the concept of $s$-energy randomness was introduced—a notion rooted in potential theory that relates to the effective Hausdorff dimension of a set. Despite its utility, a significant open question remained: could energy randomness be characterized purely through the lens of algorithmic complexity? This paper answers that question, providing a bridge between the analytic tools of potential theory and the discrete measures of Kolmogorov complexity.

Theoretical Framework: Potential and Capacity

The authors approach the problem by generalizing $s$-energy randomness to $f$-energy randomness, where $f$ is a function mapping natural numbers to non-negative reals. In the standard case, $f(n) = 2^{sn}$. The study relies on three core concepts from potential theory:

  1. $f$-potential and $f$-energy: These define the "cost" or energy of a measure. A sequence is considered random with respect to a measure if that measure has finite energy.
  2. $f$-capacity: This serves as a size metric for subsets of sequences, analogous to standard probability measures but without the requirement of perfect additivity.
  3. Effective Approximation: A primary technical challenge is that $f$-capacity is not perfectly computable. The authors resolve this by demonstrating that for "amicable" (well-behaved, non-decreasing) functions $f$, the capacity of open sets can be effectively approximated from below by left-computably enumerable (left-c.e.) measures.

By constructing these left-c.e. measures, the authors build statistical tests that link capacity-based randomness to the universal left-c.e. semimeasure, which forms the basis of a priori complexity ($KM$).

The Complexity Characterization

The central contribution of this work is a theorem that mirrors the famous Ample Excess Lemma (which characterizes standard Martin-Löf randomness via prefix-free Kolmogorov complexity).

Main Theorem

For a computable real number $s \in (0, 1)$, a sequence $X$ is $s$-energy random if and only if: $$\sum_{n\in\omega} 2^{sn - KM(X \upharpoonright n)} < \infty$$ Where $KM(X \upharpoonright n)$ represents the a priori complexity of the first $n$ bits of $X$.

This result reveals that energy randomness is not merely an abstract probabilistic property but is strictly determined by the compressibility of a sequence's initial segments. If the complexity $KM$ stays sufficiently high relative to the growth of $2^{sn}$, the sum converges, and the sequence is deemed $s$-energy random.

Generalization to $f$-energy

The authors further extend this to broader classes of functions. If a function $f$ is amicable and its sum converges appropriately, a sequence $X$ is $f$-energy random if and only if: $$\sum_{n\in\omega} f(n)2^{-KM(X \upharpoonright n)} < \infty$$

Implications for Multidimensional Spaces

While much of the foundational work in algorithmic randomness focuses on binary sequences (Cantor space), this paper successfully extends its findings to sequences over any finite alphabet. This extension is mathematically significant because it allows the theory to be applied to multidimensional Euclidean spaces ($\mathbb{R}^d$). This provides the necessary groundwork for classifying the zero times of multidimensional Martin-Löf random Brownian motion, a topic the authors identify as a primary focus for subsequent research.

Conclusion and Limitations

The characterization of energy randomness via $KM$ complexity provides a robust new tool for the study of fractal measures and random sets. However, the authors note a specific limitation: the current proofs rely on the dimension $s$ being a computable real number. The techniques employed do not yet generalize to noncomputable dimensions, representing an open area for future investigation.

By proving that energy randomness is a property of algorithmic compressibility, this work reinforces the deep symmetry between the continuous world of potential theory and the discrete world of information theory.

Summary updated

BibTeX
@misc{miller2015energy,
  author = {Joseph S. Miller and Jason Rute},
  title = {{Energy randomness}},
  year = {2015},
  eprint = {1509.00524},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1509.00524},
}
Figure