As I mentioned earlier, I’ve been reading a little about the probabilistic method, especially in combinatorics and related fields, as a result of a course I’m TAing. This material is certainly fundamental to a lot of mathematics and computer science, but I’ve never really studied probability. I’ve been trying to change that. The material in this post is from Alon and Spencer’s *The Probabilistic Method.*

**1. First moments**

For the purposes of the probabilistic method, we often want to show that a certain event is *possible*, which is done by showing that it occurs with positive probability as the outcome of a random process. Let be a nonnegative random variable on a probability space . A basic observation is that:

that is, a random variable takes at least its expectation value with positive probability. This alone is sufficient to obtain many interesting results.

**Example:** Let’s go back to the problem of bounding below the Ramsey numbers. Consider a random 2-coloring of the edges of the graph , and let be the random variable which outputs the number of monochromatic -cliques, and . We note that if we remove one vertex from from each monochromatic edge, we get a 2-colored complete graph with vertices and no -cliques. (more…)