Question

What are some interesting examples of probabilistic reasoning to establish results that would traditionally be considered analysis? What I mean by "probabilistic reasoning" is that the approach should be motivated by the sort of intuition one gains from a study of probability, e.g. games, information, behavior of random walks and other processes. This is very vague, but hopefully some of you will know what I mean (and perhaps have a better description for what this intuition is).

I'll give one example that comes to mind, which I found quite inspiring when I worked through the details. Every Lipschitz function (in this case, $[0,1] \to \mathbb{R}$) is absolutely continuous, and thus is differentiable almost everywhere. We can use a probabilistic argument to actually construct a version of its derivative. One begins by considering the standard dyadic decompositions of [0,1), which gives us for each natural n a partition of [0,1) into $2^{n-1}$ half-open intervals of width $1/{2^{n-1}}$. We define a filtration by letting $\mathcal{F}_n$ be the sigma-algebra generated by the disjoint sets in our nth dyadic decomposition. So e.g. $\mathcal{F}_2$ is generated by ${[0,1/2), [1/2,1)}$. We can then define a sequence of random variables $Y_n(x) = 2^n (f(r_n(x)) - f(l_n(x))$ where $l_n(x)$ and $r_n(x)$ are defined to be the left and right endpoints of whatever interval contains x in our nth dyadic decomposition (for $x \in [0,1)$). So basically we are approximating the derivative. The sequence $Y_n$ is in fact a martingale with respect to $\mathcal{F}_n$, and the Lipschitz condition on $f$ makes this a bounded martingale. So the martingale convergence theorem applies and we have that $Y_n$ converges almost everywhere to some $Y$. Straightforward computations yield that we indeed have $f(b) - f(a) = \int_a^b Y$.

What I really like about this is that once you get the idea, the rest sort of works itself out. When I came across the result it was the first time I had thought of dyadic decompositions as generating a filtration, but it seems like a really natural idea. It seems much more structured than just the vague idea of "approximation", since e.g. the martingale condition controls the sort of refinement the next approximating term must yield over its predecessor. And although we could have achieved the same result easily by a traditional argument, I find it interesting to see from multiple points of view. So that's really my goal here.

Answer 1

One nice example is Bernstein's proof of the Weierstrass theorem. This proof analyses a simple game: Let $f$ be a continuous function on $[0,1]$, and run $n$ independent yes/no experiments in which the “yes” probability is $x$. Pay the gambler $f(m/n)$ if the answer “yes” comes up $m$ times. The gambler's expected gain from this is, of course, $$p_n(x)=\sum_{k=0}^n f(k/n)\binom{n}{k}x^k(1-x)^{1-k}$$ (known as the Bernstein polynomial). The analysis shows that $p_n(x)\to f(x)$ uniformly.

S. N. Bernstein, A demonstration of the Weierstrass theorem based on the theory of probability, first published (in French) in 1912. It has been reprinted in Math. Scientist 29 (2004) 127–128 (MR2102260).

Answer 2

While I've forgotten most of the necessary technical details (ah for the days when I knew more about probability and less about homological algebra), one striking example is the exploitation of conformal invariance of planar Brownian motion to reprove results in complex analysis. See

Burgess Davis. Brownian Motion and Analytic Functions, Ann. Probab. Volume 7, Number 6 (1979), 913-932.

which in particular has a probabilistic proof of the little Picard theorem.

(I first learned of Davis' proof from a sketch in Körner's wonderful book Fourier Analysis, which I'd recommend for students as an antidote to the inevitable tedium and occasional narrowness of a first & second course in analysis.)

Answer 3

There are probabilistic proofs of Atiyah-Singer or most anything else that can be done with a heat kernel.

(Rogers & Williams is rife with probabilistic proofs of analytic facts [as well as the fundemental theorem of algebra], and more generally just about all of potential theory can be recast in terms of martingales a la Doob, as Qiaochu points out; surely there are many more examples.)

Answer 4

Shannon's theorem giving the capacity of noisy channel is proved using random coding. (Efficiently-computable codes are not known.)

Answer 5

See also http://en.wikipedia.org/wiki/Probabilistic_proofs_of_non-probabilistic_theorems

Answer 6

The Radon-Nikodym Theorem and the Lebesgue differentiation theorem can be proved by Martingale theory (see "Probabilty Theory" by Heinz Bauer, pp. 173-5).

Answer 7

Question: Given $n$ points in Euclidean space (which we might as well take to be $\ell_2^n$), what is the smallest $k=k(n)$ so that these points can be moved into $k$-dimensional Euclidean space via a transformation which expands or contracts all pairwise distances by a factor of at most $1+\epsilon$?

Answer: $k(n)\le C \ {\log (n+1) \over {\epsilon^2}}$.

Proof: A (suitably normalized) random rank $k(n)$ orthogonal projection works.

Nowadays this is called the Johnson-Lindenstrauss Lemma. All known proofs in a form this strong use random linear operators.

Answer 8

This paper (Prime Numbers and Brownian Motion, by Patrick Billingsley) is perhaps more about proving number theoretic facts than analytical, but at least to me they have a very analytical flavor anyway, and was the first thing to come into my mind when I read your question. I think you would find it interesting.

Answer 9

I'm not sure how kosher it is for me to answer my question, but since there had been several comments about my original post I did not want to make any major edits to it. I've posed this question to my probability professor and he mentioned his favorite, from the paper "Triple points: from non-Brownian filtrations to harmonic measures." by Tsirelson. It's pretty far over my head, but it claims to have a probabilistic proof of (I'm quoting the description)

A conjecture by C. Bishop (1991) about harmonic measures for three arbitrary (not just regular) non-intersecting domains in Rn. Roughly speaking, trilateral contact is always rare harmonically (though not topologically).

This seems like it goes hand in hand with some of the above comments, where basically knowledge of things like hitting probabilities of brownian motion and similar things for other processes can assist in understanding the fine properties of various domains, useful to people in PDE and harmonic analysis.

Answer 10

Davie's construction of subspaces of $c_0$ and $\ell_p$ ($p\in (2, \infty)$) without the approximation property, as outlined in Section 2.d of Lindenstrauss and Tzafriri's book Classical Banach Spaces I, uses a probabilistic lemma (Lemma 2.d.4, p.87-88). I do not know Davie's proof all that intimately, having been through it only once - courtesy of a fellow grad student who took a couple of hours to go over it in a research group seminar... I remember that it looked like magic at the time.

(Edited once for a typo)

Answer 11

Doeblin's proof of the fundamental limit theorem for regular Markov chains: (450 p. in Introduction to probability, available online.) The proof uses coupling.

Answer 12

Since probability theory is usefully formalized as a special case of quantum probability, a related question is what examples are there of quantum proofs for classical (non-quantum) results. There are now sufficiently many examples to merit a survey by Drucker and deWolf “Quantum Proofs for Classical Theorems.” I blogged about two such examples on FXPAL's blog.