Probabilistic proofs of non-probabilistic theorems

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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[edit]

  • 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]
  • 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.
  • Euler's Basel sum, 
\qquad \sum_{n=1}^\infin \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]

Combinatorics[edit]

  • 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 some of them.

Algebra[edit]

Topology and geometry[edit]

  • 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 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[edit]

Quantum theory[edit]

  • 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[edit]

See also[edit]

Notes[edit]

  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. ^ Raphaël Salem, On singular monotonic functions whose spectrum has a given Hausdorff dimension. Ark. Mat. 1, (1951). 353–365.
  3. ^ Robert Kaufman, On the theorem of Jarník and Besicovitch. Acta Arith. 39:3 (1981), 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. ^ a b 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: 913–932 .
  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. ^ a b 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", GAFA, 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. ^ Charles Horowitz, Karin Usadi Katz and Mikhail G. Katz (2008), Loewner's torus inequality with isosystolic defect, Journal of Geometric Analysis 19 (2009), no. 4, 796-808. See arXiv:0803.0690.
  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[edit]