From Gales to Covers
This post continues to study relationship between definitions of Hausdorff dimension obtained through covers and gales. In the last post, we have shown how to switch from covers to gales, which allowed us to conclude that
\[
\inf G(X) \le \dim_H(X)
\]
So now our aim should be verification of reverse inequality, i.e. $\dim_H(X)\le \inf G(X)$. In order to do this, we go back to definitions. Let us start with basics $\mathcal{C} = \{0,1\}^{\mathbb{N}}$ is Cantor space with some subset $X$. Let $d$ be an $s$-gale which succeeds on $X$, i.e. $X\subseteq S^{\infty}[d]$. This means that $\inf G(X)\le s$. Furthermore, for any given $\epsilon>0$, one could choose $s$ such that $\inf G(X)\ge s-\epsilon$. Given such $s$, we claim that $\mathcal{H}^s(X)=0$, i.e.
\[
\inf\{\sum_{i=1}^{\infty}diam(C_{w_i})^s \} = 0
\]
where $X\subseteq \bigcup C_{w_i}$. This would give us $\dim_H(X)\le s \le \inf G(X) + \epsilon$. By letting $\epsilon\to 0$, the desired inequality follows. So our main goal is to prove the above claim about $\mathcal{H}^s(X)$ being zero. The idea is consider a whole family of covers, each of which results in smaller values for target expression.
Building $C_i$
Given $i\in\mathbb{N}$, we try to build a cover $C_i = \{C_{w_j}\}_{j=1}^{\infty}$ such that $\sum_{j=1}^{\infty}(diam(C_{w_j}))^s \le 2^{-i}$. Recall that $s$-gale satisfies the following condition:
\[
d(w0) + d(w1) = 2^s d(w)
\]
Let us assign a measure for each class generated by a string $w$ as
\[
\mu^*(w) = 2^{-\vert w \vert s}
\]
Then we define so called 'mass' of a string which involves above measure and the $s$-gale.
\[
M(w) = \mu^*(w)d(w)
\]
Observe that $M$ satisfies following nice property
\[
M(w0) + M(w1) = M(w)
\]
In other words mass of string preserves under extensions. Now we are ready to construct a cover $C_i$. We specify strings in $C_i$ with the following condition
\[
L = \{w\mid d(w)\ge 2^i,\,\forall \sigma\prec w(d(\sigma)<2^i) \}
\]
It is analog of first hitting times from probability theory. We have that $L$ is a prefix-free language. Moreover, $X\subseteq \bigcup_{w\in L}C_w$. We are left to show that
\[
\sum_{w\in L} \mu^*(w)\le 2^{-i}
\]
Observe that it suffices to show above for any finite subset of $L$. Let $F$ be a finite subset of $L$. Due to preservation of mass property, we have that $\sum_{w\in F}M(w)\le 1$. Moreover, one has $d(w)\ge 2^i$ for any $w\in F$. Hence, it immediately follows that $\sum_{w\in F}\mu^*(w)\le 2^{-i}$. Since one can construct such covers for any $i\in \mathbb{N}$, the claim holds.
Conclusion
In this way we have verified equivalence of Hausdorff dimensions obtained in a classical way and that of gales. This shows that measure-theoretic properties are closely linked to predictability properties, if we are to interpret $s$-gales as kind of predicting machines.
\[
\inf G(X) \le \dim_H(X)
\]
So now our aim should be verification of reverse inequality, i.e. $\dim_H(X)\le \inf G(X)$. In order to do this, we go back to definitions. Let us start with basics $\mathcal{C} = \{0,1\}^{\mathbb{N}}$ is Cantor space with some subset $X$. Let $d$ be an $s$-gale which succeeds on $X$, i.e. $X\subseteq S^{\infty}[d]$. This means that $\inf G(X)\le s$. Furthermore, for any given $\epsilon>0$, one could choose $s$ such that $\inf G(X)\ge s-\epsilon$. Given such $s$, we claim that $\mathcal{H}^s(X)=0$, i.e.
\[
\inf\{\sum_{i=1}^{\infty}diam(C_{w_i})^s \} = 0
\]
where $X\subseteq \bigcup C_{w_i}$. This would give us $\dim_H(X)\le s \le \inf G(X) + \epsilon$. By letting $\epsilon\to 0$, the desired inequality follows. So our main goal is to prove the above claim about $\mathcal{H}^s(X)$ being zero. The idea is consider a whole family of covers, each of which results in smaller values for target expression.
Building $C_i$
Given $i\in\mathbb{N}$, we try to build a cover $C_i = \{C_{w_j}\}_{j=1}^{\infty}$ such that $\sum_{j=1}^{\infty}(diam(C_{w_j}))^s \le 2^{-i}$. Recall that $s$-gale satisfies the following condition:
\[
d(w0) + d(w1) = 2^s d(w)
\]
Let us assign a measure for each class generated by a string $w$ as
\[
\mu^*(w) = 2^{-\vert w \vert s}
\]
Then we define so called 'mass' of a string which involves above measure and the $s$-gale.
\[
M(w) = \mu^*(w)d(w)
\]
Observe that $M$ satisfies following nice property
\[
M(w0) + M(w1) = M(w)
\]
In other words mass of string preserves under extensions. Now we are ready to construct a cover $C_i$. We specify strings in $C_i$ with the following condition
\[
L = \{w\mid d(w)\ge 2^i,\,\forall \sigma\prec w(d(\sigma)<2^i) \}
\]
It is analog of first hitting times from probability theory. We have that $L$ is a prefix-free language. Moreover, $X\subseteq \bigcup_{w\in L}C_w$. We are left to show that
\[
\sum_{w\in L} \mu^*(w)\le 2^{-i}
\]
Observe that it suffices to show above for any finite subset of $L$. Let $F$ be a finite subset of $L$. Due to preservation of mass property, we have that $\sum_{w\in F}M(w)\le 1$. Moreover, one has $d(w)\ge 2^i$ for any $w\in F$. Hence, it immediately follows that $\sum_{w\in F}\mu^*(w)\le 2^{-i}$. Since one can construct such covers for any $i\in \mathbb{N}$, the claim holds.
Conclusion
In this way we have verified equivalence of Hausdorff dimensions obtained in a classical way and that of gales. This shows that measure-theoretic properties are closely linked to predictability properties, if we are to interpret $s$-gales as kind of predicting machines.
Comments
Post a Comment