96
$\begingroup$

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.

$\endgroup$
10
  • 4
    $\begingroup$ One example that comes to mind is the relationship between Brownian motion and harmonic functions. Is that the kind of thing you're thinking of? $\endgroup$ Dec 18, 2009 at 1:08
  • 6
    $\begingroup$ The book The Probabilistic Method, by Alon and Spencer, includes probability-inspired proofs of results that don't belong to probability in sections called "The Probabilistic Lens", which are inserted between the various chapters. I don't have my copy at hand right now, and the only analytic one I remember being there is Bernstein's proof of the Weierstrass approximation theorem, which Harald Hanche-Olsen has already mentioned. $\endgroup$ Dec 18, 2009 at 1:53
  • 5
    $\begingroup$ I don't mean to be overly critical (really!), but isn't it immediate from the definition that a Lipshitz function is absolutely continuous? It's just a replay of the argument that a linear function with slope M is continuous: take delta = epsilon/M. I think HHO's example below is so good that it should be the exemplar of the question, perhaps. $\endgroup$ Dec 18, 2009 at 2:51
  • 5
    $\begingroup$ @Yemon: Absolute continuity does not mention differentiability. It turns out, but is comparatively much deeper, that an AC function is differentiable almost everywhere. I still think that Lipschitz implies AC is done just by taking delta = epsilon/(Lipschitz constant). $\endgroup$ Dec 18, 2009 at 7:33
  • 4
    $\begingroup$ Shouldn't this be community wiki? $\endgroup$ Dec 27, 2009 at 0:40

28 Answers 28

111
$\begingroup$

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)^{n-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).

$\endgroup$
2
  • 9
    $\begingroup$ This is freaking amazing!! $\endgroup$
    – Pietro
    May 2, 2010 at 20:06
  • 1
    $\begingroup$ It is also reported in Sinai book Probability Theory - an Introductory Course, also available online $\endgroup$ Jun 14, 2019 at 21:15
41
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Nice! One needs to rescale by a factor $\sqrt{\frac{n}{k}}$ after applying the projection. $\endgroup$
    – Mizar
    Aug 9, 2015 at 17:25
25
$\begingroup$

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

$\endgroup$
21
$\begingroup$

1) perimeter of planar sets with constant width

I like the probabilistic proof that every set of constant width 1 has perimeter pi using Buffon's needle problem. See also the wikipedia article on Buffon's noodle problem.

Another beautiful analytic (of a sort) theorem where probability plays an important role is regarding the overhang problem. The description of the problem and the solution is taken from the abstract of the paper "Maximum overhang" by Mike Paterson, Yuval Peres, Mikkel Thorup, Peter Winkler and Uri Zwick:

2) Maximum overhang

How far can a stack of $n$ identical blocks be made to hang over the edge of a table? The question dates back to at least the middle of the 19th century and the answer to it was widely believed to be of order $\log n$. Recently, Paterson and Zwick constructed $n$-block stacks with overhangs of order $n^{1/3}$, exponentially better than previously thought possible. We show here that order $n^{1/3}$ is indeed best possible, resolving the long-standing overhang problem up to a constant factor.

$\endgroup$
20
$\begingroup$

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.)

$\endgroup$
0
16
$\begingroup$

I believe that Krylov and Safonov's original proof of the Harnack inequality for solutions of elliptic equations in nondivergence form was a probabilistic one. PDE people wouldn't have the slightest idea just from glancing at the title of their paper that this is what they proved (or at least this PDE person). This was not an isolated incident. Much of Krylov's pioneering work in elliptic equations was originally written up in the language of Markov processes, etc, with analytic proofs appearing later.

$\endgroup$
15
$\begingroup$

Here's something that's pretty neat: find a measurable subset $A$ of $[0,1]$ such that for any subinterval $I$ of $[0,1]$, the Lebesgue measure $\mu(A\cap I)$ has $0 < \mu(A\cap I) < \mu(I)$. There's an explicit construction of such a set in Rudin, who describes such sets as "well-distributed". Balint Virag (and maybe others) found a very slick probabilistic construction.

