This is closely related to proof by the probabilistic method, which shows up quite often in pattern recognition literature and combinatorics (Erdös was fond of

This is closely related to proof by the probabilistic method, which shows up quite often in pattern recognition literature and combinatorics (Erdös was fond of it). This method says that instead of even proving the exact existence of something (despite missing any examples) you simply prove that the probability of its existence is positive (and thus cannot be zero). At some level these are just proofs that lower-bound the size of the set of instances, and it may be possible to convert any such argument in to one that is more directly measuring the count of instances. In practice however they tend to go through using bounds which are derived from measurable to arguments on random variables, so the conversion is less obvious to me. I wish my copy of DGL wasn't 2 hours away or I'd dig up one. (Edit: Wikipedia to the rescue! The "second example" on this page goes through using Markov's Bound on distributions http://en.wikipedia.org/wiki/Probabilistic_method http://en.wikipedia.org/wiki/Probabilistic_method)