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:
- The statement should be reasonably well-known (the kind of thing that would be taught in some kind of graduate class)
- There should be a "standard" proof available in textbooks or standard reference material that is "commonly" taught
- 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.
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
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.