Effective dimensions and relative frequencies

摘要

Consider the problem of calculating the fractal dimension of a setX consisting of all infinite sequences S over a finite alphabet Σ that satisfy some given condition P on the asymptotic frequencies with which various symbols from Σ appear in S. Solutions to this problem are known in cases where (i) the fractal dimension is classical Hausdorff or packing dimension (by work of Volkmann and Olsen), or (ii) the fractal dimension is effective (even finite-state) and the condition P completely specifies an empirical distribution π over Σ, i.e., a limiting frequency of occurrence for every symbol in Σ. In this paper, we show how to calculate the finite-state dimension (equivalently, the finite-state compressibility) of such a set X when the condition P only imposes partial constraints on the limiting frequencies of symbols. Our results automatically extend to less restrictive effective fractal dimensions (e.g., polynomial-time, computable, and constructive dimensions), and they have the classical results (i) as immediate corollaries. Our methods are nevertheless elementary and, in most cases, simpler than those by which the classical results were obtained.