Probabilistic Method

The Probabilistic Method

Introduction

(Adapted from Canada Training Materials) Sometimes, in Olympiad you might be ask to show that there exists an object with a specific property. If you're lucky, you might define an adequate object. However, this is usually hard and out of the question. This is where the probabilistic method comes in.

The Method

There are two types :

1. Choose an object at random.

The basic method: Choose an object uniformly at random. This means that each object is equally likely to be picked.

Variations: You do not have to choose an object uniformly at random. You just need to describe a way of picking an object that has some randomness involved. As you will see, there are sometimes other effective ways of doing this.

1. Prove that you will choose an object with the desired property with probability $p > 0$.

Often you will be looking for an object where some numeric quantity $X$ with value at least or at most $y$. If you can show that the expected value of $X$ is $y$, then there exists some case where $X \ge y$ and $X \le y$.

Applications

We start with a simple problem.

There are $n$ students and $m$ pair of these are enemies. Prove that one can divide the students into $k$ rooms so that there are at most $\frac{m}{k}$ pairs of enemies that are placed in the same room as each other.

Independently place each student in a random room. Now consider a fixed pair of enemies.

The probability that they will be placed in the same room is exactly $\frac{1}{k}$. Therefore, on average, the number of pairs of enemies placed in the same room is also $\frac{m}{k}$. In particular, there exists a configuration satisfying the problem statement.

Now, we look at a beautiful, but tougher result by Erdos in 1965.

(Erdos, 1965) A set $S$ is called sum-free if there is no triple of (not neccesary distinct) elements $x, y, z \in S$ satisfying $x + y = z$. Prove that every set $A$ of non-zero integers contain a subset $S \subseteq A$, with cardinality larger than $\frac{|A|}{3}$, which is sum-free.

Let $p$ be a prime number of the form $3k + 2$ such that $p$ is greater than the maximum absolute value of any element in $A$. (By Dirichlet's Theorem) Also let $C = \{k + 1, k + 2, . . . , 2k + 1\}$, and note that this set is sum-free modulo $p$. Pick $r$ uniformly at random from $\{1, 2, . . . , p ? 1\}$, and consider multiplying each element of $A$ by $r$, modulo $p$.

Since $p$ is large, every element in $A$ is non-zero modulo $p$. Therefore, each element in $A$ has probability exactly $\frac{|C|}{p - 1} \ge \frac{1}{3}$ of mapping into $C$ when multiplied by $r$. Linearity of expectation then implies that the expected number of elements mapping into $C$ is $> \frac{|A|}{3}$. Let $S$ be the set of these elements. We know there exists some choice of $r$ for which $|S| \ge E[|S|] > \frac{|A|}{3}$. It remains only to show that $S$ is sum-free. Indeed, if $x, y, z \in S$, then $xr + yr \not\equiv zr \pmod{p}$ since $xr, yr, zr \in C$, therefore $x + y \neq z$.

Conclusion : Probabilistic Method is a very powerful technique.

The canada training material can be found here. Click on Probabilistic Method to open the file.