<p>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.</p>

<ul>
<li><p>"Textbook" proof: set up a randomized recurrence relation, prove by induction that it has the desired solution.</p></li>
<li><p>"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.</p></li>
</ul>

<p>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.</p>

CC BY-SA 2.5
2010-11-19T08:26:08.970Z
I think this works. it's a nice example. you're right that the 'uncommon' proof is also in textbooks, but still not that common.
Suresh Venkat
CC BY-SA 2.5
2010-11-19T15:15:13.570Z
I've been teaching undergrads that "uncommon" proof for over a decade.
Jeffε
CC BY-SA 2.5
2011-02-20T02:24:04.237Z
I do not know what others think of it; but Jon Bentley has given a very elegant runtime analysis for the expected runtime of quick sort in the text Beautiful Code. You can also acces his video over the same topic <a href="http://www.youtube.com/watch?v=aMnn0Jq0J-E">here</a>. I am pretty sure this is "the book's analysis" of quicksort's expected runtime
Akash Kumar
CC BY-SA 2.5
2010-11-19T07:55:09.953Z
2010-11-19T07:55:09.953Z
David Eppstein
<p>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. </p>

CC BY-SA 2.5
2010-11-19T11:52:09.407Z
Adding to that, Lautemann's proof greatly simplifies Sipser's proof (1983), which is attributed by Sipser to Gacs.
Sadeq Dousti
CC BY-SA 2.5
2010-11-19T11:53:01.450Z
Is there a reference for the "uncommon" proof, or is it folklore?
Sadeq Dousti
CC BY-SA 2.5
2010-11-19T14:34:25.143Z
The proof is in the Nisan-Wigderson paper.
Lance Fortnow
CC BY-SA 2.5
2010-11-20T03:36:13.100Z
It is an "uncommon proof" alright, but what is the "new understanding" from this proof? I would think Lautemann's proof is more illuminating. Am I missing something here?
V Vinay
CC BY-SA 2.5
2010-11-19T11:04:26.017Z
2010-11-19T11:04:26.017Z
Lance Fortnow
<p>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 <i>The Probabilistic Method</i>, but arguably the "book" proof is Jaikumar Radhakrishnan's proof using entropy (<i>J. Combin. Theory Ser. A</i> <b>77</b> (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.</p>

CC BY-SA 2.5
2011-01-05T16:56:06.063Z
2011-01-05T16:56:06.063Z
Timothy Chow
<p>The standard proof of the Chernoff bound (from the <a href="http://rads.stackoverflow.com/amzn/click/0521474655" rel="nofollow noreferrer">Randomized Algorithms</a> textbook) uses the Markov inequality and moment generating functions, with a bit of a Taylor expansion thrown in. Nothing too difficult, but somewhat mechanical. </p>

<p>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 <a href="http://www.cs.sfu.ca/~kabanets/Research/constructive-chernoff.html" rel="nofollow noreferrer">Impagliazzo and Kabanets</a>, as well as <a href="http://hunch.net/?p=1491" rel="nofollow noreferrer">this brief post by Sanjoy Dasgupta</a>. 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). </p>

<blockquote>
  <p>What are good examples of such things
  ? To be more concrete, here are the
  rules:</p>
  
  <ol>
  <li>The statement should be reasonably well-known (the kind of thing that
  would be taught in some kind of
  graduate class)</li>
  <li>There should be a "standard" proof available in textbooks or standard
  reference material that is "commonly"
  taught</li>
  <li>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.</li>
  </ol>
</blockquote>

<p>I'll start off with two examples. </p>

<ol>
<li><p>The chernoff bound</p>

<ul>
<li>"textbook" proof: markov inequality, moment generating functions, Taylor expansion (MR)</li>
<li>Uncommon and insightful proof: method of types, exponent of tail involving KL-divergence</li>
</ul></li>
<li><p><a href="http://en.wikipedia.org/wiki/Schwartz%E2%80%93Zippel_lemma" rel="nofollow noreferrer">The Schwartz-Zippel Lemma</a></p>

<ul>
<li>"textbook" proof: base-case involving univariate polynomial. Induction on number of variables</li>
<li>"uncommon" proof: geometric argument via <a href="http://eccc.hpi-web.de/report/2010/096/" rel="nofollow noreferrer">Dana Moshkovitz</a> (and <a href="https://cstheory.stackexchange.com/questions/1772/alternative-proofs-of-schwartzzippel-lemma/1883#1883">Per Vognsen</a>)</li>
</ul></li>
</ol>

<p>One example per answer please. </p>

<p>p.s I'm not necessarily implying that the uncommon proof <strong>should</strong> 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. </p>

<big-list><proofs>
Proofs that expose a deeper structure
Suresh Venkat
# Proofs that expose a deeper structure

(Asked by: username_0 on 2010-11-19)

The standard proof of the Chernoff bound (from the [Randomized Algorithms](http://rads.stackoverflow.com/amzn/click/0521474655) 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](http://www.cs.sfu.ca/~kabanets/Research/constructive-chernoff.html), as well as [this brief post by Sanjoy Dasgupta](http://hunch.net/?p=1491). 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](http://en.wikipedia.org/wiki/Schwartz%E2%80%93Zippel_lemma)

   * "textbook" proof: base-case involving univariate polynomial. Induction on number of variables
   * "uncommon" proof: geometric argument via [Dana Moshkovitz](http://eccc.hpi-web.de/report/2010/096/) (and [Per Vognsen](https://cstheory.stackexchange.com/questions/1772/alternative-proofs-of-schwartzzippel-lemma/1883#1883))

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.

**Tags:** big-list, proofs

---

## 3 answers

### Answer by username_1 on 2010-11-19. Score: 22

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.

> **Comments:**
> **username_0**: I think this works. it's a nice example. you're right that the 'uncommon' proof is also in textbooks, but still not that common.  
> **username_2**: I've been teaching undergrads that "uncommon" proof for over a decade.  
> **username_3**: I do not know what others think of it; but Jon Bentley has given a very elegant runtime analysis for the expected runtime of quick sort in the text Beautiful Code. You can also acces his video over the same topic <a href="http://www.youtube.com/watch?v=aMnn0Jq0J-E">here</a>. I am pretty sure this is "the book's analysis" of quicksort's expected runtime  

---

### Answer by username_4 on 2010-11-19. Score: 19

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.

> **Comments:**
> **username_5**: Adding to that, Lautemann's proof greatly simplifies Sipser's proof (1983), which is attributed by Sipser to Gacs.  
> **username_5**: Is there a reference for the "uncommon" proof, or is it folklore?  
> **username_4**: The proof is in the Nisan-Wigderson paper.  
> **username_6**: It is an "uncommon proof" alright, but what is the "new understanding" from this proof? I would think Lautemann's proof is more illuminating. Am I missing something here?  

---

### Answer by username_7 on 2011-01-05. Score: 6

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.


---

