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.)

concentration of exchangeable processes

Having thoroughly embarrassed myself in the previous post, let me shoot for something half-way redeeming.

Let X_1, X_2, ... be a sequence of {0,1}-valued random variables. We say that the process {X_i} is exchangeable if every finite-dimensional joint distribution is invariant under the permutation of indices. The de Finetti theorem characterizes the exchangeable processes as mixtures (possibly uncountable) of Bernoulli processes. Note that this is only true for infinite sequences -- there are well-known examples of finite exchangeable sequences that cannot be extended even by 1 (see Diaconis for a fascinating discussion).

Now exchangeable processes are in general not concentrated. Indeed, the measure P on {0,1}^n with P(00...0)=P(11...1)=1/2 (i.e., a mixture of two degenerate Bernoulli processes) is exchangeable but not concentrated.

However, I claim the following:

1. if P is a mixture of Bernoulli processes whose biases are bounded within
0<=a<=b<=1, and f:{0,1}^n -> R is 1-Lipschitz w.r.t. the normalized Hamming metric,
we have
P(f - Ef > t) <= exp(-2n(t-d)^2) where t < d =b-a and the bias of a Bernoulli process is P(X=1). Note that this recovers the ordinary McDiarmid bound, for which b=a, trivially.

2. if P only assigns positive probability to sequences with at most k ones,
we have
P(f - Ef > t) <= exp(-2n(t/2k)^2) ) for any f:{0,1}^n -> R that is 1-Lipschitz w.r.t. the normalized Hamming metric.

The proofs are standard and apparently not worthy of writing up -- but let me know if you try it and get stuck. Have these appeared in literature?

Tighter Hamming ball volume?

Let C(n,k) be the binomial coefficient "n choose k". We want to bound the sum of these, with k ranging from 0 to d. This is equivalent to bounding the volume of the n-dimensional Hamming ball of radius d. Denote this number by B(n,d).

A well-known bound (appearing, for example, in the Sauer-Shelah-VC lemma) is

B(n,d) <= (en/d)^d .

We are pretty sure that it can be sharpened, for example by writing a (1/2) in front of the RHS. (We actually think it can be sharpened by better than a constant.)

Thus has to be known. Anyone have a reference? Thanks in advance!

2 inequalities

1.

Let mu and nu be two Bernoulli measures on {0,1}, with biases p and q, respectively. Thus,
mu({1})=p=1-mu({0})
nu({1})=q=1-nu({0})

Let P and Q be the n-fold products of mu and nu, respectively. Thus, P and Q are two probability measures on {0,1}^n.

Show that
||P-Q|| <= n|p-q|
where ||.|| is the total variation norm (and <= is a poor man's way of writing \leq in plain text).

2.

Now assume that q = 1/2; thus Q is the uniform measure on {0,1}^n.

Show that
||P-Q|| <= C n^(1/2) |p-1/2|

where C>0 is some fixed universal constant. (Hint: Pinsker's inequality might come in handy.)



Are these novel or already known?

Back by popular demand

My anxious readership has been flooding me with emails, demanding to know if I'm still alive and why I quit blogging. (Just kidding. Is anyone still reading this thing?)

A good chunk of my time has been occupied by administrative activity (job search), as well as personal matters (both good and bad).

I regularly attend two courses: one by Gideon Schechtman and one by Itai Benjamini.

Here is a nice "paradox" from Gideon's first lecture. Consider the 2x2 square = [-1,1]^2. In each quadrant, inscribe a unit circle. Let S_2 be the largest circle about the origin not intersecting any of the inscribed unit circles. Let R_2 be its radius; compute R_2 (it's easy!).

Now repeat the same in n dimensions: divide [-1,1]^n into 2^n orthants, inscribe a unit ball in each one, and let R_n be the radius of the maximal ball about the origin that does not intersect any of the inscribed balls. It shouldn't take you more than 2 minutes to come up with a formula for R_n -- the basic 2-dimensional intuition carries over to higher dimensions.

However, to anyone not familiar with high-dimensional geometric phenomena, something very surprising should happen. I won't give it a away here, but feel free to discuss in the comments. This sort of "paradox" probably has a name -- anyone know what it is?

CS/politics -- dispelling the myth

I know that the blog's subtitle is "A math/computer science research blog", and that I haven't had a research post in months. I also know that this is the last place you want to turn to for politics.

The point of this post isn't really to weigh in on the upcoming US election -- I have nothing original to say about politics (it's hard enough to find original things to say in math/cs). My goal here is to dispel a false impression you might have gotten if you peruse math/cs blogs. You might naturally come to the conclusion that every mathematician/computer scientist is left-leaning and favors Obama.

