6
$\begingroup$

What are some examples of applications of the probabilistic method to areas where it might not be expected? I was just wondering how feasible it would be to present different ideas about the probabilistic method to those who don't necessarily have a lot of math background.

One really interesting example I found was hat games, and the applications of Hamming codes and probabilities to find really slick ways to think about different hat puzzles. I was just wondering if you had any other specific examples that don't take a lot of build up to get to some interesting results.

I plan to introduce the basics of probability and expected value, but I don't think I can get to topics like the Local Lemma and Martingales. Also, I don't think I'd like to go very deep into graphs or analysis either, given that a lot of people aren't very familiar with those concepts.

$\endgroup$
3
  • $\begingroup$ What exactly do you mean by "the probabilistic method?" A specific algorithm or approach or just using probability theory in general to solve a problem? $\endgroup$
    – Math1000
    Commented Dec 24, 2019 at 1:32
  • 1
    $\begingroup$ For example there is something specifically known as the "probabilistic method": en.wikipedia.org/wiki/Probabilistic_method - is this what you are refering to? $\endgroup$
    – Math1000
    Commented Dec 24, 2019 at 1:33
  • $\begingroup$ Yep, exactly the contents in that link. $\endgroup$
    – Alvin Chen
    Commented Dec 24, 2019 at 2:12

2 Answers 2

11
$\begingroup$

Honestly, I find almost every example of the probabilistic method unexpected. I think that my favourite cute example comes in the following easy-to-state puzzle:

"Prove that any 10 points in the plane can be covered with disjoint open unit discs."

(At first glance, this might seem super obvious, but to see that it isn't true for arbitrarily many points consider like a million points distributed in the unit square, which can't be covered)

The solution by the probabilistic method comes from taking an arbitrary collection of 10 points $x_1, \dotsc, x_{10}$ and dropping a hexagonal lattice of unit discs uniformly at random on the plane (this can be made precise with a little thought).

Letting $A_i$ be the event that $x_i$ is not covered by any of the discs in the lattice, we have that $\mathbf{P}(A_i)$ is the density of "holes" between the discs in the lattice. It is a straightforward geometric exercise to see that the area of each "hole" is $\sqrt{3} - \pi/2$ and so that their density is $$ \frac{\sqrt{3} - \pi/2}{\sqrt{3}} \approx 0.0931. $$

In particular, we have that \begin{align*} \mathbf{P}(\text{All points are covered}) &= \mathbf{P}\Big(\bigcap_{i=1}^{10} A_i^c\Big) \\ &= 1 - \mathbf{P}\Big(\bigcup_{i=1}^{10} A_i\Big) \\ &\geq 1 - 10 \cdot 0.0931 \\ &> 0. \end{align*}

Since this probability is positive, the probabilstic method yields that there must be some orientation of the lattice, and so some collection of disjoint open unit discs that cover all 10 points.

$\endgroup$
3
  • 2
    $\begingroup$ +1. even though you say you find all applications unexpected, I would say this application is very unexpected. $\endgroup$ Commented Dec 31, 2019 at 14:11
  • $\begingroup$ I wonder, does the statement fail for 11 points? If not, what is the smallest example of a set of points which cannot be covered by disjoint unit disks? $\endgroup$
    – Mike Daas
    Commented Jan 6, 2020 at 1:21
  • $\begingroup$ @MikeDaas A 2012 paper (Covering Points with Disjoint Unit Disks by Aloupis, et al) proves the following: "Let k be the size of the smallest point set that is not coverable by disjoint unit disks. Then 13 ≤ k ≤ 45." It also mentions that "it is NP-complete to decide if a given set of n points can be covered. " $\endgroup$
    – r.e.s.
    Commented Aug 22, 2020 at 13:52
-1
$\begingroup$

This application seems to be beyond the scope of your question since it relies on Chebyshev's inequality, some understanding of the binomial distribution and a bit of algebraic manipulation, but I'd like to add it nonetheless since it is still relatively elementary and certainly unexpected - it may be of interest to other users ending up here through a search.

Weierstrass approximation theorem: Given a continuous function $f : [0, 1] \to \mathbb{R}$ and $\epsilon > 0$, we can construct a polynomial $p(x) = a_n x^n + a_{n-1} x^{n-1} + \dots + a_0$ such that for all $x\in[0,1]$ we have $|f(x) - p(x)| < \epsilon$.

A short proof (less than two pages) of this appears in Alon & Spencer's The Probabilistic Method, as one of the 'probabilistic lens'-intermezzos. The original proof is from Bernstein (1912) (written in French).

$\endgroup$
2
  • 1
    $\begingroup$ This is certainly unexpected! Can you give a very brief, hand-wavy description of how this proof goes? I can't even imagine the sample space involved (since $p$ ranges over arbitrary $n \in \mathbb{N}$ and also $\mathbb{R}^{n+1}$ for the coefficients...) $\endgroup$
    – antkam
    Commented Jan 3, 2020 at 4:28
  • 1
    $\begingroup$ I downvoted. I am nearly certain this is not a proof by probabilistic method. The proof I am aware of explicitly constructs the approximating polynomials (with motivation for the explicit construction coming from probability). See Bernstein polynomial. @antkam $\endgroup$ Commented Jan 6, 2020 at 4:40

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .