List of probabilistic proofs of non-probabilistic theorems

From Wikipedia, the free encyclopedia

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 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, 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

  • 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

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

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

See also

Notes

Loading related searches...

Wikiwand - on

Seamless Wikipedia browsing. On steroids.