3 ms·
Proving something exists nonconstructively using probability.
- pz 17y agoyay! 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.
- stcredzero 17y agoPerhaps there are alien minds constructed out there whose organizing principle for their version of rational thought involves optimizing Bayesian belief networks, and when they look at these, the deductive reasoning part is unsatisfying, but the probabilistic part gives them the Ah-Ha!
- edmccaffrey 17y agoWhat's the probability of that being true?
- stcredzero 17y agoAH-HA!
- stcredzero 17y agoTitle seems a little misleading, in that some constructive proof techniques are used to set-up the probabilistic tools.
- mgreenbe 17y agoThat's not how constructivity works, though --- it's all or nothing. You can be careful about the points at which you use classical reasoning (or, here, probability), but then the whole proof is no longer constructive. The argument in favor of the constructive approach is that you can very carefully decide when you depart from it. For a (Curry-Howard) corresponding intuition, a program is no longer functional the moment any computational effect is involved (mutable state, control effects like continuations and backtracking, etc.).
- thras 17y agoThe 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.
- jdoliner 17y agoThe 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.