Proofs that expose a deeper structure

Question

The standard proof of the Chernoff bound (from the Randomized Algorithms textbook) uses the Markov inequality and moment generating functions, with a bit of a Taylor expansion thrown in. Nothing too difficult, but somewhat mechanical.

But there are other Chernoff bound proofs that expose the deeper structure driving the result. For example, there's an information-theoretic version that goes via the method of types, exemplified by this paper of Impagliazzo and Kabanets, as well as this brief post by Sanjoy Dasgupta. These latter proofs are more "intuitive" in that they provides a generalization of the standard result, as well explaining where the funny terms in the exponent come from (it's a KL-divergence).

What are good examples of such things ? To be more concrete, here are the rules:

1. The statement should be reasonably well-known (the kind of thing that would be taught in some kind of graduate class)
2. There should be a "standard" proof available in textbooks or standard reference material that is "commonly" taught
3. There should be an alternate proof that is not so well known, is NOT commonly taught, and either proves a more general statement or links the statement to a deeper mathematical structure.

I'll start off with two examples.

1. The chernoff bound

   • "textbook" proof: markov inequality, moment generating functions, Taylor expansion (MR)
   • Uncommon and insightful proof: method of types, exponent of tail involving KL-divergence

2. The Schwartz-Zippel Lemma

   • "textbook" proof: base-case involving univariate polynomial. Induction on number of variables
   • "uncommon" proof: geometric argument via Dana Moshkovitz (and Per Vognsen)

One example per answer please.

p.s I'm not necessarily implying that the uncommon proof should be taught: a direct proof is often easier for students. But in the sense that "proofs help us understand", these alternate proofs are very helpful.

Answer 1

I'm not sure this is quite what you're looking for, since I've seen the "uncommon" proof in textbooks, but: the O(n log n) time bound for quicksort.

• "Textbook" proof: set up a randomized recurrence relation, prove by induction that it has the desired solution.

• "Uncommon" proof: find a simple formula for the probability that any two elements are compared (it's just 2/(d+1) where d is the difference between their ranks in the sorted order), and use linearity of expectation and harmonic series to compute the expected number of pairs that get compared.

The textbook proof requires less creative insight, but the uncommon proof introduces a technique that's very useful in other algorithm analysis e.g. for randomized incremental algorithms in computational geometry.

Answer 2

I'll throw out one from complexity, the proof that BPP is in $\Sigma_2^p$. The textbook proof is due to Lautemann, just write down the $\exists\forall$ expression and show it works with a simple probabilistic argument. The uncommon proof: Guess a hard function ($\exists$ to guess, $\forall$ to check hardness) and plug it into the Nisan-Wigderson generator.

Answer 3

We all know $\sum_i a_iX_i$ for Bernoulli $\pm 1$ $X_i$ should behave like a Gaussian with standard deviation $\sigma = \|a\|_2$, right? So, let's prove it by relating directly to Gaussians! Taking $t \ge 2$ an integer,

\begin{eqnarray*} \mathbf{E}\left[\left(\sum_i a_iX_i\right)^t\right] &=& \sum_{i_1,\ldots,i_t} \left(\prod_{j=1}^t a_{i_j}\right) \mathbf{E}\left[\prod_{j=1}^t X_{i_j}\right]\\ &\le& \sum_{i_1,\ldots,i_t} \left(\prod_{j=1}^t |a_{i_j}|\right) \mathbf{E}\left[\prod_{j=1}^t X_{i_j}\right]\\ &=& \sum_{\substack{i_1<\ldots< i_m\\ r_1,\ldots,r_m\\ \sum_j r_j = t\\ \forall j\ r_j > 0}} \binom{t}{r_1,\ldots,r_m}\left(\prod_{j=1}^m |a_{i_j}|^{r_j}\right)\left(\prod_{j=1}^m \mathbf{E}[X_{i_j}^{r_j}]\right) \end{eqnarray*}

Now, let's look at the above sum on the right. In any given summand, either some $r_j$ is odd, making the expectation $0$, or all are even, making it $1$. Imagine replacing all the $X_i$ with Gaussian $G_i$. Then we'd be in a similar scenario: odd $r_j$ would give $0$, and all even $r_j$ would make the product at least $1$. So the Gaussian case term by term dominates the Bernoulli case. Thus,

$$ \mathbf{E}\left[\left(\sum_i a_iX_i\right)^t\right] \le \mathbf{E}\left[\left(\sum_i |a_i|G_i\right)^t\right]$$

But, by $2$-stability of the Gaussian, $\sum_i |a_i| G_i$ is itself a Gaussian with standard deviation $\|a\|_2$, so we know its moments! Thus, our $t$th moment is bounded by $\|a\|_2^t \cdot t! / (2^{t/2} \cdot (t/2)!)$ (roughly $\|a\|_2^tt^{t/2}$); this is known as Khintchine's inequality. Then,

$$ \mathbf{Pr}\left[\left|\sum_i a_iX_i\right| > \lambda\right] < 2^{O(t)}\cdot \lambda^{-t}\cdot \|a\|_2^t t^{t/2}$$ Set $t = \lambda^2 / (C\cdot \|a\|_2^2)$ for a sufficiently large constant $C$ and you get the Gaussian tail bound $\mathrm{exp}(-\Omega(\lambda^2 / \|a\|_2^2))$. I first heard this proof of Khintchine's inequality when chatting with Daniel Kane, but probably there's an older reference. Notice the proof also makes it clear what level of independence amongst the $X_i$ you need to get various tail bounds.

Answer 4

Minc conjectured and Brégman proved that if $A$ is a 0-1 matrix with $r_i$ 1's in row $i$, then the permanent of $A$ is at most $$\prod_i (r_i!)^{1/r_i}.$$ There is a short proof in Alon and Spencer's textbook The Probabilistic Method, but arguably the "book" proof is Jaikumar Radhakrishnan's proof using entropy (J. Combin. Theory Ser. A 77 (1997), 161-164). It's not at all obvious from the statement of the result that the concept of entropy lies under the surface here.