Proving something exists nonconstructively using probability.

yay! i like seeing math posts on HN, even though the prob method usually leaves you feeling less than satisfied. the proofs, at least the ones i've seen, don't usually elicit that AHA moment. but that's just me. i think i still have the copy of the Spencer book i checked out of the library years ago.

Title seems a little misleading, in that some constructive proof techniques are used to set-up the probabilistic tools.

The best description I was ever given of the probabilistic method: "It's not like we're searching for a needle in a haystack here. We're searching for hay in a haystack... But every time we reach in, we find a needle" - Laszlo Babai This was said of the Ramsey number (Example 1) which is very hard to construct examples of (AFAIK there isn't an algorithm to do it), even though a randomly generated graph will be an example with probability tending toward 1.

The Princeton Companion to Mathematics has a good description of this starting on page 572.

Basically the proof goes like this: Define a random variable that can only take on integer values. Show that the expected value is less than one. The random variable must therefore sometimes take on the value of zero.

If your random variable was defined to mean something interesting at zero, then the above is an existence proof. What they mean by "non-constructive" is that you still don't actually have an example of the thing existing -- you just know it does. Very cool.