Inspired by this question, I was curious about a comment in this article:
In many situations, it can be easy to apply Kolmogorov's zero-one law to show that some event has probability 0 or 1, but surprisingly hard to determine which of these two extreme values is the correct one.
Could someone provide an example?
There's a set of good examples from percolation theory: http://en.wikipedia.org/wiki/Percolation_theory
If you create a "random network" with a certain probability p of edges between nodes (see article above for precise definitions) then there is an infinite cluster with probability either zero or one. But for a given value of p it can be nontrivial to determine which.
p is between zero and one so I'm not sure the Kolmogorov theorem applies
$\endgroup$
Commented
Oct 27, 2009 at 22:23
I'm sure there must be situations where the answer is harder to determine, but the example that made me interested in the 0-1 Law (which I learned about from an excellent talk by W. Russell Mann about ten years ago) is the following:
Let $a_n$ be a sequence of real numbers (or complex numbers, or vectors in $\mathbb{R}^n$, or elements of a Hilbert space...), and let $(\epsilon_n)$ be a sign sequence, i.e., for all $n$, $\epsilon_n \in \{\pm 1\}$. Then, taking the probability space $\{ \pm 1 \}^{\infty}$ of all sign sequences [infinite direct product of the uniform probability measure on $\{\pm 1\}$], the event that the series $\sum_{n=1}^{\infty} \epsilon_n a_n$ converges is a tail event, hence has probability $0$ or $1$. The question is to find a necessary and sufficient condition on the original series $\sum_n a_n$ for this probability to be $1$.
The Rademacher-Paley-Zygmund Theorem answers this question. A discussion (not a proof!) of this theorem and related problems is given here:
I was just looking through a book which proves many interesting and rather difficult results on Brownian motion (pdf link, website link), and it seems that the Kolmogorov zero-one law applies to most of these.
Using Fourier transforms, a standard Brownian motion Xt on the range 0≤t≤1 can be decomposed as $$ X_t = At + \sum_{n=1}^\infty\frac{1}{\sqrt{2}\pi n}\left(B_n(\cos 2\pi nt - 1)+C_n\sin 2\pi nt\right) $$ where A, Bn, Cn are independent normals with mean 0 and variance 1. It follows that any property of the Brownian motion which is unchanged under addition of a linear combination of sines, cosines and linear terms is a tail event and, by Kolmogorov's zero-one law, has probability zero or one. Eg, Brownian motion is known to be nowhere differentiable (with probability 1).
It gets more interesting if you look at the modulus of continuity of Brownian motion. For any time t, the Law of the iterated logarithm says that $$ \limsup_{h\downarrow 0}\frac{|X_{t+h}-X_t|}{\sqrt{2h\log\log (1/h)}}=1 $$ with probability 1. From this, you can say that, with probability one, Brownian motion satisfies this limit almost everywhere (but not everywhere - there are exceptional times). More generally, they show that with probability one, the following are true at all times, $$ \limsup_{h\downarrow 0}\frac{|X_{t+h}-X_t|}{\sqrt{2h\log(1/h)}}\le 1,\ \limsup_{h\downarrow 0}\frac{|X_{t+h}-X_t|}{\sqrt{h}}\ge 1. $$ With probability one, these bounds are achieved. Times where the left inequality is an equality are fast times and slow times are when the right one is an equality. In the book I linked, they calculate lots of stuff about these fast and slow times, such as their fractal dimensions.
According to my decomposition of Brownian motion above, all of these definitions and statements are about tail events and we know that they must have probability 0 or 1 of being true. In fact, the sets of slow and fast times are defined in terms of tail events, so any measurable statement about these sets must be either always true or always false with probability one, and any measurable function of them, such as their fractal dimensions, must be deterministic constants with probability one, even though it is hard to calculate what they are. The same goes for many of the other properties of Brownian motion in the book I linked - they are tail events and therefore always true or false with probability one.
Complexity theory provides tons of examples of this phenomenon.
Using Kolmogorov's zero-one law, one can show that Pr{AX = BX} is 0 or 1, where AX is the class of problems that can be solved by the complexity class A with oracle access to the language X. X is chosen uniformly over all languages. (The set of all languages is basically the powerset of Z, thus one can think of this set as [0,1], and then rephrase the probabilistic statement as a statement about the measure of the set to make it more precise.)
Although we know the answer to this question for some sets of complexity classes, like P and NP (Pr{PX = NPX}=0), I'm sure there are many complexity classes for which we don't know the answer.
I can't seem to reply to Martin's response so I'm making a new one.
The first question one asks in percolation theory is whether an infinite open cluster exists. The zero-one law applies because as David Speyer said above, the existence of an infinite cluster is invariant under finite changes of edges. Equivalently, existence of an infinite cluster is a translation-invariant event. Thus this probability is zero or one, but depends on p, the parameter of the system (the probability a given bond is open). The beautiful theorem is that there is a critical parameter pc which only depends on the lattice structure.
One also studies the function
θ(p) = Pp( 0 is part of an infinite open cluster ).
Certainly, if p < pc, then θ(p) = 0 since there is no open cluster for 0 to be part of. For other values of p, θ(p) need not be equal to one, because the zero-one law does not apply: you can cut 0 off from an infinite cluster by finitely-many changes (make the bonds around 0 closed); similarly, the event is not translation-invariant.
As an aside, David's example above is critical percolation on the lattice Z2, where pc = 1/2 (this value is non-trivial; Kesten proved it years after Hammersley presented the model).
