# Erdős Probabilistic method

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.

• As Brian has said, your second question is just a simplification to use a simple slightly larger number as upper bound. For your first question, you should expand it more. Writing a long text and then asking "What I am unclear is about the reference to the expected number?" leaves us guessing what exactly your question is. – Phira May 22 '12 at 10:47
• I was not clear as to why expected number is being used. The way I was using the probabilistic method was taking $P(\cup A_i)\le\sum P(A_i)\le g(n,k)<1$ (g(n,k) is some upper bound for $\sum P(A_i)$ and then using this to obtain $N< f(k)$ for some function $f(k)$ which would then be a lower bound. I hadn't heard of this other approach until today, and wasn't aware of the argument which makes it work (1st moment method) and it seems to me of no additional ease. – Shahab May 22 '12 at 14:10

(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.

• I don't think the OP got off track. It's true that this is not only the expected number of occurrences but also an upper bound on the probability of at least one occurrence. I understood the question to be why we take the detour via the expected number and then apply the first moment method to get back to probabilities instead of arguing directly that the probability of the union of the events is $\le$ the sum of the individual probabilities. That seems like a good question that neither your answer nor Didier's addresses. – joriki May 22 '12 at 7:54
• @joriki: That interpretation of the question never even occurred to me; the wording seemed to me to indicate lack of understanding of what was being done rather than lack of understanding of why that particular line of argument was chosen. (Judging by the little that I’ve read in the area, the answer to that question might just be because it’s a standard form of argument in this field!) – Brian M. Scott May 22 '12 at 8:05
• You're right about the wording of the question; I should have said something more like "the question makes sense if you interpret it in light of the fact that the OP's approach is correct and more direct than the one in the paper". About the standard form of argument: I was trying to come up with a more complex example where that form of the argument works and a direct bound on probabilities doesn't, but I couldn't. This Wikipedia example can also be reformulated in terms of a simple probability bound. – joriki May 22 '12 at 8:15
• @joriki: Now you have me wondering whether it is largely a matter of style and habit. – Brian M. Scott May 22 '12 at 8:25
• The second example in the Wikipedia article uses Markov's inequality for a value other than $1$; this would be more complicated to reformulate directly in terms of probabilities. So perhaps the argument using the expected value has become standard because it's more widely applicable and the unnecessary slight complication for the simple cases isn't a problem. – joriki May 23 '12 at 7:06

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.

• Please see my comment under Brian's answer. – joriki May 22 '12 at 7:55
• @joriki Thanks for your input. You might be right. Since (I find that) the wording of the question is rather ambiguous, I feel like waiting for some more explanations from the OP. – Did May 22 '12 at 7:58

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