On Gales

-
In this post we aim to provide characterization of Hausdorff Dimension in Cantor space in terms of special function called gales. Our presentation mainly follows that of Mayordomo [1], while the notion itself is from Lutz [2].

Gales
Let us first go through definitions of supergales and gales. Take $s\in [0, \infty)$.
An $s$-supergale is a function $d:\{0,1\}^*\to [0,\infty)$ such that:
\[
d(w) \ge 2^{-s}\left[ d(w0) + d(w1) \right]
\]
for all $w\in \{0,1\}^*$. A definition $s$-gale is similar to the above, except for the equality sign in place of the inequality sign for each $w\in \{0,1\}^*$. A supermartingale is $1$-supergale, while a martingale is an $1$-gale.
As for names, they seem to derive from a notion of martingale from probability theory. A parameter $s$ describes fairness of the betting game. Observe that the condition for $s$-gale can be rewritten as:
\[
E[d(wb)] = \frac{1}{2}d(w0) + \frac{1}{2}d(w1) = 2^{s-1}d(w)
\]
Depending on the value of $s$, the game can be

  • Unfair, if $s<1$;
  • Fair, if $s=1$;
  • More than fair, if $s>1$.


 Success criteria
 We say that $d$ succeeds on a sequence $S\in C$ if
 \[
 \limsup_{n\to \infty} d(S[0,\ldots n-1]) = \infty
 \]
 Based on the above criteria, one could define a covering set of $d$
 \[
 S^{\infty}[d] = \{S\in C\mid s \text{ suceeds on } S\}
 \]
 For a class $X\subseteq C$, we then define a sets $G(X)$ and $\widehat{G}(X)$
 \[
 G(X) = \{s\in \mathbb{R}^{\ge 0}\mid \text{ there is s-gale succeeding on } X  \}
 \]
 and
\[
\widehat{G}(X) = \{s\in \mathbb{R}^{\ge 0}\mid \text{ there is s-supergale succeeding on } X  \}
\]
Note that if we have two reals $s<s'$ and $d$ is a $s$-(super)gale, then $d'(w) = 2^{(s'-s)\vert w \vert}d(w)$ is $s'$-(super)gale. Hence $G(X),\hat{G}(X)$ are upward closed. Finally, we let:
\[
dim_H(X) = \inf G(X)
\]
It turns out that $\inf G(X) = \inf \widehat{G}(X)$, hence taking $\inf$ of either set will result in the same value of complexity measure. Let us end our post here. Next posts will attempt to verify equivalence between Hausdorff dimension defined in classical way and that which is defiend through gales.

References:
1. Mayordomo, Elvira. "Effective hausdorff dimension." (2000).
2. Lutz, Jack H. "Gales and the constructive dimension of individual sequences." ICALP. Vol. 1853. 2000.

Comments

Post a Comment

Popular posts from this blog

On learning C++

-
"You are number of languages that you know" said one of the quotes attributed to Al-Farabi, which my school teacher used to tell us. Indeed almost all languages describe the same objects: humans, animals, nature and universe in general. However, the way each language does so might differ from another one. This difference makes learning new languages fun. A somewhat similar statement can be said about programming languages. Almost all of them perform some kind of logical and computational transformations on given data, however the ways they do so might significantly differ. Having learnt some Python to play with Machine Learning (ML) algorithms, I wanted to explore other programming languages. The first language which came to mind was C++. It is one of the languages used to code massive and complex software systems. So did I explored using a website  https://www.programiz.com/cpp-programming . How it went The installation part went easy. The application XCode does a solid ...
Read more

On ideas behind Bayesian Learning

-
When one reads about Machine Learning (ML) or Artificial Intelligence (AI) it is common to come across a list of approaches to AI such as: symbolic reasoning, Bayesian learning, artificial neural networks and so on. Seeing this list I was puzzled with a notion of Bayesian Learning. The only thing I knew with a name Bayes in its name was a famous Bayes's theorem which states that \[ P(H\mid E) = \frac{P(E\mid H)P(H)}{P(E)} \] where $P(H)$ and $P(H\mid E)$ denote prior and posterior probabilities of hypothesis $H$, respectively. What puzzled me is the application of such a simple looking formula to draw patterns from data. In order to learn basic principles of Bayesian learning, I decided to consult Wikipedia and few online tutorials. This post is about results of this exploration. Wikipedia says Bayesian learning (inference?) is a method of statistical inference in which Bayes's theorem is used to update the probability for a hypothesis as more evidence or informatio...
Read more

Neural Networks as Morphisms

-
Image
Abstract This set of notes attempts to study possibility of constructing categories with neural nets as morphism and functors. The reason for such construction comes stems from possible enriching connections between category theory and deep learning. Usually Category Theory is used to formalize abstractions of the given concrete objects. On the other hand, Deep Learning is mostly used in constructing explicit neural network based mappings between various spaces given by sampled datasets. The notes explores if it is possible to leverage on strengths of category theory and deep learning in order to represent more abstract concepts and processes. Introduction Motivation: The main motivation for development of framework if two folds. Firstly, it might shed a new light for representing more abstract objects, such as movements and processes. Secondly, we leverage on rich experience of building deep neural nets accumulated in Machine Learning community. Abs...
Read more