Let $X_1, X_2, \ldots$ be i.i.d. coin flips, i.e. $X_1$ is $1$ with probability $1/2$ and $-1$ with probability $1/2$. Consider the (random) series

$$S:=\sum_{n=1}^\infty X_n/n.\,\,\,$$

By the Kolmogorov three-series theorem, it converges almost surely. However, it's a simple exercise to see that for any $a$, the event $\{S > a\}$ has non-trivial measure: for $a>0$, there's a positive chance of the first $e^a$ terms of the series being positive, so the $e^a$-th partial sum is positive, and the tail is independent and positive or negative with equal probability, due to symmetry. For $a\leq 0$, it's trivial, again because of symmetry.

A common way of realizing i.i.d. coin flips on the unit interval is as Rademacher functions: for $x\in[0,1]$, let ${b_n}$ be its binary expansion, and $X_n(x) = (-1)^{b_n}$. Realized this way, the random sum $S$ becomes an almost everywhere finite measurable function from $[0,1]$ to $\mathbb R$. It only takes a bit more work to see that the set $\{S>a\}$ is exactly a well-distributed set.

Alex Bloemendal has written this up in a short note, but I'm not sure if he's published it anywhere.

$\endgroup$
1
  • $\begingroup$ You shouldn't use $x$ for both the variable in $[0,1]$ and the number that you want $S$ greater than. $\endgroup$ Feb 7, 2012 at 20:47
13
$\begingroup$

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.)

$\endgroup$
4
  • 1
    $\begingroup$ This is obviously a very old answer, but I see that you're still active on MO. Would you happen to have a reference for the probabilistic proof of Atiyah-Singer that you mention? Is it substantially different from the usual heat kernel approach? $\endgroup$ Feb 7, 2012 at 19:44
  • 1
    $\begingroup$ amazon.com/Stochastic-Analysis-Manifolds-Graduate-Mathematics/… $\endgroup$ Feb 8, 2012 at 0:02
  • $\begingroup$ @SteveHuntsman Could you please comment more on 'There are probabilistic proofs ....... anything else that can be done with a heat kernel' and please provide some references ('any other non-trivial examples other than index theorem')? $\endgroup$
    – Turbo
    Dec 31, 2015 at 8:46
  • $\begingroup$ @Turbo - Treat the heat kernel as a transition density as in section 4.1 of the book mentioned in my comment above $\endgroup$ Dec 31, 2015 at 13:16
12
$\begingroup$

There are a number of probabilistic inequalities that are quite frequently used in harmonic analysis. For example, Khintchine's inequality (http://en.wikipedia.org/wiki/Khintchine_inequality).

The same idea of using random signs and taking expectations is rather common. One specific inequality proved in this manner which I've come across comes is the Rademacher-Menshov Theorem (for almost orthogonal functions). The theorem gives a way to control the $L^2$ norm of partial sums of a sequence of N "almost orthogonal" functions by the sum of the $L^2$ norms of each function modulo a logarithmic loss in N. A precise statement and proof of this inequality can be found on page 43 of this article by Ciprian Demeter, Terence Tao, and Christoph Thiele: http://arxiv.org/abs/math/0510581.

$\endgroup$
11
$\begingroup$

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

$\endgroup$
10
$\begingroup$

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.

$\endgroup$
8
$\begingroup$

One of the basic constructions in the theory of singular integral operators is the Calderón-Zygmund decomposition, which follows from a simple stopping time argument. This result has numerous important applications in harmonic analysis; for instance, it plays a role in proving the $L^p$-convergence of Fourier series ($1 < p < \infty$).

$\endgroup$
7
$\begingroup$

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.

$\endgroup$
7
$\begingroup$

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)

$\endgroup$
6
$\begingroup$

How about the Convolution Theorem, which can be seen as a consequence of $$ {\rm E}[e^{iu(X+Y)}]={\rm E}[e^{iuX}]{\rm E}[e^{iuY}],\;\; u \in \mathbb{R}, $$ where $X$ and $Y$ are independent random variables.

$\endgroup$
6
$\begingroup$

An outstanding result of this sort is the theorem of Tsirelson,

