Erdős Probabilistic method

Question

My question is based on the Erdos probabilistic method. I am trying to read from the paper here. The proof of Theorem 1 contains the statement

Since a block sequence is monochromatic with probability $2^{1−k}$, it follows from the linearity of expectation that the expected number of monochromatic k-term quasi-progressions under a random coloring is at most $2N^2(c/2)^k/(k − 1)$.

Essentially as I understand the probablistic argument should run as follows: The probability of a particular event $A$ is $2^{1−k}$. We then conclude that the probability of the occuurence of any such event is bounded above by $2^{1−k}\times$ the number of such possible events. The number of possible events is bounded above as per the previous arguments (according to my understanding) in the paper by $N(N-k+1)c^k/(k − 1)$, and forcing $2N(N-k+1)(c/2)^k/(k − 1)$ to be less then $1$ will give us a bound for $N$ within which if $N$ is chosen the desired event is not guaranteed and hence we have a lower bound.

What I am unclear is about the following:

1. The reference to the expected number ?
2. Why is $2N(N-k+1)(c/2)^k/(k − 1)$ not used instead of $2N^2(c/2)^k/(k − 1)$ ?

If there is some further clarification needed I will be glad to supply it.

Thanks.

Answer 1

(Note that you’ve used both $K$ and $k$ for the paper’s $k$.) You get off track when you say

We then conclude that the probability of the occurrence of any such event is bounded above by $2^{1−k}\times$ the number of such possible events.

That product is actually the expected number of occurrences of the event. At that point he’s shown that if there are at most $c^k$ block sequences corresponding to $k$-term quasi-progressions of diameter $1$ having a particular first term and low difference, then the number of such block sequences is at most $$(N-k+1)\cdot\frac{N}{k-1}\cdot c^k\;.$$ The probability that any one of them is monochromatic is $\dfrac1{2^{k-1}}$, so by linearity of expectation the expected number of monochromatic sequences is at most $$(N-k+1)\cdot\frac{N}{k-1}\cdot c^k\cdot\frac1{2^{k-1}}\le\frac{2N^2}{k-1}\left(\frac{c}2\right)^k\;.$$

To put the matter in everyday terms, if you’re a basketball player and have a probability of $0.8$ of making a free throw, and you take $1000$ free throws, on average you can expect to make about $800$ of them. That’s the kind of reasoning used here, and it’s mathematically justifiable.

The replacement of $(N-k+1)N$ by $N^2$ is just a convenience, useful because $k$ is not specified. Even if $k=1$ this version works.

Answer 2

Re 1., the probability of a particular event times the number of such events equals the expected number of events occurring, if the events are equiprobable. More generally, the expected number of events occurring is the sum of the probabilities of the events.

Re 2., $(N-k+1)N\leqslant N^2$ merely simplifies subsequent computations. If furthermore $k\ll N$, this even captures the main part of the phenomenon.

Answer 3

A simple instance of the probabilistic method:

After some calculation, I find:

The expected value of black spots on my randomly bought apple is 0.2. The expected value of brown spots on my randomly bought apple is 0.295.

I can now conclude that at most 20% of apples have black spots (possibly less, if some apples have more than one). And that at most 30% of apples have brown spots. (Note that I could have said 29.5% but I can replace it by a simpler larger number and the sentence remains true.)

Now, I can conclude that there are apples without black or brown spots (actually at least 50% of apples).

In the typical random graph application the numbers depend on the number of vertices and on either the number of edges or the edge probability.

This means that you make the same calculation, possibly replacing probabilites by simpler larger expressions. And in the end you check that for sufficiently large $N$ (depending on the other parameter), the sum is smaller than 100%.

So, the expected value is used to get a bound in one direction, this is also called the first moment method. To get a bound in the other direction, you can use the variance, see http://en.wikipedia.org/wiki/Second_moment_method