Unexpected yet accessible examples of the probabilistic method

Question

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.

Answer 1

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.

Answer 2

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).