List of probabilistic proofs of non-probabilistic theorems

Probability theory routinely uses results from other fields of mathematics (mostly, analysis). The opposite cases, collected below, are relatively rare; however, probability theory is used systematically in combinatorics via the probabilistic method. They are particularly used for non-constructive proofs.

Analysis

• Normal numbers exist. Moreover, computable normal numbers exist. These non-probabilistic existence theorems follow from probabilistic results: (a) a number chosen at random (uniformly on (0,1)) is normal almost surely (which follows easily from the strong law of large numbers); (b) some probabilistic inequalities behind the strong law. The existence of a normal number follows from (a) immediately. The proof of the existence of computable normal numbers, based on (b), involves additional arguments. All known proofs use probabilistic arguments.
• Dvoretzky's theorem which states that high-dimensional convex bodies have ball-like slices is proved probabilistically. No deterministic construction is known, even for many specific bodies.
• The diameter of the Banach–Mazur compactum was calculated using a probabilistic construction. No deterministic construction is known.
• The original proof that the Hausdorff–Young inequality cannot be extended to ${\displaystyle p>2}$ is probabilistic. The proof of the de Leeuw–Kahane–Katznelson theorem (which is a stronger claim) is partially probabilistic.^[1]
• The first construction of a Salem set was probabilistic.^[2] Only in 1981 did Kaufman give a deterministic construction.^[3]
• Every continuous function on a compact interval can be uniformly approximated by polynomials, which is the Weierstrass approximation theorem. A probabilistic proof uses the weak law of large numbers. Non-probabilistic proofs were available earlier.
• Existence of a nowhere differentiable continuous function follows easily from properties of Wiener process. A non-probabilistic proof was available earlier.
• Stirling's formula was first discovered by Abraham de Moivre in his `The Doctrine of Chances' (with a constant identified later by Stirling) in order to be used in probability theory. Several probabilistic proofs of Stirling's formula (and related results) were found in the 20th century.^[4][5]

• The only bounded harmonic functions defined on the whole plane are constant functions by Liouville's theorem. A probabilistic proof via n-dimensional Brownian motion is well known.^[6] Non-probabilistic proofs were available earlier.
• Non-tangential boundary values^[7] of an analytic or harmonic function exist at almost all boundary points of non-tangential boundedness. This result (Privalov's theorem), and several results of this kind, are deduced from martingale convergence.^[8] Non-probabilistic proofs were available earlier.
• The boundary Harnack principle is proved using Brownian motion^[9] (see also^[10]). Non-probabilistic proofs were available earlier.
• Euler's Basel sum, ${\displaystyle \qquad \sum _{n=1}^{\infty }{\frac {1}{n^{2}}}={\frac {\pi ^{2}}{6}},}$ can be demonstrated by considering the expected exit time of planar Brownian motion from an infinite strip. A number of other less well-known identities can be deduced in a similar manner.^[11]

• The Picard theorem can be proved using the winding properties of planar Brownian motion.^[12][13]
• The fact that every Lipschitz function on the real line is differentiable almost everywhere can be proved using martingale convergence.
• Multidimensional Fourier inversion formula can be established by the weak law of large numbers and some elementary results from complex analysis.^[14]
• Abért and Weiss proved, via a probabilistic construction, that Bernoulli shifts are weakly contained (in the sense of Kechris) in any free measure-preserving action action of a discrete, countable group on a standard probability space.^[15]

Combinatorics

• A number of theorems stating existence of graphs (and other discrete structures) with desired properties are proved by the probabilistic method. Non-probabilistic proofs are available for a few of them.
• The maximum-minimums identity admits a probabilistic proof.
• Crossing number inequality which is a lower bound on the number of crossing for any drawing of a graph as a function of the number of vertices, edges the graph has.

Algebra

• The fundamental theorem of algebra can be proved using two-dimensional Brownian motion.^[6] Non-probabilistic proofs were available earlier.
• The index theorem for elliptic complexes is proved using probabilistic methods^[16] (rather than heat equation methods). A non-probabilistic proof was available earlier.

Topology and geometry

• A smooth boundary is evidently two-sided, but a non-smooth (especially, fractal) boundary can be quite complicated. It was conjectured to be two-sided in the sense that the natural projection of the Martin boundary^[17] to the topological boundary is at most 2 to 1 almost everywhere.^[18] This conjecture is proved using Brownian motion, local time, stochastic integration, coupling, hypercontractivity etc.^[19] (see also^[20]). A non-probabilistic proof is found 18 years later.^[21]
• The Loewner's torus inequality relates the area of a compact surface (topologically, a torus) to its systole. It can be proved most easily by using the probabilistic notion of variance.^[22] A non-probabilistic proof was available earlier.
• The weak halfspace theorem for minimal surfaces states that any complete minimal surface of bounded curvature which is not a plane is not contained in any halfspace. This theorem is proved using a coupling between Brownian motions on minimal surfaces.^[23] A non-probabilistic proof was available earlier.

Number theory

• The normal number theorem (1909), due to Émile Borel, could be one of the first examples of the probabilistic method, providing the first proof of existence of normal numbers, with the help of the first version of the strong law of large numbers (see also the first item of the section Analysis).
• The Rogers–Ramanujan identities are proved using Markov chains.^[24] A non-probabilistic proof was available earlier.

Quantum theory

• Non-commutative dynamics (called also quantum dynamics) is formulated in terms of Von Neumann algebras and continuous tensor products of Hilbert spaces.^[25] Several results (for example, a continuum of mutually non-isomorphic models) are obtained by probabilistic means (random compact sets and Brownian motion).^[26][27] One part of this theory (so-called type III systems) is translated into the analytic language^[28] and is developing analytically;^[29] the other part (so-called type II systems) exists still in the probabilistic language only.
• Tripartite quantum states can lead to arbitrary large violations of Bell inequalities^[30] (in sharp contrast to the bipartite case). The proof uses random unitary matrices. No other proof is available.

Information theory

• The proof of Shannon's channel coding theorem uses random coding to show the existence of a code that achieves channel capacity.

See also

• Probabilistic method

Notes

External links

• Probabilistic Proofs of Analytic Facts at MathOverflow

This page was last edited on 9 February 2024, at 17:43