A trick or a general technique? (Probabilistic Method) - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-19T19:52:38Z http://mathoverflow.net/feeds/question/85730 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/85730/a-trick-or-a-general-technique-probabilistic-method A trick or a general technique? (Probabilistic Method) Sean Eberhard 2012-01-15T11:48:30Z 2012-01-17T02:33:01Z <p>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.</p> <p>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.</p> <p>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?</p> <p>(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.)</p> http://mathoverflow.net/questions/85730/a-trick-or-a-general-technique-probabilistic-method/85751#85751 Answer by Ori Gurel-Gurevich for A trick or a general technique? (Probabilistic Method) Ori Gurel-Gurevich 2012-01-15T17:12:17Z 2012-01-16T22:58:16Z <p>EDIT: short false answer deleted. I believe something can be salvaged here, but it is too late for me now.</p> http://mathoverflow.net/questions/85730/a-trick-or-a-general-technique-probabilistic-method/85869#85869 Answer by cardinal for A trick or a general technique? (Probabilistic Method) cardinal 2012-01-17T00:55:32Z 2012-01-17T01:21:55Z <p>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$?</p> <p>Namely, $$\mathbb E P = \mathbb E \frac{P}{Q} Q \geq \bigg(\min \frac{P}{Q}\bigg) \mathbb E Q.$$</p> <p>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.</p> http://mathoverflow.net/questions/85730/a-trick-or-a-general-technique-probabilistic-method/85874#85874 Answer by Thierry Zell for A trick or a general technique? (Probabilistic Method) Thierry Zell 2012-01-17T01:22:27Z 2012-01-17T01:22:27Z <p>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.</p> <p>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 <strong>is</strong> possible to show that this formula yields~1, it's just not all that easy.)</p> http://mathoverflow.net/questions/85730/a-trick-or-a-general-technique-probabilistic-method/85877#85877 Answer by Will Sawin for A trick or a general technique? (Probabilistic Method) Will Sawin 2012-01-17T02:33:01Z 2012-01-17T02:33:01Z <p>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.</p> <p>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.</p> <p>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:</p> <p>$E'[P/Q]=E[PQ/QE[Q]]=E[P/E[Q]]=E[P]/E[Q]$</p>