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 ${X}$ be a nonnegative random variable on a probability space ${\Omega}$. A basic observation is that:

$\displaystyle \mathbb{P}(X \geq \mathbb{E}( X)) > 0.$

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 ${K_N}$, and let ${X}$ be the random variable which outputs the number of monochromatic ${k}$-cliques, and ${Y = N - X}$. We note that if we remove one vertex from ${K_N}$ from each monochromatic edge, we get a 2-colored complete graph with ${Y}$ vertices and no ${k}$-cliques. (more…)