MR1487755 Tsirelson, B. Triple points: from non-Brownian filtrations to harmonic measures. Geom. Funct. Anal. 7 (1997), no. 6, 1096–1142.

He proved the following theorem conjectured by M. Sodin and myself:

Let $D_j,1\leq j\leq 3$ be three disjoint regions in $R^n$. Choose points $x_j\in D_j$, and consider harmonic measures $\mu_j=\omega(D_j,x_j)$. We consider them as Borel probability measures in $R^n$ sitting on the boundaries $\partial D_j$. Then there exist Borel sets $E_j\subset\partial D_j$, such that $\mu_j(E_j)=1$, and $E_1\cap E_2\cap E_3=\emptyset$.

The very difficult proof is based on advanced probability theory. When $n=2$ there is a relatively simple analytic proof. It is also not hard to obtain such result with $3$ replaced by $12$, where $12$ does not depend on dimension:-) Tsirelson writes:

"This is a challenge: can the result be achieved by non-stochastic arguments?"

As far as I know, nobody has done this. Usually the results of potential theory which are proved using probability, can e also proved without probability, in most cases with simpler proofs. This result is a remarkable exception.

$\endgroup$
5
$\begingroup$

Some examples can be found in the book "Statistical independence in probability, analysis and number theory" by Mark Kac.

$\endgroup$
5
$\begingroup$

I really like the probabilistic proof of the fact that $$ e^{-n}\sum_{k=0}^n\frac{n^{k}}{k!}\to\frac12 $$ as $n\to\infty$.

The proof goes as follows (taken from here). Suppose that $X_1,\ldots,X_n$ are independent and identically distributed Poisson random variables with the parameter $\lambda=1$. We have that $$ P(X_1+\ldots+X_n\le n)=e^{-n}\sum_{k=0}^n\frac{n^{k}}{k!} $$ and $$ P(X_1+\ldots+X_n\le n)=P(n^{-1/2}(X_1+\ldots+X_n-n)\le 0) $$ for each $n\ge1$. By the central limit theorem, $$ P(n^{-1/2}(X_1+\ldots+X_n-n)\le 0)\to\Phi(0)=1/2 $$ as $n\to\infty$, where $\Phi$ is the cumulative distribution function of the standard normal random variable.

$\endgroup$
1
  • $\begingroup$ One of my favorite exercises to give or demonstrate for students taking an early course in probability (i.e. not their first but not measure theory based). $\endgroup$
    – Pierre
    Sep 2, 2016 at 15:30
4
$\begingroup$

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

$\endgroup$
2
  • 2
    $\begingroup$ How is this an analytic fact? $\endgroup$ Feb 8, 2012 at 1:23
  • $\begingroup$ @MarcinKotowski Well, there is a limit. $\endgroup$
    – Elle Najt
    Apr 27, 2017 at 4:20
4
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ None of the results in the (excellent) paper you reference are ven remotely analytic. $\endgroup$ Feb 8, 2012 at 1:23
2
$\begingroup$

