show/hide this revision's text 2 deleted 1 characters in body

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 be 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.)

show/hide this revision's text 1

A trick or a general technique? (Probabilistic Method)

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 be even give 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.)