You'd be wrong, though. One brave soul -- namely, Lev at Yale -- is willing to go against the current and argue in favor of McCain. Read his piece here. You owe it to yourself to step out of the echo chamber and hear a refreshing dissenting voice.

My exchange with Derbyshire

which he has kindly allowed me to post, is below. I'll address the comments in the previous post after Sabbath.

---

NRO diary
7 messages

---

Aryeh Kontorovich	Fri, Oct 3, 2008 at 1:54 AM
To: gxnmvw7e
Dear Mr. Derbyshire, your recent NRO diary has prompted me to write a blog post: http://absolutely-regular.blogspot.com/2008/10/non-apologia.html I assure you this is not hate-mail from an offended Christian! All the best, -Aryeh

---

John Derbyshire <>	Fri, Oct 3, 2008 at 2:13 AM
To: Aryeh Kontorovich <>
Thank you, Aryeh. I really didn't get any of that, though. >>there is absolutely no logical reason to prefer materialism over a belief in a higher power But there is: it's called "Occam's Razor" And why is there anything mysterious about humans caring for their children? All the higher animals care for their children. It's called n-a-t-u-r-e. Best, JD [Quoted text hidden] -- John Derbyshire [Old website] http:\\www.olimu.com [New website] http:\\www.johnderbyshire.com

---

Aryeh Kontorovich <>	Fri, Oct 3, 2008 at 2:26 AM
To: John Derbyshire <>
Thank you for the prompt reply! I think the readers would be rather interested to see your reply -- may I post it in the comments? Re: Occam's Razor. This is perfectly fine and good for understanding and predicting natural phenomena (and indeed, is a perfectly natural hypothesis selection criterion in science, with some rigorous mathematical justification). For morality and ethics, the scientific method is woefully inadequate. Re: n-a-t-u-r-e. Not so fast. Natural human instincts (such as for food and sex) are easily subverted by modern technology to serve pure hedonism (cf. junk food, contraception, pornography). Why doesn't every atheist spend his life on a womanizing drug binge? Cheers, -Aryeh [Quoted text hidden]

---

John Derbyshire <>	Fri, Oct 3, 2008 at 2:34 AM
To: Aryeh Kontorovich
Sure. Use as you like. Just spell my name right. On Thu, Oct 2, 2008 at 8:26 PM, Aryeh Kontorovich wrote: > Thank you for the prompt reply! I think the readers would be rather > interested to see your reply -- may I post it in the comments? > > Re: Occam's Razor. This is perfectly fine and good for understanding and > predicting natural phenomena (and indeed, is a perfectly natural hypothesis > selection criterion in science, with some rigorous mathematical > justification). For morality and ethics, the scientific method is woefully > inadequate. Sez who? Seems perfectly adequate to me. > > Re: n-a-t-u-r-e. Not so fast. Natural human instincts (such as for food and > sex) are easily subverted by modern technology to serve pure hedonism (cf. > junk food, contraception, pornography). Why doesn't every atheist spend his > life on a womanizing drug binge? It's an empirical fact that they don't. Perhaps they are just better in touch with their nature than you believers. The empirical fact is, in fact, even worse for your case than that. The less religion, the more morality. Religious nations (India, Nigeria, Mexico) have worse stats om crime, dysfunction, HIV, etc. that irreligious ones (Norway, Japan, New Zealand). The most religious subgroup of the US population is Af-Ams; the leasst religious, E-Asian Americans. Guess which way the crime/HIV/etc. stats go? If it's morality you want, hang out with unbelievers! JD [Quoted text hidden]

