A trick or a general technique? (Probabilistic Method) - MathOverflow

A trick or a general technique? (Probabilistic Method)

2012-01-15T11:48:30Z

Suppose we have some positive quantites $P$ and $Q$ which depend on some choices that we make, and we want to show that some choice makes the quotient $P/Q$ fall below some cool bound.

One idea is to make our choices randomly in some way and show that $P/Q$ is small on average. That is, we can use the trivial bound $$ \min P/Q \leq \mathbf{E}[P/Q]. $$ But this inequality is unlikely to be of much use, because we still have to compute $P/Q$ for a random choice. A much more useful inequality arises as follows. Observe that $$ \mathbf{E}[P - Q\mathbf{E}[P]/\mathbf{E}[Q]] = 0, $$ whence $$ \min P/Q \leq \mathbf{E}[P]/\mathbf{E}[Q]. $$ This inequality is much more likely to be useful because now we can compute expectations first and then take the quotient. Moreover, in some cases this will even give a better bound than the other inequality.

I'm not looking so much for a detailed explanation of what's going on in this specific inequality, but rather for general intuition. Is this just a trick? How can other tricks like this be anticipated?

(Setting: In proving the discrete Cheeger inequality, $P$ is the number of edges coming out of a subset of a graph and $Q$ is the minimum of the size of the subset and the size of its complement, but this question is about general technique and not this specific problem.)

Answer by Ori Gurel-Gurevich for A trick or a general technique? (Probabilistic Method)

2012-01-15T17:12:17Z

EDIT: short false answer deleted. I believe something can be salvaged here, but it is too late for me now.

Answer by cardinal for A trick or a general technique? (Probabilistic Method)

2012-01-17T00:55:32Z

Perhaps you're looking for something deeper, but does this not simply follow by monotonicity of the integral and the (almost sure) positivity of $Q$?

Namely, $$ \mathbb E P = \mathbb E \frac{P}{Q} Q \geq \bigg(\min \frac{P}{Q}\bigg) \mathbb E Q. $$

Note that we can let $P$ be completely arbitrary (e.g., taking on nonpositive values) and replace $\min$ by $\inf$ and everything still goes through as long as the expectations exist and are finite.

Answer by Thierry Zell for A trick or a general technique? (Probabilistic Method)

2012-01-17T01:22:27Z

Well, this is going to sound a bit silly, but your main tool, the fact that $$E[P−QE[P]/E[Q]]=0,$$ follows trivially from the linearity of expectation, and to me, the linearity is where the magic happens.

The linearity of expectation may not sound like a big deal, it's a fairly easy fact in probability theory, but I'm always surprised by its non-obvious consequences for combinatorics in general and the probabilistic method in particular. My favorite application of linearity is that the expectation of the number $X$ of fixed points for a permutation of $n$ elements taken uniformly at random is exactly 1. It's a one-line proof using linearity versus highly non-trivial derangement juggling if you just write it out explicitly: $$ E[X]=\sum_{k=0}^n k\binom{n}{k} d_{n-k} \frac{1}{n!};$$ where $d_{n-k}$ is the number of derangements on $n-k$ elements, computed using the inclusion-exclusion formula. (BTW, it is possible to show that this formula yields~1, it's just not all that easy.)

Answer by Will Sawin for A trick or a general technique? (Probabilistic Method)

2012-01-17T02:33:01Z

One way to see this technique is as a way of dealing with certain bad cases. $E[P/Q]$ can be unhelpfully dragged up by the inclusion of certain cases where $Q$ is small and $P$ is medium. $E[P]/E[Q]$ is not nearly so distorted. In particular, take $Q=0$, $P>0$. The first inequality becomes totally unhelpful, as $E[P/Q]=\infty$. But $E[P]$ and $E[Q]$ are still finite.

Any time a naive probabilistic bound is poor due to some very very bad cases, you should look for a trick to exclude these cases or dull their impact on the bound. In particular, you should try to change the probability measure, reducing it on those cases.

Here, since we want to avoid small $Q$, we multiply the probability measure by $Q/E[Q]$. It will still be a probability measure after this, and the new expectation will be:

$E'[P/Q]=E[PQ/QE[Q]]=E[P/E[Q]]=E[P]/E[Q]$