## Sunday, April 22, 2007

### Breakdown of discrete intuition

Most of the classical inequalities -- Jensen, Hölder, Cauchy-Schwartz -- work for integrals just as well as for sums. In fact, it's best to think of these as integral inequalities with respect to a positive Borel measure (which includes the Lebesgue and the counting measures as special cases, and subsumes both sums and integrals). This can keep our intuition from being excessively taxed; I, for one, prefer to reason about sums and carry that intuition over to integrals. Are there instances where that intuition can fail?

Indeed there are, as Michael Steele shows us in Exercise 8.3 of his book. In part (a), we're asked to show that for all nonnegative sequences , we have
(the solution is given in the book, but readers are invited to attempt this one cold). In part (b), we're admonished against the careless conclusion that for (integrable) , we have

-- does anyone have an example where the latter fails?

A heuristic to guide one's intuition is the following principle of Hardy, Littlewood, and Pólya, called "homogeneity in ." That is, one considers as a formal symbol and checks the order to which an expression is "homogeneous in ." In this case, the lhs is homogeneous of order 2 while the rhs is homogeneous of order 3. According to the heuristic, this incompatibility destroys the integral analog. Anyone have more such examples where the integral analog fails? Could there be a general theorem lurking around?

Massimo said...

Maybe I miss something but my proof of the discrete case relies on the finiteness of the sequence. A fair comparison between the two case (sum and integral) IMHO should use an infinite sum. For infinite sums even the discrete case fails, with essentially the same counterexample of the continuos case. So I think the intuition breaks because of the finite-infinite jump, and not for the discrete-continuos jump.

Leo said...

Massimo,

Riemann integrals are approximated by finite sums -- as are infinite series. So I don't think the "number of terms" in the summation is the issue here; it's certainly not a problem in Holder, Jensen, or Cauchy-Schwartz(-Bunyakovski)

Anonymous said...

The reason the inequality between integrals does not hold is that integrals are the continuous analogues of *means*, not sums.

Leo said...

Thanks for the insight, anonymous (I wish you'd left a name!). As I said in the post, sums and integrals really are the same thing -- only the measure changes. However, you're right that integrating a function f:[0,1]->R
over [0,1] is the same as computing its average w.r.t. the uniform distribution on [0,1]. Extending the analogy to the discrete case requires us normalize by n (the sequence length), in which case the discrete inequality becomes easily falsifiable.

Csaba Szepesvári said...

Hi,
Try f(x) = x.
The reason the intuitition fails is indeed the lack of homogeneity:
Let A(n;f) = sum_{k=1}^n a_k^{1/2}, where a_k = f(k/n), B(n;f) = sum_{k=1}^n a_k^{1/3}. Then A(n;f) ~ n int_0^1 f(x)^{1/2} dx and B(n;f) ~ n int_0^1 f(x)^{1/3} dx. Hence A(n;f)^2 ~ n^2 (int_0^1 f(x)^{1/2} dx)^2, whilst B(n;f)^3 ~ n^3 (int_0^1 f(x)^{1/3} dx)^3. From this it is clear that A(n;f)^2<= B(n;f)^3 does not imply anything on the relation of the integrals (int_0^1 f(x)^{1/2} dx)^2, (int_0^1 f(x)^{1/3} dx)^3, because of the extra factor of n multiplying B(n;f)^3.

Leo said...

Thanks for really nailing it down, Csaba. So the issue indeed seems to be normalization by n. If f:[0,1]-> R is such that

[sum_{k=1}^n (1/n) f(k/n)^(1/2)]^2
<=
[sum_{k=1}^n (1/n) f(k/n)^(1/3)]^3

for all n, then the integral inequality will hold as well, right?

Csaba Szepesvári said...

Yes, indeed.