# Paths on $\mathbb{Z}^d$

Let's say a path must be non-self-intersecting, and that we have the usual lattice structure. Then if $\sigma(n)$ is the number of paths of length $n$ then why do we have convergence of the sequence $\sigma(n)^{(1/n)}$ as is asserted in Grimmett's "Percolation?"

The same book also asserts that the property of having a path of length infinity is a tail-measurable event relative to the random variables that return value $1$ on open edges and $0$ on closed edges in the context of bond percolation on $\mathbb{Z}^d$. I was hoping for a completely detailed explanation of why this is true. It seems intuitively obvious because the event of having an infinite cluster should not depend on any finite list of the RVs, as the author notes. But this event is only expressible as an uncountable union of elementary cylinders of the form $X_K=a_K$, $X_{K+1}=a_{K+1}$, etc.

I also want to make sure, as this is relevant to the second question, that when people talk about random graph theory, and thus graph-valued RVs, the implied sigma algebra on the space of subgraphs of a given graph ought to be the countable-cocountable sigma algebra. is that true?

• Regarding the second question, I'm not sure I fully understand the question, but aren't there only countably many elementary cylinders? – Sean Eberhard Apr 5 '13 at 23:48
• I am including any cylinders, not just finite dimensional ones. You need to control infinitely many (the tail end) to have any hope, but then there are uncountably many of these. – Jeff Apr 5 '13 at 23:54
• To clarify, then, we're not really concerned about tail-measurability in particular, but we would just like to know why "having an infinite path" is measurable at all? I guess it's pretty clear that "having arbitrarily long paths" is measurable, and similarly "having an infinite cluster" is measurable, but I agree that whether "having an infinite path" is measurable is less obvious. – Sean Eberhard Apr 6 '13 at 0:24
• If my previous comment correctly identified the issue, then the following hint may help: Having an infinite path starting at $0$ is the same as having arbitrarily long paths starting at $0$. (This is not completely trivial.) – Sean Eberhard Apr 6 '13 at 0:31
• That is not the problem. I only care about tail measurability. It is clear to me that having an infinite cluster is measurable relative to the product sigma algebra defined in the text. Maybe I'm missing something entirely obvious. But the book simply makes the intuitive remark that "having an infinite cluster doesn't depend on the first finitely many edges." (If you enumerate them.) Now, I can "write down all the examples" of subgraphs of the lattice that have an infinite cluster, and each of these would indeed be a list of requirements that, say, $X_{500}=0, X_{501}=1, ...$ – Jeff Apr 6 '13 at 0:35

Question 1.

This is an example of the omnipresent "Fekete's subadditive lemma", which states that if $f:\mathbb{N}\to\mathbb{R}$ is a function satisfying $f(m+n)\leq f(m)+f(n)$ then $f(n)/n$ converges to $\inf_m f(m)/m$ as $n\to \infty$. Proving this is a good Analysis I exercise.

In this case, let $\sigma(n)$ be the number of non-self-intersecting paths of length $n$ in $\mathbb{Z}^d$ starting at $0$. Observation: If we have a legal path of length $m+n$ then we can think of it as a legal path of length $m$ followed by a legal path of length $n$. Moreover the original path of length $m+n$ is completely determined by these two paths, so $\sigma(m+n)\leq\sigma(m)\sigma(n)$. (There is a further restriction that the latter path not intersect the former path, so equality need not hold.)

It follows that $f(n) = \log \sigma(n)$ is subadditive, so by the subadditive lemma $f(n)/n$ converges to $\inf_m f(m)/m$. Exponentiating, $\sigma(n)^{1/n}$ converges to $\inf_m \sigma(m)^{1/m}$.

Question 2.

Following our discussion in the comments, this may help.

In detail, the reason the event "has an infinite cluster" is measurable at all (i.e., with respect to $\sigma(X_1,X_2,\dots)$) is that it is the union of the countably many measurable events "has arbitrarily large clusters containing $e$", where $e$ ranges over all possible edges. But note equally that it is the union of the countably many events "has arbitrarily large clusters containing $e$, even after erasing any of the first $499$ edges", where $e$ ranges over all possible edges except the first $499$. This latter description is manifestly in $\sigma(X_{500},X_{501},\dots)$.