The Lumber Room

"Consign them to dust and damp by way of preserving them"

Archive for June 29th, 2010

Convex, continuous, Jensen’s

with 3 comments

On the principle that things I’ve forgotten at least thrice are worth remembering…

A convex function (need a mnemonic?) is f such that
\displaystyle f(\lambda x + (1-\lambda)y) \le \lambda f(x) + (1-\lambda)f(y) for any λ in [0,1].

Midpoint convex (almost) implies convex
A natural question is whether we need all λ in [0,1]; what about just ½? Functions which satisfy
\displaystyle f(\frac{x+y}{2}) \le \frac{f(x)+f(y)}{2}
are called midpoint convex.

It turns out that when things are “nice” as in most frequently encountered cases, a midpoint convex function is convex. (A counterexample is this crazy non-measurable nowhere-continuous bounded-in-no-interval function: since R is a vectorspace over Q, there is a basis (that includes π, say), and any real number x has a unique representation as a finite rational sum of basis elements. Define f(x) to be the coefficient of π in the representation of x. This function is in fact linear over Q.)
For midpoint convex to mean convex, any of the following conditions will do:

  • f is continuous [Proof: prove the inequality for λ with denominators that are powers of 2, then use denseness in R.]
  • f is continuous at some point (any one point will do) [Proof: see next section]
  • f is (Lebesgue) measurable
  • f is bounded on some measurable set with positive measure

Convex functions are continuous
In fact, a stronger theorem is true: If a midpoint convex function is discontinuous at a single point, then it is unbounded on every interval and (hence) discontinuous everywhere.
Proof: Suppose wlog that f is discontinuous at 0, that f(0)=0, and that a sequence x_n \rightarrow 0 has f(x_n) \rightarrow m for some positive m. Prove that \liminf f(2^k x_n) \ge 2^k m, so f is unbounded near 0. Then use this to show unbounded everywhere.

Note that convex functions are bounded on every interval, so by above theorem they are continuous.

Convex functions are differentiable almost everywhere
In fact a convex function has left and right derivatives at all points, these are monotonically increasing, and there are only countably many points where they don’t coincide.

All the above is from pages 10 to 16 of this book I had found through googling; if anyone’s reading this, please tell me if you know better proofs.

A proof of Jensen’s inequality
Here, Jensen’s inequality is the statement that for a convex function f,
\displaystyle \mathbb{E}\left[f(X)\right] \geq f\left(\mathbb{E}\left[X\right]\right) .

An equivalent definition of a convex function is that at any point we can find a line through the point that lies entirely below the function. (Why?) In other words, for any point a, there is a “slope” m such that
\displaystyle f(x) \ge f(a) + m(x-a) for all x.
With this definition, Jensen’s inequality has an absurdly short proof: take a to be the mean \mathbb{E}\left[X\right], then take expectation.

Advertisements

Written by S

Tue, 2010-06-29 at 02:32:05

Posted in mathematics

Examples of bad design

with 15 comments

Design is hard. Don Norman, author of the wonderful book The Design of Everyday Things (written in 1988 and still a classic!) asked a question in the first five minutes of a recent talk:

Imagine you’re on the first slide of your powerpoint presentation and want to move to the next slide. Your remote control has two buttons. They are unmarked, but one button points up and one button points down.

Which button do you press?

It turns out that half the people would press up, half the people would press down, and everybody thinks their choice is obvious.

Even in cases where most of us get it right (like elevators), some are still confused. So it is easy to make mistakes, especially when designing the interface to a complex system. But it takes a special genius to take something simple and make it confusing:

Buttons with adjacent descriptions

Do the arrows describe the buttons beside them?

(from Stack Overflow.)

Written by S

Tue, 2010-06-29 at 01:03:27

Posted in Uncategorized