Hausdorff dimension of non-recurrent walks

Question

Preface: I am fairly new to the concept of Hausdorff dimension, so I don't know how interesting a question this is.

Identify walks on $\mathbb{Z}$ with infinite binary sequences (say $0$ means moving left, $1$ means moving right). It is then well-known that, in the Cantor space $2^\mathbb{N}$ under the Lebesgue measure, the set $A$ of non-recurrent walks -- i.e. those sequences $x$ for which $\frac{\sum_{k=1}^n x(k)}{n} = \frac{1}{2}$ for only finitely many $n$ -- is null. I am curious as to the Hausdorff dimension of this set, but I do not see how to figure this. Thus my question:

What is the Hausdorff dimension of the set $A$ of non-recurrent walks?

Perhaps this too is already well-known, but if so I could not locate the result. I hope this question is not trivial, though if it is at least I will have learned that. I look forward to any replies; this seems like a marvelous site!

Answer 1

First of all the dimension of the space. You didn't give the metric you want to use, so I'll use my favourite one: two points are at distance $2^{-n}$ if they first disagree in the $n$th symbol. The 1-Hausdorff measure agrees with coin-flipping measure so that the full space has Hausdorff dimension 1.

Now for the non-recurrent subset. It's also of Hausdorff dimension 1. Probably the simplest way to see this is to use some technology: consider the measure $\mu_\alpha$ that is coin-flipping with weights $\alpha$ and $1-\alpha$. Clearly for $\alpha\ne1/2$ this measure is supported on the non-recurrent set. But the Hausdorff dimension of the measure is $(-\alpha\log\alpha-(1-\alpha)\log(1-\alpha))/\log 2$. This is a lower bound for the Hausdorff dimension of the non-recurrent set. But as $\alpha\to1/2$, this lower bound converges to 1.

In case you have an aversion to dynamical systems there is a way to do this with a single (non-invariant) measure and get the result without taking any limits. Let $n_1 < n_2 < \ldots$ be a sequence of density 0 such that the number of terms up to $N$ ($T(N)$ say) grows faster than $\sqrt{3N\log\log N}$ (e.g. $(n_i)$ is the sequence $\lfloor i^2/\log i\rfloor$). Now build the measure that is fair coin-tossing at each $n$ except at the $n_i$ when you always put a 1. Since the fair part of the process puts you in the range $\pm\sqrt{(2+\epsilon)N\log\log N}$ for all sufficiently large $N$ (by the Law of the Iterated Logarithm), the unfair part of the process guarantees that you only return to 0 finitely many times. Hence this measure is supported on the non-recurrent set. This measure has Hausdorff dimension 1: the measure of a $2^{-N}$ neighbourhood of a typical point is $2^{-N+T(N)}$. The Hausdorff dimension is the limit of $\log(2^{-N+T(N)})/\log(2^{-N})$. The fact that $T(N)=o(N)$ guarantees that the Hausdorff dimension is 1.

Answer 2

Anthony's answer settles the matter, but I'll say a few words about relevant terminology and references that are too long to fit in the comment box. (And go a bit beyond what you actually asked, but may give things some context.)

This is essentially a question in multifractal analysis. Given an asymptotic property such as "the asymptotic frequency of ones is bounded away from 1/2", one can study the set of points with this property in different ways. If you study the measure of this set, you're doing ergodic theory; if you study the dimension of this set, you're doing multifractal analysis.

In your setting, a natural thing to do is to fix $\alpha \in [0,1]$ and to consider the set $K_\alpha = \{ x \mid \frac 1n \sum_{k=1}^n x(k) \to \alpha \}$. (Each set $K_\alpha$ is contained in your non-recurrent set.) Then $2^{\mathbb{N}} = (\bigcup_{\alpha\in [0,1]} K_\alpha) \cup \hat K$, where $\hat K$ is the set of points $x$ for which $\lim \frac 1n \sum_{k=1}^n x(k)$ does not exist. This is an example of a multifractal decomposition. One can show that the measures $\mu_\alpha$ in Anthony's answer have the property that $\mu_\alpha(K_\alpha)=1$ and $$ \dim_H K_\alpha = \dim_H \mu_\alpha = \frac{-\alpha\log \alpha - (1-\alpha)\log (1-\alpha)}{\log 2}. $$ Thus the function $\alpha \mapsto K_\alpha$ is an analytic and concave function of $\alpha$; this is an example of a multifractal spectrum. There are lots of these, associated to various asymptotic quantities, and you can find a lot of subtle behaviour. (For example, one can ask how big the set $\hat K$ is, and it turns out that even though it is null for every shift-invariant measure on $2^\mathbb{N}$, it still has full Hausdorff dimension.)

For more on this, you can see the book "Dimension Theory in Dynamical Systems", by Yakov Pesin -- the first few chapters are very abstract and difficult to follow if you're not already pretty familiar with some of the basic ideas in dimension theory, but you can also skip straight to the chapters on multifractal analysis and get an idea of what's going on. There's also a survey paper by Barreira, Pesin, and Schmeling from 1997 or thereabouts that is a good introduction.