A concrete example of using conformal invariance of Brownian motion in the plane (alluded to in Yemon Choi's answer) is the following:

Consider a simply connected domain in the plane which contains the unit disk and whose boundary is a smooth curve which contains an arc of length $2\pi(1-\epsilon)$ in the unit circle. Then the Riemann map sending this domain to the unit disk and fixing the center of the disk sends the rest of the boundary curve to an arc of length at most $2\pi\epsilon$.

I find this pretty amazing considering there is no bound on the length of the remaining boundary (e.g. you can draw an elephant compared to which the unit disk is a tiny golf ball).

The proof is that the distribution of the first time Brownian motion starting at the center hits the boundary must be sent to the uniform distribution on the circle by the Riemann mapping. I'm not sure what a non-probabilistic proof looks like (probably cross-cuts plus domain-monoticity of some sort I guess) but I doubt it competes in elegance (though we all have our own taste of course).

$\endgroup$
1
$\begingroup$

Doeblin's proof of the fundamental limit theorem for regular Markov chains: (450 p. in Introduction to probability, available online.) The proof uses [coupling](http://en.wikipedia.org/wiki/Coupling_(probability)).

$\endgroup$
1
  • $\begingroup$ I realize this isn't an analytic fact $\endgroup$
    – Yoo
    Dec 24, 2009 at 5:37
1
$\begingroup$

In operator theory there is a result of C.Brislawn here where he uses Doob's Martingales in order to derive a criterion for integral operators to be nuclear. Also using that he gives a trace formula which is similar to the usual trace formula,but applied to a version of operator's kernel.

$\endgroup$
1
$\begingroup$

Dudley's VC-dimension-based upper bound on the packing numbers of function classes used a very clever (and simple!) sampling argument; see Theorem 29.3 in http://link.springer.com/book/10.1007%2F978-1-4612-0711-5 or these notes: https://www.cs.bgu.ac.il/~asml162/wiki.files/dudley-pollard.pdf

$\endgroup$
1
$\begingroup$

Chebyshev's sum inequality can be proven more concisely using probability. Indeed, if $f$ and $g$ are two monotone functions and $X$ a random variable, then we have $$ (f(X_1)-f(X_2))(g(X_1)-g(X_2)) \ge 0 $$ where $X_1, X_2$ are i.i.d. copies of $X$. Then taking expectation gives us the Chebyshev's sum inequality.

$\endgroup$
1
$\begingroup$

In case people are still reading answers to this post, let me add another example to the list. T. Korner used a probabilistic method to solve a problem of Littlewood asking for a complex univariate polynomial of degree $n$ with unimodular coefficients whose restriction to the unit circle (in the complex plane) has modulus uniformly bounded above and below by order $\sqrt{n}$. The probabilistic step consists of randomly modifying a previous example of Byrnes that "almost solves" the problem and then showing that the modification solves the problem with positive probability (utilizing a basic large deviation estimate for sums of i.i.d. random variables). Something interesting to note about the technique is that, in comparison with a lot of other indirect probabilistic proofs in analysis, it has a flavor reminiscent of some aspects of the Probabilistic Method or "Probabilistic Lens" as used in combinatorics. While the result itself has been improved (for instance, showing the existence of such polynomials satisfying a more stringent constraint of having +/-1 coefficients) and perhaps made obsolete, I still find the proof elegant and worth reading.

$\endgroup$
0
$\begingroup$

I stumbled across an elementary and probabilistic proof of Euler's formula $\prod_{p\in\mathbb{P}}\frac{1}{1-p^{-s}}=\sum_{n=1}^{\infty}\frac{1}{n^s} $ for the zeta-function. One reference is here: https://math.stackexchange.com/questions/427910/a-simple-way-to-obtain-prod-p-in-mathbbp-frac11-p-s-sum-n-1-in.

$\endgroup$
0
$\begingroup$

Let $Y_0,Y_1,\ldots,Y_n$ (starting with index $0$) be i.i.d. and uniformly distributed in $(0,1).$

Let $X_1,\ldots,X_n$ (starting with index $1$) be defined by $X_k = \begin{cases} 1 & \text{if } Y_k<Y_0, \\ 0 & \text{otherwise}. \end{cases}$

Then $\Pr(X_1+\cdots+X_n = m \mid Y_0) = \dbinom n m Y_0^m(1-Y_0)^{n-m}. $

Therefore \begin{align} \Pr(X_1+\cdots+X_n=m) & = \operatorname E\left( \binom n m Y_0^n (1-Y_0)^{n-m} \right) \\[8pt] & = \binom n m \int_0^1 y^n (1-y)^{n-m}\, dy. \tag 1 \end{align}

But \begin{align} & \Pr(X_1+\cdots + X_n=m) \\[8pt] = {} & \Pr\left( \begin{array}{c} \text{When $Y_0,\ldots, Y_n$ are sorted into} \\ \text{increasing order, the one in the} \\ \text{$(k+1)$th position is $Y_0.$} \end{array} \right) = \frac 1{n+1}. \end{align} Thus we have the value of the integral in line $(1)$ above.

This argument is essentially due to the Reverend Thomas Bayes, who died in 1761.${}{}$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.