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 $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 an 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 two-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, $\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 Lipchitz function on the real line is differentiable almost everywhere can be proved using martingale convergence.

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.

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^[14] (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^[15] to the topological boundary is at most 2 to 1 almost everywhere.^[16] This conjecture is proved using Brownian motion, local time, stochastic integration, coupling, hypercontractivity etc.^[17] (see also^[18]). Known non-probabilistic approaches give weaker results:^[16] at most 10 sides in four (and more) dimensions; at most 4 sides in three dimensions; and 2 sides on the plane.
• 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.^[19] 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.^[20] 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.^[21] 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.^[22] Several results (for example, a continuum of mutually non-isomorphic models) are obtained by probabilistic means (random compact sets and Brownian motion).^[23][24] One part of this theory (so-called type III systems) is translated into the analytic language^[25] and is developing analytically;^[26] 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^[27] (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

1. Karel de Leeuw, Yitzhak Katznelson and Jean-Pierre Kahane, Sur les coefficients de Fourier des fonctions continues. (French) C. R. Acad. Sci. Paris Sér. A–B 285:16 (1977), A1001–A1003.
2. Salem, Raphaël (1951). "On singular monotonic functions whose spectrum has a given Hausdorff dimension". Ark. Mat. 1: 353–365. doi:10.1007/bf02591372.
3. Kaufman, Robert (1981). "On the theorem of Jarník and Besicovitch". Acta Arith. 39 (3): 265–267.
4. Blyth, Colin R.; Pathak, Pramod K. (1986), "A note on easy proofs of Stirling's theorem", American Mathematical Monthly, 93 (5): 376–379, doi:10.2307/2323600, JSTOR 2323600.
5. Gordon, Louis (1994), "A stochastic approach to the gamma function", American Mathematical Monthly, 101 (9): 858–865, doi:10.2307/2975134, JSTOR 2975134.
6. Revuz, Daniel; Yor, Marc (1994), Continuous martingales and Brownian motion (2nd ed.), Springer (see Exercise (2.17) in Section V.2, page 187).
7. See Fatou's theorem.
8. Durrett, Richard (1984), Brownian motion and martingales in analysis, California: Wadsworth, ISBN 0-534-03065-3.
9. Bass, R.F.; Burdzy, K. (1989), "A probabilistic proof of the boundary Harnack principle", Seminar on Stochastic Processes, Boston: Birkhäuser (published 1990), pp. 1–16, hdl:1773/2249.
10. Bass, Richard F. (1995), Probabilistic techniques in analysis, Springer, p. 228.
11. Markowsky, Greg T. (2011), "On the expected exit time of planar Brownian motion from simply connected domains", Electronic Communications in Probability, 16: 652–663, doi:10.1214/ecp.v16-1653.
12. Davis, Burgess (1975), "Picard's theorem and Brownian motion", Transactions of the American Mathematical Society, 213: 353–362, doi:10.2307/1998050.
13. Davis, Burgess (1979), "Brownian motion and analytic functions", Annals of Probability, 7: 913–932, doi:10.1214/aop/1176994888.
14. Bismut, Jean-Michel (1984), "The Atiyah–Singer Theorems: A Probabilistic Approach. I. The index theorem", J. Funct. Analysis, 57: 56–99, doi:10.1016/0022-1236(84)90101-0.
15. As long as we have no article on Martin boundary, see Compactification (mathematics)#Other compactification theories.
16. Bishop, C. (1991), "A characterization of Poissonian domains", Arkiv för Matematik, 29 (1): 1–24, doi:10.1007/BF02384328 (see Section 6).
17. Tsirelson, Boris (1997), "Triple points: from non-Brownian filtrations to harmonic measures", Geometric and Functional Analysis, Birkhauser, 7 (6): 1096–1142, doi:10.1007/s000390050038. author's site
18. Tsirelson, Boris (1998), "Within and beyond the reach of Brownian innovation", Proceedings of the international congress of mathematicians, Documenta mathematica, Extra Volume ICM 1998, III, Berlin: der Deutschen Mathematiker-Vereinigung, pp. 311–320, ISSN 1431-0635.
19. Horowitz, Charles; Usadi Katz, Karin; Katz, Mikhail G. (2008). "Loewner's torus inequality with isosystolic defect". Journal of Geometric Analysis. 19 (4): 796–808. arXiv:0803.0690. doi:10.1007/s12220-009-9090-y.
20. Neel, Robert W. (2008), "A martingale approach to minimal surfaces", Journal of Functional Analysis, Elsevier, 256 (8): 2440–2472, doi:10.1016/j.jfa.2008.06.033. Also arXiv:0805.0556.
21. Fulman, Jason (2001), "A probabilistic proof of the Rogers–Ramanujan identities", Bulletin of the London Mathematical Society, 33 (4): 397–407, doi:10.1017/S0024609301008207. Also arXiv:math.CO/0001078.
22. Arveson, William (2003), Noncommutative dynamics and E-semigroups, New York: Springer, ISBN 0-387-00151-4.
23. Tsirelson, Boris (2003), "Non-isomorphic product systems", in Price, Geoffrey, Advances in quantum dynamics, Contemporary mathematics, 335, American mathematical society, pp. 273–328, ISBN 0-8218-3215-8. Also arXiv:math.FA/0210457.
24. Tsirelson, Boris (2008), "On automorphisms of type II Arveson systems (probabilistic approach)", New York Journal of Mathematics, 14: 539–576.
25. Bhat, B.V.Rajarama; Srinivasan, Raman (2005), "On product systems arising from sum systems", Infinite Dimensional Analysis, Quantum Probability and Related Topics (IDAQP), 8 (1): 1–31, doi:10.1142/S0219025705001834. Also arXiv:math.OA/0405276.
26. Izumi, Masaki; Srinivasan, Raman (2008), "Generalized CCR flows", Communications in Mathematical Physics, 281 (2): 529–571, doi:10.1007/s00220-008-0447-z. Also arXiv:0705.3280.
27. Perez-Garcia, D.; Wolf, M.M.; C., Palazuelos; Villanueva, I.; Junge, M. (2008), "Unbounded violation of tripartite Bell inequalities", Communications in Mathematical Physics, Springer, 279 (2): 455–486, doi:10.1007/s00220-008-0418-4

External links

• Probabilistic Proofs of Analytic Facts at MathOverflow