Monday, June 1, 2009

A reverse Jensen inequality for exponentials

Let x_1, ... x_n be real numbers and t_1, ... t_n be nonnegative numbers summing to 1.

A trivial consequence of Jensen's inequality is that

exp(t_1 x_1 + ... + t_n x_n) <= t_1 exp(x_1) + ... + t_n exp(x_n).

I claim that in the other direction, we have the following:

t_1 exp(x_1) + ... + t_n exp(x_n) <= exp( diam(x) + t_1 x_1 + ... + t_n x_n)

where diam(x) = max_i x_i - min_i x_i is the diameter of {x_1, ..., x_n}.

Any proof ideas? (Unlike my previous goof-ups, I can actually prove this one.)

cjgb said...

Easy one, as

diam + sum_i ( t_i x_i ) =

sum_i t_i ( diam + x_i ) <=

sum_i t_i max( x_i ) = max( x_i )

Therefore, the "converse" is true not only for exp but for any increasing function...

Aryeh said...

cjgb: your proof (and claim) fail for negative x. If the x's are all assumed to be positive and F is any increasing function, then trivially

t_1 F(x_1) + ... + t_n F(x_n)
<=
F(max x_i)

cjgb said...

Sorry, there was a small typo in my "proof". However, I still claim that it holds.

I want to prove that

t_1 exp(x_1) + ... + t_n exp(x_n) <= exp( diam(x) + t_1 x_1 + ... + t_n x_n)

If F is increasing (and exp is), you have, as you agreed, that

t_1 F(x_1) + ... + t_n F(x_n)
<=
F(max x_i)

All I would need to prove is that

max x_i <= diam + sum_i ( t_i x_i )

and that is exactly what my previous "proof" says (only that I wrote "<=" where I meant ">=". In fact,

max( x_i ) = sum_i t_i max( x_i ) <= sum_i t_i ( diam + x_i ) = diam + sum_i ( t_i x_i )

regardless of the sign of the x_i as

max_i x_i <= x_i + diam

Aryeh said...

Indeed, that does it! Very nicely done.