non-integrable subadditive ergodic theorem

Question

Dear MO_World,

I have (another) question about relaxing the assumptions in the sub-additive ergodic theorem. Apologies if this is something I should know already...

There are a number of statements of the Kingman sub-additive ergodic theorem and its extensions. Here is a fairly typical version:

Let $T\colon X\to X$ be a measure-preserving transformation of a probability space. Let $(f_n)$ be a sequence of measurable functions from $X$ to $[-\infty,\infty)$ satisfying $f_{n+m}(x)\le f_n(x)+f_m(T^nx)$ for every $m,n\in\mathbb N$ and $x\in X$. Suppose further that $f_1^+$ is integrable. Then $f_n(x)/n$ is convergent for almost every $x$.

There are also statements about convergence in the mean in certain situations, but I focus on pointwise convergence.

My general question is: When can you remove the integrability assumption?

In the following example the conclusion holds, even though the hypothesis fails. Consider a distribution on the positive reals so that if $(X_n)$ is a sequence of iid random variables with the given distribution, then $\mathbb E(\min(X_1,X_2,\ldots,X_n))=\infty$ for all $n$. (As an example, consider a random variable that takes the value $2^{k^3}$ with probability $2^{-k}$ for each $k\ge 1$. Let $M_n$ be $\min(X_1,X_2,\ldots,X_n)$. Then $\mathbb P(M_n=2^{k^3})\approx 2^{-nk}$ so that $\mathbb E M_n=\infty$.

Let $\Omega= \lbrace 2^{k^3}\colon k\ge 1 \rbrace ^\mathbb Z$ equipped with the Bernoulli probability measure arising from the distribution above. Now define the sequence $f_n(\omega)$ as follows: $f_{2n}(\omega)=0$; $f_{2n+1}(\omega)=\min_{0\le j\le 2n+1}\omega_j$. This sequence of functions is clearly sub-additive. Also $0\le f_n(\omega)/n\le \omega_0/n$, so that $f_n/n\to 0$ everywhere.

My specific question is as follows:

Suppose that $(f_n)$ is a sub-additive sequence of functions taking values in $[-\infty,\infty)$. If we assume that $\limsup f_n(x)/n \lt \infty$ a.e., then does it follow that $f_n(x)/n$ converges almost surely? [ The above example shows that we cannot expect convergence in norm, even if the $f_n$ are non-negative ]

Answer 1

I think I have a counterexample, though it turned out to be more intricate than I first expected.

The space $X$ is the 2-adics ${\bf Z}_2$ with the usual probability Haar measure and the shift $Tx := x+1$. To describe the functions $f_n$, we will put a weighted directed graph on $X$, that is to say a number of edges $a \to b$ with $a,b \in X$ and some weight $w$ (which will be a non-negative real). It will be convenient to allow multiple edges from $a$ to $b$. This weighted graph defines a (possibly infinite) pseudoquasimetric $d: X \times X \to [0,+\infty]$, with $d(a,b)$ being the infimum of the total weights of directed paths from $a$ to $b$. We then set $f_n(x) := d(x,x+n)$; this is a subadditive sequence taking values in $[0,+\infty]$. (We will set things up so that $f_1$, and hence all higher $f_n$, are almost surely finite, at which point one can make them surely finite by modification on a null set.)

Now to set up the weighted graph. For each $x \in {\bf Z}_2$, we define the $2$-adic norm $\|x\| := 2^{-n}$, where $n$ is the largest natural number such that $2^n$ divides $x$ (i.e. $x \in 2^n {\bf Z}_2$.

1. Red edges: directed edges from $x$ to $x+h$ of weight $h$, where $x \in {\bf Z}_2$ and $h$ is a natural number with $h \geq \|x\|^{-100}$.
2. Green edges: directed edges from $x$ to $x+1$ of weight $\|x\|^{-100}$, where $x \in {\bf Z}_2$.
3. Blue edges: directed edges from $x$ to $x+h$ of weight $0$, where $x \in {\bf Z}_2$, $m$ is a natural number with $2^m \geq \|x\|^{-100}$, and $h$ is the first natural number for which $x+h$ is divisible by $2^m$.

(These edges are a little pathological when $x=0$, but this case will almost surely not occur for us.)

From the green edges we see that $f_1(x) \leq \|x\|^{-100}$, so $f_1$ is almost surely finite, and so $f_n$ is almost surely finite also.

From the blue edges we see that $f_h(x) = 0$ whenever $2^m \geq \|x\|^{-100}$ and $h$ is the first natural number for which $2^m | x+h$. As such we see that $\lim \inf_{n \to \infty} f_n(x)/n \leq 0$ for almost every $x$.

From the red edges we see that $f_h(x) \leq h$ whenever $h \geq \|x\|^{-100}$. As such we see that $\lim \sup_{n \to \infty} f_n(x)/n \leq 1$ for almost every $x$.

To finish the counterexample, we claim that for almost every $x$, one has $f_n(x) \geq n/2$ for all sufficiently large n with $x+n$ odd. In other words, for $x$ and $n$ as above, every directed path from $x$ to $x+n$ has total weight at least $n/2$. The reason for this is that in this path, every blue edge cannot end at the odd number $x+n$, but must be followed by another edge. Furthermore, this edge is either a blue edge with a much larger value of $m$, a red edge that is longer than the blue edge, or a green edge whose weight is larger than the length of the blue edge. Because of this, the effect of the low-weight blue edges is outweighed by the effect of the heavier red and green edges, and the total weight has to be at least half the length of the path, which is n.

Answer 2

Having read Terry's answer, I found a counterexample of my own. It's quite a bit simpler (although less nice in the sense that the liminf is $-\infty$ rather than 0).

It's actually an additive process rather than sub-additive one. Define a transformation $T$ on $X=\mathbb N^\mathbb Z\times\lbrace 0,1\rbrace$ by $T(x,0)=(x,1)$ and $T(x,1)=(Sx,0)$ where $S$ is the shift. Define the function $f(x,0)=-x_0$ and $f(x,1)=x_0$. Let the measure on $X$ be $\mu\times c$ where $c$ is counting measure and $\mu$ is a horrendously non-integrable iid process on $\mathbb N^\mathbb Z$.

If you look at the values of $f$ along an orbit, you see the values $-x_0,x_0,-x_1,x_1,-x_2,x_2,\ldots$ if you start from an `even' point or $x_0,-x_1,x_1,-x_2,x_2,\ldots$ if you start from an odd point. In the first case the partial sums $S_nf(x)$ are always non-positive and take the value 0 infinitely often, so that $\limsup S_nf(x)/n=0$. In the second case, the partial sums $S_nf(x)$ are bounded above by $x_0$ and take this value infinitely often, so that again $\limsup S_nf(x)/n=0$.

On the other hand, in the first case, summing $2n+1$ terms, $S_{2n+1}f/(2n+1)=-x_n/(2n+1)$. If the distribution is sufficiently nasty (e.g. the $x_i$'s take the value $3^n$ with probability $2^{-n}$), you get $\liminf S_nf/n=-\infty$. Similarly in the second case, summing $2n$ terms, you see that $\liminf S_nf/n=-\infty$.

Answer 3

Assuming that you are allowing the possibility of convergence to $-\infty$, doesn't this follow from Fekete's Subadditive Lemma? At every point $x$ the sequence $(f_n(x))$ is subadditive so $$\lim f_n(x)/n=\inf f_n(x)/n.$$ I am assuming that this is what you mean when you say "a subadditive sequence of functions," but maybe I misunderstood the question.