Dimension and Relative Frequencies

Details Dimension and Relative Frequencies Dimension and Relative Frequencies

2007-03-16

arxiv.org/abs/cs/0703085v1

Computer Science

Computational Complexity

Scientific paper

We show how to calculate the finite-state dimension (equivalently, the finite-state compressibility) of a saturated sets $X$ consisting of {\em all} infinite sequences $S$ over a finite alphabet $\Sigma_m$ satisfying some given condition $P$ on the asymptotic frequencies with which various symbols from $\Sigma_m$ appear in $S$. When the condition $P$ completely specifies an empirical probability distribution $\pi$ over $\Sigma_m$, i.e., a limiting frequency of occurrence for {\em every} symbol in $\Sigma_m$, it has been known since 1949 that the Hausdorff dimension of $X$ is precisely $\CH(\pi)$, the Shannon entropy of $\pi$, and the finite-state dimension was proven to have this same value in 2001. The saturated sets were studied by Volkmann and Cajar decades ago. It got attention again only with the recent developments in multifractal analysis by Barreira, Saussol, Schmeling, and separately Olsen. However, the powerful methods they used -- ergodic theory and multifractal analysis -- do not yield a value for the finite-state (or even computable) dimension in an obvious manner. We give a pointwise characterization of finite-state dimensions of saturated sets. Simultaneously, we also show that their finite-state dimension and strong dimension coincide with their Hausdorff and packing dimension respectively, though the techniques we use are completely elementary. Our results automatically extend to less restrictive effective settings (e.g., constructive, computable, and polynomial-time dimensions).

Affiliated with

Also associated with

No associations

Rating

Dimension and Relative Frequencies does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Dimension and Relative Frequencies, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Dimension and Relative Frequencies will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-679737