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



non-integrable subadditive ergodic theorem
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.


