Three Bernstein inequalities

This post concerns three unrelated inequalities, or families of inequalities, that all go by the name of Bernstein’s inequality, after Sergei Natanovich Bernstein (Сергей Натанович Бернштейн). In no particular order, they are:

  • a family of inequalities in probability theory that bound the deviations of independent or weakly dependent random variables,
  • an inequality bounding the Lp norms of band-limited functions, and
  • an inequality bounding the derivatives of complex polynomials.

1. Deviations of Random Variables

There are quite a few Bernstein inequalities for families of independent or weakly correlated random variables X1, …, Xn. The following inequality is one of the simplest, but gives the general idea. Let X1, …, Xn be independent, but not necessarily identically distributed, real-valued random variables taking values in [−R, +R]. Then for any t > 0,

\displaystyle \mathbb{P} \left[ \sum_{j=1}^{n} X_j > t \right] \leq \exp \left( - \frac12 \frac{t^2}{\sum_{j=1}^{n} \mathbb{E} \bigl[ X_j^2 \bigr] + \frac{R t}{3}} \right).

For those readers who prefer to think in terms of the vector-valued random variable X = (X1, …, Xn), this inequality reads

\displaystyle \mathbb{P} \left[ \bigl\| \mathbf{X} \bigr\|_{1} > t \right] \leq \exp \left( - \frac12 \frac{t^2}{\mathbb{E} \bigl[ \bigl\| \mathbf{X} \bigr\|_{2}^{2} \bigr] + \frac{t}{3} \bigl\| \mathbf{X} \bigr\|_{\infty} } \right).

A similar inequality for negative t is easily obtained by replacing each random variable Xj by its negative. There are also many generalizations, some also known as Bernstein inequalities, and others falling under the general heading of concentration of measure.

2. Lp Norms of Band-Limited Functions

Suppose that f: ℝn → ℂ is band-limited in the sense that its Fourier transform ℱ[f]: ℝn → ℂ is identically zero outside the ball B(0, R) of radius R centred at the origin 0 of ℝn. Suppose also that 1 ≤ p < q < ∞. Then there is a constant C, independent of f, such that

\displaystyle \bigl\| f \bigr\|_{L^{q}(\mathbb{R}^{n})} \leq C R^{n (\frac1p - \frac1q)} \bigl\| f \bigr\|_{L^{p}(\mathbb{R}^{n})} .

In fact, with a possibly different constant, the same inequality holds with a weak Lp quasi-norm on the right-hand side:

\displaystyle \bigl\| f \bigr\|_{L^{q}(\mathbb{R}^{n})} \leq C R^{n (\frac1p - \frac1q)} \bigl\| f \bigr\|_{L^{p,\infty}(\mathbb{R}^{n})} .

This inequality is not too difficult to prove using Young’s inequality for convolutions and standard interpolation between L1,∞ and L2q,∞.

3. Derivatives of Polynomials

Suppose that p: ℂ → ℂ is a polynomial of degree n. Then Bernstein’s inequality for the polynomial p states that, on the unit disc

\displaystyle D := \bigl\{ z \in \mathbb{C} \big| |z| \leq 1 \bigr\},

the degree n of p, multiplied by the maximum absolute volue of p, bounds the maximum absolute value of the derivative of p:

\displaystyle \max_{z \in D} |p'(z)| \leq n \max_{z \in D} |p(z)|.

Similarly, for the kth derivative of p, it holds that

\displaystyle \max_{z \in D} |p^{(k)}(z)| \leq \frac{n!}{(n-k)!} \max_{z \in D} |p(z)|.

This Bernstein inequality is useful in the theory of polynomial approximation, since it gives some measure of approximation of derivatives “for free” once the function itself has been approximated.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s