Extractable patterns

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...

In this post we attempt to understand a relationship between Hausdorff dimension defined in a classical way and Hausdorff dimension defined using gales. Recall that classical Hausdorff dimension is defined in terms of covers. So, in order to understant that relationship, we need to be able to 'switch' back and forth from covers and gales. In this post we will try to switch from covers to gales. As before, we work in Cantor space $\mathcal{C} = \{0,1\}^{\mathbb{N}}$. We start with some subset $X\subseteq \mathcal{C}$. For any given $\varepsilon>0$, one can choose $s\ge 0$ such that $s-\varepsilon < \dim_H(X) < s$. Then we go on to show that there $s$-gale succeeding on $X$, i.e. $\inf G(X)\le s$. Combining this with above inequality, we have \[ \inf G(X)\le s < \dim_H(X) + \varepsilon \] By letting $\varepsilon \to 0$, one shows that $\inf G(X)\le \dim_H(X)$. So, we are left to show that it is indeed possible to construct $s$-gale given the fact that $\dim...

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 ca...

In some of previous posts we have discussed regular languages and automatic relations from automata theory. This discussion were meant to lead to the upcoming discussion of automatic groups. Groups are one of the most fundamental algebraic structures arising almost everywhere in mathematics. Why to study automatic group? Well this kind of research arouse around sixties when Rabin and others asked what would happen if we impose some kind of algorithmic conditions on mathematical structures. First people studied heavily so called computable structures, i.e. structures recognized by computable functions. These days people study structures under all sorts of algorithmic constraints. Some study in computable constraints, some go beyond and look at Turing machines which work with reals, while some people, like me, study structures with automata-theoretic constraints. One of the first people who have done that are Hodgson, Khoussainov and Nerode. There are several variants of studying...

Introduction People like to measure things. In mathematical analysis there is a notion of measure studied in Measure theory . In Topology we have a notion of topological dimension . In Information Theory we have a notion of entropy . In Computational Complexity Theory we have notions of time and space complexities . So the general idea is to quantify size or complexity of the given object. Then we can talk about whether this object is somehow bigger/more complex than the other object. In this post I would like to say few things about Hausdorff dimension . Motivation Why do we need Hausdorff dimension? There are many reasons. One of the reasons people talk most is its fineness. In other words Hausdorff measure can provide some meaningful information when Lebesgue measure gives none. To see that, observe that there are many sets of measure $0$. A single point is of measure $0$ and a Cantor space is of measure $0$. However, it is clear that those two are completely different objec...

Several posts ago, we have talked about SVMs. In particular how it is possible to formulate SVM objective as optimization technique. In this post we are going to learn about Lagrange Duality, an optimization method, which is going to help us to solve the optimization problem we ended up with last time. Let us start with a simpler optimization problem given as: \[ \min_w\, f(w) \] subject to constraints: \[ h_i(w) = 0, \quad i=1,\ldots, l. \] The classical way to solve such a problem is to write a Lagrangian function: \[ L(w,\beta) = f(w) + \sum_{i=1}^l \beta_i h_i(w) \] and set \[ \frac{\partial L}{\partial w_i} = 0, \quad \frac{\partial L}{\partial \beta_i}=0 \] This works because at critical points of $L(w,\beta)$ we must have $h_i(w)=0$ for all $i$. Now let us consider a more complex optimization problem: \[ \min f(w) \] subject to constraints: \[ g_i(w) \le 0, \quad i = 1,\ldots,k \] and \[ h_j(w) = 0,\quad j = 1,\ldots,l \] Let us call the above pr...

In one of the previous posts we have gone through a concept of  regular languages. These languages are quite convenient to work with and have a great deal of good properties, which might be the topic for another post. In this post I would like to focus on automatic relations. This notion tries to extend regularity from unary relation to $k$-ary relations. So instead of asking if $x\in L$ for a given regular language $L$, we ask $(x_1,x_2,\ldots,x_n)\in R$ for a some relation $R$. Suppose $R\subseteq (\Sigma^*)^n$ be some $n$-ary relation. Our aim is to check a membership of the tuple $(x_1,x_2, \ldots, x_n)$ in $R$. For this we stack or \emph{convolute} these words, so that it might look like this in the case of $n=4$: \[ \begin{bmatrix} 1 & 0 & 0 & 1 & 1\\ 0 & 1 & 1 & & \\ 1 & & & &\\ 1 & 0 & 0 & & \end{bmatrix} \] Observe that above block is nonuniform in length, so it cannot be generated by the tuple...