---

Aryeh Kontorovich	Fri, Oct 3, 2008 at 2:48 AM
To: John Derbyshire <>
Sure. Use as you like. Just spell my name right. did I misspell your name in the post or correspondence? My sincere apologies (though I haven't been able to locate an error after several cursory glances). > Re: Occam's Razor. This is perfectly fine and good for understanding and > predicting natural phenomena (and indeed, is a perfectly natural hypothesis > selection criterion in science, with some rigorous mathematical > justification). For morality and ethics, the scientific method is woefully > inadequate. Sez who? Seems perfectly adequate to me. Well, the Nazis had used the scientific method to determine that a human ceases to live outside a certain temperature and pressure range. Scientifically, those were sound experiments. Science tells us what we can do. Morality tells us what we should do. It's an empirical fact that they don't. Perhaps they are just better in touch with their nature than you believers. Actually, if you look at the demographics in America and Europe, you'll see that the believers make much better breeders than the non-believers. Say what you will about Muslims, but they certainly seem to be beating the rational, logical westerners at this game. The empirical fact is, in fact, even worse for your case than that. The less religion, the more morality. Religious nations (India, Nigeria, Mexico) have worse stats om crime, dysfunction, HIV, etc. that irreligious ones (Norway, Japan, New Zealand). The most religious subgroup of the US population is Af-Ams; the leasst religious, E-Asian Americans. Guess which way the crime/HIV/etc. stats go? If it's morality you want, hang out with unbelievers! I certainly wasn't defending all religions as morally virtuous (I was merely defending religious faith from the conflation with superstition). As far as moral superiority, I am only prepared to defend Judaism. -AK

---

John Derbyshire <>	Fri, Oct 3, 2008 at 1:08 PM
To: Aryeh Kontorovich <>
On Thu, Oct 2, 2008 at 8:48 PM, Aryeh Kontorovich >> > Re: Occam's Razor. This is perfectly fine and good for understanding and >> > predicting natural phenomena (and indeed, is a perfectly natural >> > hypothesis >> > selection criterion in science, with some rigorous mathematical >> > justification). For morality and ethics, the scientific method is >> > woefully >> > inadequate. >> >> Sez who? Seems perfectly adequate to me. > > > Well, the Nazis had used the scientific method to determine that a human > ceases to live outside a certain temperature and pressure range. > Scientifically, those were sound experiments. Science tells us what we can > do. Morality tells us what we should do. You lose a point there for being the first to say "Nazi". Don't you know the damn rules? >> It's an empirical fact that they don't. Perhaps they are just better >> in touch with their nature than you believers. > > Actually, if you look at the demographics in America and Europe, you'll see > that the believers make much better breeders than the non-believers. Say > what you will about Muslims, but they certainly seem to be beating the > rational, logical westerners at this game. Yes. Religious belief contributes to fitness (in the technical biological sense -- increases your genome's chances of passing on its material). And this proves ... what? That evolution is a haphazard business, that sooner or later heads in a wrong direction. Which any biologist could have told you. Biologist's joke: "To a first approximation, all species are extinct." It's actually about 99.9 percent. > >> The empirical fact is, in fact, even worse for your case than that. >> The less religion, the more morality. Religious nations (India, >> Nigeria, Mexico) have worse stats om crime, dysfunction, HIV, etc. >> that irreligious ones (Norway, Japan, New Zealand). The most >> religious subgroup of the US population is Af-Ams; the leasst >> religious, E-Asian Americans. Guess which way the crime/HIV/etc. >> stats go? >> >> If it's morality you want, hang out with unbelievers! > > > I certainly wasn't defending all religions as morally virtuous (I was merely > defending religious faith from the conflation with superstition). As far as > moral superiority, I am only prepared to defend Judaism. That old thing? I'll give it another 3,000 yrs, then -- pfffft! -- [Quoted text hidden]

---