254A, Notes 1: Concentration of measure

3 January, 2010 in 254A - random matrices, math.PR | Tags: Azuma's inequality, Chernoff inequality, concentration of measure, McDiarmid's inequality, moment method, Talagrand inequality

Suppose we have a large number of scalar random variables ${X_1,\ldots,X_n}$ , which each have bounded size on average (e.g. their mean and variance could be ${O(1)}$ ). What can one then say about their sum ${S_n := X_1+\ldots+X_n}$ ? If each individual summand ${X_i}$ varies in an interval of size ${O(1)}$ , then their sum of course varies in an interval of size ${O(n)}$ . However, a remarkable phenomenon, known as concentration of measure, asserts that assuming a sufficient amount of independence between the component variables ${X_1,\ldots,X_n}$ , this sum sharply concentrates in a much narrower range, typically in an interval of size ${O(\sqrt{n})}$ . This phenomenon is quantified by a variety of large deviation inequalities that give upper bounds (often exponential in nature) on the probability that such a combined random variable deviates significantly from its mean. The same phenomenon applies not only to linear expressions such as ${S_n = X_1+\ldots+X_n}$ , but more generally to nonlinear combinations ${F(X_1,\ldots,X_n)}$ of such variables, provided that the nonlinear function ${F}$ is sufficiently regular (in particular, if it is Lipschitz, either separately in each variable, or jointly in all variables).

The basic intuition here is that it is difficult for a large number of independent variables ${X_1,\ldots,X_n}$ to “work together” to simultaneously pull a sum ${X_1+\ldots+X_n}$ or a more general combination ${F(X_1,\ldots,X_n)}$ too far away from its mean. Independence here is the key; concentration of measure results typically fail if the ${X_i}$ are too highly correlated with each other.

There are many applications of the concentration of measure phenomenon, but we will focus on a specific application which is useful in the random matrix theory topics we will be studying, namely on controlling the behaviour of random ${n}$ -dimensional vectors with independent components, and in particular on the distance between such random vectors and a given subspace.

Once one has a sufficient amount of independence, the concentration of measure tends to be sub-gaussian in nature; thus the probability that one is at least ${\lambda}$ standard deviations from the mean tends to drop off like ${C \exp(-c\lambda^2)}$ for some ${C,c > 0}$ . In particular, one is ${O( \log^{1/2} n )}$ standard deviations from the mean with high probability, and ${O( \log^{1/2+\epsilon} n)}$ standard deviations from the mean with overwhelming probability. Indeed, concentration of measure is our primary tool for ensuring that various events hold with overwhelming probability (other moment methods can give high probability, but have difficulty ensuring overwhelming probability).

This is only a brief introduction to the concentration of measure phenomenon. A systematic study of this topic can be found in this book by Ledoux.

— 1. Linear combinations, and the moment method —

We begin with the simple setting of studying a sum ${S_n := X_1+\ldots+X_n}$ of random variables. As we shall see, these linear sums are particularly amenable to the moment method, though to use the more powerful moments, we will require more powerful independence assumptions (and, naturally, we will need more moments to be finite or bounded). As such, we will take the opportunity to use this topic (large deviation inequalities for sums of random variables) to give a tour of the moment method, which we will return to when we consider the analogous questions for the bulk spectral distribution of random matrices.

In this section we shall concern ourselves primarily with bounded random variables; in the next section we describe the basic truncation method that can allow us to extend from the bounded case to the unbounded case (assuming suitable decay hypotheses).

The zeroth moment method gives a crude upper bound when ${S}$ is non-zero,

$\displaystyle {\bf P}( S_n \neq 0 ) \leq \sum_{i=1}^n {\bf P}( X_i \neq 0 ) \ \ \ \ \ (1)$

but in most cases this bound is worse than the trivial bound ${{\bf P}(S_n \neq 0) \leq 1}$ . This bound, however, will be useful when performing the truncation trick, which we will discuss below.

The first moment method is somewhat better, giving the bound

$\displaystyle {\bf E} |S_n| \leq \sum_{i=1}^n {\bf E} |X_i|$

which when combined with Markov’s inequality gives the rather weak large deviation inequality

$\displaystyle {\bf P}( |S_n| \geq \lambda ) \leq \frac{1}{\lambda} \sum_{i=1}^n {\bf E} |X_i|. \ \ \ \ \ (2)$

As weak as this bound is, this bound is sometimes sharp. For instance, if the ${X_i}$ are all equal to a single signed Bernoulli variable ${X \in \{-1,+1\}}$ , then ${S_n = nX}$ , and so ${|S_n| = n}$ , and so (2) is sharp when ${\lambda=n}$ . The problem here is a complete lack of independence; the ${X_i}$ are all simultaneously positive or simultaneously negative, causing huge fluctuations in the value of ${S_n}$ .

Informally, one can view (2) as the assertion that ${S_n}$ typically has size ${S_n = O( \sum_{i=1}^n |X_i| )}$ .

The first moment method also shows that

$\displaystyle {\bf E} S_n = \sum_{i=1}^n {\bf E} X_i$

and so we can normalise out the means using the identity

$\displaystyle S_n - {\bf E} S_n = \sum_{i=1}^n X_i - {\bf E} X_i.$

Replacing the ${X_i}$ by ${X_i - {\bf E} X_i}$ (and ${S_n}$ by ${S_n - {\bf E} S_n}$ ) we may thus assume for simplicity that all the ${X_i}$ have mean zero.

Now we consider what the second moment method gives us. We square ${S_n}$ and take expectations to obtain

$\displaystyle {\bf E} |S_n|^2 = \sum_{i=1}^n \sum_{j=1}^n {\bf E} X_i \overline{X_j}.$

If we assume that the ${X_i}$ are pairwise independent (in addition to having mean zero), then ${{\bf E} X_i \overline{X_j}}$ vanishes unless ${i=j}$ , in which case this expectation is equal to ${{\bf Var}(X_i)}$ . We thus have

$\displaystyle {\bf Var}(S_n) = \sum_{i=1}^n {\bf Var}(X_i) \ \ \ \ \ (3)$

which when combined with Chebyshev’s inequality (and the mean zero normalisation) yields the large deviation inequality

$\displaystyle {\bf P}( |S_n| \geq \lambda ) \leq \frac{1}{\lambda^2} \sum_{i=1}^n {\bf Var}(X_i). \ \ \ \ \ (4)$

Without the normalisation that the ${X_i}$ have mean zero, we obtain

$\displaystyle {\bf P}( |S_n - {\bf E} S_n| \geq \lambda ) \leq \frac{1}{\lambda^2} \sum_{i=1}^n {\bf Var}(X_i). \ \ \ \ \ (5)$

Informally, this is the assertion that ${S_n}$ typically has size ${S_n = {\bf E} S_n + O( (\sum_{i=1}^n {\bf Var}(X_i))^{1/2} )}$ , if we have pairwise independence. Note also that we do not need the full strength of the pairwise independence assumption; the slightly weaker hypothesis of being pairwise uncorrelated would have sufficed.

The inequality (5) is sharp in two ways. Firstly, we cannot expect any significant concentration in any range narrower than the standard deviation ${O( (\sum_{i=1}^n {\bf Var}(X_i))^{1/2} )}$ , as this would likely contradict (3). Secondly, the quadratic-type decay in ${\lambda}$ in (5) is sharp given the pairwise independence hypothesis. For instance, suppose that ${n = 2^m-1}$ , and that ${X_j := (-1)^{a_j \cdot Y}}$ , where ${Y}$ is drawn uniformly at random from the cube ${\{0,1\}^m}$ , and ${a_1,\ldots,a_n}$ are an enumeration of the non-zero elements of ${\{0,1\}^m}$ . Then a little Fourier analysis shows that each ${X_j}$ for ${1 \leq j \leq n}$ has mean zero, variance ${1}$ , and are pairwise independent in ${j}$ ; but ${S}$ is equal to ${(n+1) {\bf I}( Y = 0 ) - 1}$ , which is equal to ${n}$ with probability ${1/(n+1)}$ ; this is despite the standard deviation of ${S}$ being just ${\sqrt{n}}$ . This shows that (5) is essentially (i.e. up to constants) sharp here when ${\lambda = n}$ .

Now we turn to higher moments. Let us assume that the ${X_i}$ are normalised to have mean zero and variance at most ${1}$ , and are also almost surely bounded in magnitude by some ${K}$ : ${|X_i| \leq K}$ . (The interesting regime here is when ${K \geq 1}$ , otherwise the variance is in fact strictly smaller than ${1}$ .) To simplify the exposition very slightly we will assume that the ${X_i}$ are real-valued; the complex-valued case is very analogous (and can also be deduced from the real-valued case) and is left to the reader.

Let us also assume that the ${X_1,\ldots,X_n}$ are ${k}$ -wise independent for some even positive integer ${k}$ . With this assumption, we can now estimate the ${k^{th}}$ moment

$\displaystyle {\bf E} |S_n|^k = \sum_{1 \leq i_1,\ldots,i_k \leq n} {\bf E} X_{i_1} \ldots X_{i_{k}}.$

To compute the expectation of the product, we can use the ${k}$ -wise independence, but we need to divide into cases (analogous to the ${i \neq j}$ and ${i=j}$ cases in the second moment calculation above) depending on how various indices are repeated. If one of the ${X_{i_j}}$ only appear once, then the entire expectation is zero (since ${X_{i_j}}$ has mean zero), so we may assume that each of the ${X_{i_j}}$ appear at least twice. In particular, there are at most ${k/2}$ distinct ${X_j}$ which appear. If exactly ${k/2}$ such terms appear, then from the unit variance assumption we see that the expectation has magnitude at most ${1}$ ; more generally, if ${k/2-r}$ terms appear, then from the unit variance assumption and the upper bound by ${K}$ we see that the expectation has magnitude at most ${K^{2r}}$ . This leads to the upper bound

$\displaystyle {\bf E} |S_n|^k \leq \sum_{r=0}^{k/2} K^{2r} N_r$

where ${N_r}$ is the number of ways one can assign integers ${i_1,\ldots,i_k}$ in ${\{1,\ldots,n\}}$ such that each ${i_j}$ appears at least twice, and such that exactly ${k/2-r}$ integers appear.

We are now faced with the purely combinatorial problem of estimating ${N_r}$ . We will use a somewhat crude bound. There are ${\binom{n}{k/2-r} \leq n^{k/2-r} / (k/2-r)!}$ ways to choose ${k/2-r}$ integers from ${\{1,\ldots,n\}}$ . Each of the integers ${i_j}$ has to come from one of these ${k/2-r}$ integers, leading to the crude bound

$\displaystyle N_r \leq \frac{n^{k/2-r}}{(k/2-r)!} (k/2-r)^k$

which after using a crude form ${n! \geq n^n e^{-n}}$ of Stirling’s formula gives

$\displaystyle N_r \leq (en)^{k/2-r} (k/2)^{k/2+r},$

and so

$\displaystyle {\bf E} |S_n|^k \leq (enk/2)^{k/2} \sum_{r=0}^{k/2} (\frac{K^2 k}{en})^r.$

If we make the mild assumption

$\displaystyle K^2 \leq n/k \ \ \ \ \ (6)$

then from the geometric series formula we conclude that

$\displaystyle {\bf E} |S_n|^k \leq 2 (enk/2)^{k/2}$

(say), which leads to the large deviation inequality

$\displaystyle {\bf P}( |S_n| \geq \lambda \sqrt{n} ) \leq 2 (\frac{\sqrt{ek/2}}{\lambda})^k. \ \ \ \ \ (7)$

This should be compared with (2), (5). As ${k}$ increases, the rate of decay in the ${\lambda}$ parameter improves, but to compensate for this, the range that ${S_n}$ concentrates in grows slowly, to ${O(\sqrt{nk})}$ rather than ${O(\sqrt{n})}$ .

Remark 1 Note how it was important here that ${k}$ was even. Odd moments, such as ${{\bf E} S_n^3}$ , can be estimated, but due to the lack of the absolute value sign, these moments do not give much usable control on the distribution of the ${S_n}$ . One could be more careful in the combinatorial counting than was done here, but the net effect of such care is only to improve the unspecified constant ${C}$ (which can easily be made explicit, but we will not do so here).

Now suppose that the ${X_1,\ldots,X_n}$ are not just ${k}$ -wise independent for any fixed ${k}$ , but are in fact jointly independent. Then we can apply (7) for any ${k}$ obeying (6). We can optimise in ${k}$ by setting ${\sqrt{nk}}$ to be a small multiple of ${\lambda}$ , and conclude the gaussian-type bound

$\displaystyle {\bf P}( |S_n| \geq \lambda \sqrt{n} ) \leq C \exp( - c \lambda^2 ) \ \ \ \ \ (8)$

for some absolute constants ${C, c > 0}$ , provided that ${|\lambda| \leq c \sqrt{n} / \sqrt{K}}$ for some small ${c}$ . (Note that the bound (8) is trivial for ${|\lambda| \gg \sqrt{n}}$ , so we may assume that ${\lambda}$ is small compared to this quantity.) Thus we see that while control of each individual moment ${{\bf E} |S_n|^k}$ only gives polynomial decay in ${\lambda}$ , by using all the moments simultaneously one can obtain square-exponential decay (i.e. subgaussian type decay).

By using Stirling’s formula (Exercise 2 from Notes 0a) one can show that the quadratic decay in (8) cannot be improved; see Exercise 2 below.

It was a little complicated to manage such large moments ${{\bf E} |S_n|^k}$ . A slicker way to proceed (but one which exploits the joint independence and commutativity more strongly) is to work instead with the exponential moments ${{\bf E} \exp( t S_n )}$ , which can be viewed as a sort of generating function for the power moments. A useful lemma in this regard is

Lemma 1 (Hoeffding’s lemma) Let ${X}$ be a scalar variable taking values in an interval ${[a,b]}$ . Then for any ${t>0}$ ,

$\displaystyle {\bf E} e^{tX} \leq e^{t {\bf E} X} (1 + O( t^2 {\bf Var}(X) \exp( O( t (b-a) ) ) ). \ \ \ \ \ (9)$

In particular

$\displaystyle {\bf E} e^{tX} \leq e^{t {\bf E} X} \exp( O( t^2 (b-a)^2 ) ). \ \ \ \ \ (10)$

Proof: It suffices to prove the first inequality, as the second then follows using the bound ${{\bf Var}(X) \leq (b-a)^2}$ and from various elementary estimates.

By subtracting the mean from ${X,a,b}$ we may normalise ${{\bf E}(X)=0}$ . By dividing ${X,a,b}$ (and multiplying ${t}$ to balance) we may assume that ${b-a=1}$ , which implies that ${X = O(1)}$ . We then have the Taylor expansion

$\displaystyle e^{tX} = 1 + tX + O( t^2 X^2 \exp( O(t) ) )$

which on taking expectations gives

$\displaystyle {\bf E} e^{tX} = 1 + O( t^2 {\bf Var}(X) \exp(O(t))$

and the claim follows. $\Box$

Exercise 1 Show that the ${O(t^2(b-a)^2)}$ factor in (10) can be replaced with ${t^2 (b-a)^2/8}$ , and that this is sharp. (Hint: use Jensen’s inequality.)

We now have the fundamental Chernoff bound:

Theorem 2 (Chernoff inequality) Let ${X_1,\ldots,X_n}$ be independent scalar random variables with ${|X_i| \leq K}$ almost surely, with mean ${\mu_i}$ and variance ${\sigma_i^2}$ . Then for any ${\lambda > 0}$ , one has

$\displaystyle {\bf P}( |S_n - \mu| \geq \lambda \sigma ) \leq C \max( \exp( - c \lambda^2 ), \exp( - c \lambda \sigma / K ) ) \ \ \ \ \ (11)$

for some absolute constants ${C, c > 0}$ , where ${\mu := \sum_{i=1}^n \mu_i}$ and ${\sigma^2 := \sum_{i=1}^n \sigma_i^2}$ .

Proof: By taking real and imaginary parts we may assume that the ${X_i}$ are real. By subtracting off the mean (and adjusting ${K}$ appropriately) we may assume that ${\mu_i=0}$ (and so ${\mu=0}$ ); dividing the ${X_i}$ (and ${\sigma_i}$ ) through by ${K}$ we may assume that ${K=1}$ . By symmetry it then suffices to establish the upper tail estimate

$\displaystyle {\bf P}( S_n \geq \lambda \sigma ) \leq C \max( \exp( - c \lambda^2 ), \exp( - c \lambda \sigma ) )$

(with slightly different constants ${C, c}$ ).

To do this, we shall first compute the exponential moments

$\displaystyle {\bf E} \exp( t S_n )$

where ${0 \leq t \leq 1}$ is a real parameter to be optimised later. Expanding out the exponential and using the independence hypothesis, we conclude that

$\displaystyle {\bf E} \exp( t S_n ) = \prod_{i=1}^n {\bf E} \exp(t X_i).$

To compute ${{\bf E}\exp(tX)}$ , we use the hypothesis that ${|X| \leq 1}$ and (9) to obtain

$\displaystyle {\bf E} \exp(tX) \leq \exp( O( t^2 \sigma_i^2 ) ).$

Thus we have

$\displaystyle {\bf E} \exp( t S_n ) = \exp( O( t^2 \sigma^2 ) )$

and thus by Markov’s inequality

$\displaystyle {\bf P}( S_n \geq \lambda \sigma ) \leq \exp( O( t^2 \sigma^2 ) - t \lambda \sigma ).$

If we optimise this in ${t}$ , subject to the constraint ${0 \leq t \leq 1}$ , we obtain the claim. $\Box$

Informally, the Chernoff inequality asserts that ${S_n}$ is sharply concentrated in the range ${n \mu + O(\sigma \sqrt{n})}$ . The bounds here are fairly sharp, at least when ${\lambda}$ is not too large:

Exercise 2 Let ${0 < p < 1/2}$ be fixed independently of ${n}$ , and let ${X_1,\ldots,X_n}$ be iid copies of a Bernoulli random variable that equals ${1}$ with probability ${p}$ , thus ${\mu_i=p}$ and ${\sigma_i^2 = p(1-p)}$ , and so ${\mu = np}$ and ${\sigma^2 = np(1-p)}$ . Using Stirling’s formula (Notes 0a), show that

$\displaystyle {\bf P}( |S_n - \mu| \geq \lambda \sigma ) \geq c \exp( - C \lambda^2 )$

for some absolute constants ${C, c > 0}$ and all ${\lambda \leq c\sigma}$ . What happens when ${\lambda}$ is much larger than ${\sigma}$ ?

Exercise 3 Show that the term ${\exp( - c \lambda \sigma / K )}$ in (11) can be replaced with ${(\lambda K/\sigma)^{-c \lambda \sigma / K}}$ (which is superior when ${\lambda K \gg \sigma}$ ). (Hint: Allow ${t}$ to exceed ${1}$ .) Compare this with the results of Exercise 2.

Exercise 4 (Hoeffding’s inequality) Let ${X_1,\ldots,X_n}$ be independent real variables, with ${X_i}$ taking values in an interval ${[a_i,b_i]}$ , and let ${S_n := X_1 + \ldots + X_n}$ . Show that one has

$\displaystyle {\bf P}( |S_n - {\bf E} S_n| \geq \lambda \sigma ) \leq C \exp( - c \lambda^2 )$

for some absolute constants ${C, c > 0}$ , where ${\sigma^2 := \sum_{i=1}^n |b_i-a_i|^2}$ .

Remark 2 As we can see, the exponential moment method is very slick compared to the power moment method. Unfortunately, due to its reliance on the identity ${e^{X+Y} = e^X e^Y}$ , this method relies very strongly on commutativity of the underlying variables, and as such will not be as useful when dealing with noncommutative random variables, and in particular with random matrices. Nevertheless, we will still be able to apply the Chernoff bound to good effect to various components of random matrices, such as rows or columns of such matrices.

The full assumption of joint independence is not completely necessary for Chernoff-type bounds to be present. It suffices to have a martingale difference sequence, in which each ${X_i}$ can depend on the preceding variables ${X_1,\ldots,X_{i-1}}$ , but which always has mean zero even when the preceding variables are conditioned out. More precisely, we have Azuma’s inequality:

Theorem 3 (Azuma’s inequality) Let ${X_1,\ldots,X_n}$ be a sequence of scalar random variables with ${|X_i| \leq 1}$ almost surely. Assume also that we have the martingale difference property

$\displaystyle {\bf E}( X_i | X_1,\ldots,X_{i-1} ) = 0 \ \ \ \ \ (12)$

almost surely for all ${i=1,\ldots,n}$ (here we assume the existence of a suitable disintegration in order to define the conditional expectation, though in fact it is possible to state and prove Azuma’s inequality without this disintegration). Then for any ${\lambda > 0}$ , the sum ${S_n := X_1 + \ldots + X_n}$ obeys the large deviation inequality

$\displaystyle {\bf P}(|S_n| \geq \lambda \sqrt{n} ) \leq C \exp( - c \lambda^2 ) \ \ \ \ \ (13)$

for some absolute constants ${C, c > 0}$ .

A typical example of ${S_n}$ here is a dependent random walk, in which the magnitude and probabilities of the ${i^{th}}$ step are allowed to depend on the outcome of the preceding ${i-1}$ steps, but where the mean of each step is always fixed to be zero.

Proof: Again, we can reduce to the case when the ${X_i}$ are real, and it suffices to establish the upper tail estimate

$\displaystyle {\bf P}(S_n \geq \lambda \sqrt{n} ) \leq C \exp( - c \lambda^2 ).$

Note that ${|S_n| \leq n}$ almost surely, so we may assume without loss of generality that ${\lambda \leq \sqrt{n}}$ .

Once again, we consider the exponential moment ${{\bf E} \exp( t S_n )}$ for some parameter ${t>0}$ . We write ${S_n = S_{n-1} + X_n}$ , so that

$\displaystyle {\bf E} \exp( t S_n ) = {\bf E} \exp( t S_{n-1} ) \exp( t X_n ).$

We do not have independence between ${S_{n-1}}$ and ${X_n}$ , so cannot split the expectation as in the proof of Chernoff’s inequality. Nevertheless we can use conditional expectation as a substitute. We can rewrite the above expression as

$\displaystyle {\bf E} {\bf E}( \exp( t S_{n-1} ) \exp( t X_n ) | X_1,\ldots,X_{n-1} ).$

The quantity ${S_{n-1}}$ is deterministic once we condition on ${X_1,\ldots,X_{n-1}}$ , and so we can pull it out of the conditional expectation:

$\displaystyle {\bf E} \exp( t S_{n-1} ) {\bf E}( \exp( t X_n ) | X_1,\ldots,X_{n-1} ).$

Applying (10) to the conditional expectation, we have

$\displaystyle {\bf E}( \exp( t X_n ) | X_1,\ldots,X_{n-1} ) \leq \exp(O(t^2))$

and

$\displaystyle {\bf E} \exp( t S_n ) \leq \exp(O(t^2)) {\bf E} \exp(t S_{n-1}).$

Iterating this argument gives

$\displaystyle {\bf E} \exp( t S_n ) \leq \exp(O(n t^2))$

and thus by Markov’s inequality

$\displaystyle {\bf P}(S_n \geq \lambda \sqrt{n} ) \leq \exp( O(n t^2) - t \lambda \sqrt{n} ).$

Optimising in ${t}$ gives the claim. $\Box$

Exercise 5 Suppose we replace the hypothesis ${|X_i| \leq 1}$ in Azuma’s inequality with the more general hypothesis ${|X_i| \leq c_i}$ for some scalars ${c_i > 0}$ . Show that we still have (13), but with ${\sqrt{n}}$ replaced by ${(\sum_{i=1}^n c_i^2)^{1/2}}$ .

Remark 3 The exponential moment method is also used frequently in harmonic analysis to deal with lacunary exponential sums, or sums involving Radamacher functions (which are the analogue of lacunary exponential sums for characteristic ${2}$ ). Examples here include Khintchine’s inequality (and the closely related Kahane’s inequality). The exponential moment method also combines very well with log-Sobolev inequalities, as we shall see below (basically because the logarithm inverts the exponential), as well as with the closely related hypercontractivity inequalities.

— 2. The truncation method —

To summarise the discussion so far, we have identified a number of large deviation inequalities to control a sum ${S_n = X_1 + \ldots + X_n}$ :

The zeroth moment method bound (1), which requires no moment assumptions on the ${X_i}$ but is only useful when ${X_i}$ is usually zero, and has no decay in ${\lambda}$ .
The first moment method bound (2), which only requires absolute integrability on the ${X_i}$ , but has only a linear decay in ${\lambda}$ .
The second moment method bound (5), which requires second moment and pairwise independence bounds on ${X_i}$ , and gives a quadratic decay in ${\lambda}$ .
Higher moment bounds (7), which require boundedness and ${k}$ -wise independence, and give a ${k^{th}}$ power decay in ${\lambda}$ (or quadratic-exponential decay, after optimising in ${k}$ ).
Exponential moment bounds such as (11) or (13), which require boundedness and joint independence (or martingale behaviour), and give quadratic-exponential decay in ${\lambda}$ .

We thus see that the bounds with the strongest decay in ${\lambda}$ require strong boundedness and independence hypotheses. However, one can often partially extend these strong results from the case of bounded random variables to that of unbounded random variables (provided one still has sufficient control on the decay of these variables) by a simple but fundamental trick, known as the truncation method. The basic idea here is to take each random variable ${X_i}$ and split it as ${X_i = X_{i,\leq N} + X_{i,>N}}$ , where ${N}$ is a truncation parameter to be optimised later (possibly in manner depending on ${n}$ ),

$\displaystyle X_{i,\leq N} := X_i {\bf I}(|X_i| \leq N)$

is the restriction of ${X_i}$ to the event that ${|X_i| \leq N}$ (thus ${X_{i,\leq N}}$ vanishes when ${X_i}$ is too large), and

$\displaystyle X_{i,> N} := X_i {\bf I}(|X_i| > N)$

is the complementary event. One can similarly split ${S_n = S_{n,\leq N} + S_{n,>N}}$ where

$\displaystyle S_{n,\leq N} = X_{1,\leq N} + \ldots + X_{n,\leq N}$

and

$\displaystyle S_{n,> N} = X_{1,>N} + \ldots + X_{n,>N}.$

The idea is then to estimate the tail of ${S_{n,\leq N}}$ and ${S_{n,>N}}$ by two different means. With ${S_{n,\leq N}}$ , the point is that the variables ${X_{i,\leq N}}$ have been made bounded by fiat, and so the more powerful large deviation inequalities can now be put into play. With ${S_{n,>N}}$ , in contrast, the underlying variables ${X_{i,>N}}$ are certainly not bounded, but they tend to have small zeroth and first moments, and so the bounds based on those moment methods tend to be powerful here. (Readers who are familiar with harmonic analysis may recognise this type of divide and conquer argument as an interpolation argument.)

Let us begin with a simple application of this method.

Theorem 4 (Weak law of large numbers) Let ${X_1,X_2,\ldots}$ be iid scalar random variables with ${X_i \equiv X}$ for all ${i}$ , where ${X}$ is absolutely integrable. Then ${S_n/n}$ converges in probability to ${{\bf E} X}$ .

Proof: By subtracting ${{\bf E} X}$ from ${X}$ we may assume without loss of generality that ${X}$ has mean zero. Our task is then to show that ${{\bf P}( |S_n| \geq \epsilon n ) = o(1)}$ for all fixed ${\epsilon > 0}$ .

If ${X}$ has finite variance, then the claim follows from (5). If ${X}$ has infinite variance, we cannot apply (5) directly, but we may perform the truncation method as follows. Let ${N}$ be a large parameter to be chosen later, and split ${X_i = X_{i,\leq N} + X_{i,> N}}$ , ${S_n = S_{n,\leq N} + S_{n,> N}}$ (and ${X = X_{\leq N} + X_{>N}}$ ) as discussed above. The variable ${X_{\leq N}}$ is bounded and thus has bounded variance; also, from the dominated convergence theorem we see that ${|{\bf E} X_{\leq N}| \leq \epsilon/4}$ (say) if ${N}$ is large enough. From (5) we conclude that

$\displaystyle {\bf P}( |S_{n,\leq N}| \geq \epsilon n / 2 ) = o(1)$

(where the rate of decay here depends on ${N}$ and ${\epsilon}$ ). Meanwhile, to deal with the tail ${X_{>N}}$ we use (2) to conclude that

$\displaystyle {\bf P}( |S_{n,>N}| \geq \epsilon n / 2 ) \leq \frac{2}{\epsilon} {\bf E} |X_{>N}|.$

But by the dominated convergence theorem (or monotone convergence theorem), we may make ${{\bf E} |X_{>N}|}$ as small as we please (say, smaller than ${\delta > 0}$ ) by taking ${N}$ large enough. Summing, we conclude that

$\displaystyle {\bf P}( |S_{n}| \geq \epsilon n ) = \frac{2}{\epsilon} \delta + o(1);$

since ${\delta}$ is arbitrary, we obtain the claim. $\Box$

A more sophisticated variant of this argument (which I gave in this earlier blog post, which also has some further discussion and details) gives

Theorem 5 (Strong law of large numbers) Let ${X_1,X_2,\ldots}$ be iid scalar random variables with ${X_i \equiv X}$ for all ${i}$ , where ${X}$ is absolutely integrable. Then ${S_n/n}$ converges almost surely to ${{\bf E} X}$ .

Proof: We may assume without loss of generality that ${X}$ is real, since the complex case then follows by splitting into real and imaginary parts. By splitting ${X}$ into positive and negative parts, we may furthermore assume that ${X}$ is non-negative. (Of course, by doing so, we can no longer normalise ${X}$ to have mean zero, but for us the non-negativity will be more convenient than the zero mean property.) In particular, ${S_n}$ is now non-decreasing in ${n}$ .

Next, we apply a sparsification trick. Let ${0 < \epsilon < 1}$ . Suppose that we knew that, almost surely, ${S_{n_m}/{n_m}}$ converged to ${{\bf E} X}$ for ${n=n_m}$ of the form ${n_m := \lfloor (1+\epsilon)^m \rfloor}$ for some integer ${m}$ . Then, for all other values of ${n}$ , we see that asymptotically, ${S_n/n}$ can only fluctuate by a multiplicative factor of ${1+O(\epsilon)}$ , thanks to the monotone nature of ${S_n}$ . Because of this and countable additivity, we see that it suffices to show that ${S_{n_m}/{n_m}}$ converges to ${{\bf E} X}$ . Actually, it will be enough to show that almost surely, one has ${|S_{n_m}/{n_m} - {\bf E} X| \leq \epsilon}$ for all but finitely many ${m}$ .

Fix ${\epsilon}$ . As before, we split ${X = X_{>N_m} + X_{\leq N_m}}$ and ${S_{n_m} = S_{n_m,>N_m} + S_{n_m,\leq N_m}}$ , but with the twist that we now allow ${N = N_m}$ to depend on ${m}$ . Then for ${N_m}$ large enough we have ${|{\bf E} X_{\leq N_m} - {\bf E} X| \leq \epsilon/2}$ (say), by dominated convergence. Applying (5) as before, we see that

$\displaystyle {\bf P}( |S_{n_m,\leq N_m}/{n_m} - {\bf E} X| > \epsilon ) \leq \frac{C_\epsilon}{n_m} {\bf E} |X_{\leq N_m}|^2$

for some ${C_\epsilon}$ depending only on ${\epsilon}$ (the exact value is not important here). To handle the tail, we will not use the first moment bound (2) as done previously, but now turn to the zeroth-moment bound (1) to obtain

$\displaystyle {\bf P}( S_{n_m, >N_m} \neq 0 ) \leq n_m {\bf P}( |X| > N_m );$

summing, we conclude

$\displaystyle {\bf P}( |S_{n_m}/{n_m} - {\bf E} X| > \epsilon ) \leq \frac{C_\epsilon}{n_m} {\bf E} |X_{\leq N_m}|^2 + n_m {\bf P}( |X| > N_m ).$

Applying the Borel-Cantelli lemma (Exercise 1 from Notes 0), we see that we will be done as long as we can choose ${N_m}$ such that

$\displaystyle \sum_{m=1}^\infty \frac{1}{n_m} {\bf E} |X_{\leq N_m}|^2$

and

$\displaystyle \sum_{m=1}^\infty n_m {\bf P}( |X| > N_m )$

are both finite. But this can be accomplished by setting ${N_m := n_m}$ and interchanging the sum and expectations (writing ${{\bf P}( |X| > N_m )}$ as ${{\bf E} {\bf I}(|X| > N_m)}$ ) and using the lacunary nature of the ${n_m}$ . $\Box$

To give another illustration of the truncation method, we extend a version of the Chernoff bound to the subgaussian case.

Proposition 6 Let ${X_1,\ldots,X_n \equiv X}$ be iid copies of a subgaussian random variable ${X}$ , thus ${X}$ obeys a bound of the form

$\displaystyle {\bf P}(|X| \geq t) \leq C \exp( - c t^2 ) \ \ \ \ \ (14)$

for all ${t>0}$ and some ${C,c>0}$ . Let ${S_n := X_1+\ldots+X_n}$ . Then for any sufficiently large ${A}$ (independent of ${n}$ ) we have

$\displaystyle {\bf P}( |S_n - n {\bf E} X| \geq A n ) \leq C_A \exp( - c_A n )$

for some constants ${C_A, c_A}$ depending on ${A,p,C,c}$ . Furthermore, ${c_A}$ grows linearly in ${A}$ as ${A \rightarrow \infty}$ .

Proof: By subtracting the mean from ${X}$ we may normalise ${{\bf E} X = 0}$ . We perform a dyadic decomposition

$\displaystyle X_i = X_{i,0} + \sum_{m=1}^\infty X_{i,m}$

where ${X_{i,0} := X_i {\bf I}(|X_i| \leq 1)}$ and ${X_{i,m} := X_i {\bf I}(2^{m-1} < |X_i| \leq 2^m)}$ . We similarly split

$\displaystyle S_n = S_{n,0} + \sum_{m=1}^\infty S_{n,m}$

where ${S_{n,m} = \sum_{i=1}^n X_{i,m}}$ . Then by the union bound and the pigeonhole principle we have

$\displaystyle {\bf P}( |S_n| \geq A n ) \leq \sum_{m=0}^\infty {\bf P}( |S_{n,m}| \geq \frac{A}{100(m+1)^2} n )$

(say). Each ${X_{i,m}}$ is clearly bounded in magnitude by ${2^m}$ ; from the subgaussian hypothesis one can also verify that the mean and variance of ${X_{i,m}}$ are at most ${C' \exp( - c' 2^{2m} )}$ for some ${C', c' > 0}$ . If ${A}$ is large enough, an application of the Chernoff bound (11) (or more precisely, the refinement in Exercise 3) then gives (after some computation)

$\displaystyle {\bf P}( |S_{n,m}| \geq 2^{-m-1} A n ) \leq C' 2^{-m} \exp( - c' A n )$

(say) for some ${C', c' > 0}$ , and the claim follows. $\Box$

Exercise 6 Show that the hypothesis that ${A}$ is sufficiently large can be replaced by the hypothesis that ${A>0}$ is independent of ${n}$ . Hint: There are several approaches available. One can adapt the above proof; one can modify the proof of the Chernoff inequality directly; or one can figure out a way to deduce the small ${A}$ case from the large ${A}$ case.

Exercise 7 Show that the subgaussian hypothesis can be generalised to a sub-exponential tail hypothesis

$\displaystyle {\bf P}(|X| \geq t) \leq C \exp( - c t^p )$

provided that ${p>1}$ . Show that the result also extends to the case ${0 < p \leq 1}$ , except with the exponent ${\exp( - c_A n )}$ replaced by ${\exp( - c_A n^{p-\epsilon} )}$ for some ${\epsilon > 0}$ . (I do not know if the ${\epsilon}$ loss can be removed, but it is easy to see that one cannot hope to do much better than this, just by considering the probability that ${X_1}$ (say) is already as large as ${An}$ .)

— 3. Lipschitz combinations —

In the preceding discussion, we had only considered the linear combination ${X_1,\ldots,X_n}$ of independent variables ${X_1,\ldots,X_n}$ . Now we consider more general combinations ${F(X)}$ , where we write ${X := (X_1,\ldots,X_n)}$ for short. Of course, to get any non-trivial results we must make some regularity hypotheses on ${F}$ . It turns out that a particularly useful class of regularity hypothesis here is a Lipschitz hypothesis – that small variations in ${X}$ lead to small variations in ${F(X)}$ . A simple example of this is McDiarmid’s inequality:

Theorem 7 (McDiarmid’s inequality) Let ${X_1,\ldots,X_n}$ be independent random variables taking values in ranges ${R_1,\ldots,R_n}$ , and let ${F: R_1 \times \ldots \times R_n \rightarrow {\bf C}}$ be a function with the property that if one freezes all but the ${i^{th}}$ coordinate of ${F(x_1,\ldots,x_n)}$ for some ${1 \leq i \leq n}$ , then ${F}$ only fluctuates by most ${c_i > 0}$ , thus

$\displaystyle |F(x_1,\ldots,x_{i-1},x_i,x_{i+1},\ldots,x_n) -$

$\displaystyle F(x_1,\ldots,x_{i-1},x_i',x_{i+1},\ldots,x_n)| \leq c_i$

for all ${x_j \in X_j}$ , ${x'_i \in X_i}$ for ${1 \leq j \leq n}$ . Then for any ${\lambda > 0}$ , one has

$\displaystyle {\bf P}( |F(X) - {\bf E} F(X)| \geq \lambda \sigma ) \leq C \exp(- c \lambda^2 )$

for some absolute constants ${C,c>0}$ , where ${\sigma^2 := \sum_{i=1}^n c_i^2}$ .

Proof: We may assume that ${F}$ is real. By symmetry, it suffices to show the one-sided estimate

$\displaystyle {\bf P}( F(X) - {\bf E} F(X) \geq \lambda \sigma^2 ) \leq C \exp(- c \lambda^2 ). \ \ \ \ \ (15)$

To compute this quantity, we again use the exponential moment method. Let ${t > 0}$ be a parameter to be chosen later, and consider the exponential moment

$\displaystyle {\bf E} \exp( t F(X) ). \ \ \ \ \ (16)$

To compute this, let us condition ${X_1,\ldots,X_{n-1}}$ to be fixed, and look at the conditional expectation

$\displaystyle {\bf E}(\exp( t F(X) ) | X_1,\ldots,X_{n-1} ).$

We can simplify this as

$\displaystyle {\bf E}( \exp( t Y) | X_1,\ldots,X_{n-1} ) \exp( t {\bf E}(F(X)|X_1,\ldots,X_{n-1}) )$

where

$\displaystyle Y := F(X) - {\bf E}( F(X)|X_1,\ldots,X_{n-1})$

For ${X_1,\ldots,X_{n-1}}$ fixed, ${tY}$ only fluctuates by at most ${t c_n}$ and has mean zero. Applying (10), we conclude that

$\displaystyle {\bf E}( \exp( t Y) | X_1,\ldots,X_{n-1} ) \leq \exp( O( t^2 c_n^2 ) ).$

Integrating out the conditioning, we see that we have upper bounded (16) by

$\displaystyle \exp(O(t^2 c_n^2)) {\bf E} \exp( t ({\bf E}(F(X)|X_1,\ldots,X_{n-1}) ).$

We observe that ${({\bf E}(F(X)|X_1,\ldots,X_{n-1})}$ is a function ${F_{n-1}(X_1,\ldots,X_{n-1})}$ of ${X_1,\ldots,X_{n-1}}$ , where ${F_{n-1}}$ obeys the same hypotheses as ${F}$ (but for ${n-1}$ instead of ${n}$ ). We can then iterate the above computation ${n}$ times and eventually upper bound (16) by

$\displaystyle \exp(\sum_{i=1}^n O(t^2 c_i^2) ) \exp( t {\bf E} F(X) ),$

which we rearrange as

$\displaystyle {\bf E} \exp( t (F(X) - {\bf E} F(X)) ) \leq \exp( O(t^2 \sigma^2) ),$

and thus by Markov’s inequality

$\displaystyle {\bf P}( F(X) - {\bf E} F(X) \geq \lambda \sigma ) \leq \exp( O( t^2 \sigma^2 ) - t \lambda \sigma ).$

Optimising in ${t}$ then gives the claim. $\Box$

Exercise 8 Show that McDiarmid’s inequality implies Hoeffding’s inequality (Exercise 4).

Remark 4 One can view McDiarmid’s inequality as a tensorisation of Hoeffding’s lemma, as it leverages the latter lemma for a single random variable to establish an analogous result for ${n}$ random variables. It is possible to apply this tensorisation trick to random variables taking values in more sophisticated metric spaces than an interval ${[a,b]}$ , leading to a class of concentration of measure inequalities known as transportation cost-information inequalities, which will not be discussed here.

The most powerful concentration of measure results, though, do not just exploit Lipschitz type behaviour in each individual variable, but joint Lipschitz behaviour. Let us first give a classical instance of this, in the special case when the ${X_1,\ldots,X_n}$ are gaussian variables. A key property of gaussian variables is that any linear combination of independent gaussians is again an independent gaussian:

Exercise 9 Let ${X_1,\ldots,X_n}$ be independent real gaussian variables with ${X_i = N(\mu_i,\sigma_i^2)_{\bf R}}$ , and let ${c_1,\ldots,c_n}$ be real constants. Show that ${c_1 X_1 +\ldots + c_n X_n}$ is a real gaussian with mean ${\sum_{i=1}^n c_i \mu_i}$ and variance ${\sum_{i=1}^n |c_i|^2 \sigma_i^2}$ .

Show that the same claims also hold with complex gaussians and complex constants ${c_i}$ .

Exercise 10 (Rotation invariance) Let ${X = (X_1,\ldots,X_n)}$ be an ${{\bf R}^n}$ -valued random variable, where ${X_1,\ldots,X_n \equiv N(0,1)_{\bf R}}$ are iid real gaussians. Show that for any orthogonal matrix ${U \in O(n)}$ , ${UX \equiv X}$ .

Show that the same claim holds for complex gaussians (so ${X}$ is now ${{\bf C}^n}$ -valued), and with the orthogonal group ${O(n)}$ replaced by the unitary group ${U(n)}$ .

Theorem 8 (Gaussian concentration inequality for Lipschitz functions) Let ${X_1,\ldots,X_n \equiv N(0,1)_{\bf R}}$ be iid real gaussian variables, and let ${F: {\bf R}^n \rightarrow {\bf R}}$ be a ${1}$ -Lipschitz function (i.e. ${|F(x)-F(y)| \leq |x-y|}$ for all ${x,y \in {\bf R}^n}$ , where we use the Euclidean metric on ${{\bf R}^n}$ ). Then for any ${\lambda}$ one has

$\displaystyle {\bf P}( |F(X) - {\bf E} F(X)| \geq \lambda ) \leq C \exp(-c \lambda^2 )$

for some absolute constants ${C, c > 0}$ .

Proof: We use the following elegant argument of Maurey and Pisier. By subtracting a constant from ${F}$ , we may normalise ${{\bf E} F(X) = 0}$ . By symmetry it then suffices to show the upper tail estimate

$\displaystyle {\bf P}( F(X) \geq \lambda ) \leq C \exp(-c \lambda^2 ).$

By smoothing ${F}$ slightly we may assume that ${F}$ is smooth, since the general case then follows from a limiting argument. In particular, the Lipschitz bound on ${F}$ now implies the gradient estimate

$\displaystyle |\nabla F(x)| \leq 1 \ \ \ \ \ (17)$

for all ${x \in {\bf R}^n}$ .

Once again, we use the exponential moment method. It will suffice to show that

$\displaystyle {\bf E} \exp( t F(X) ) \leq \exp( C t^2 )$

for some constant ${C>0}$ and all ${t>0}$ , as the claim follows from Markov’s inequality and optimisation in ${t}$ as in previous arguments.

To exploit the Lipschitz nature of ${F}$ , we will need to introduce a second copy of ${F(X)}$ . Let ${Y}$ be an independent copy of ${X}$ . Since ${{\bf E} F(Y) = 0}$ , we see from Jensen’s inequality that

$\displaystyle {\bf E} \exp( - t F(Y) ) \geq 1$

and thus (by independence of ${X}$ and ${Y}$ )

$\displaystyle {\bf E} \exp( t F(X) ) \leq {\bf E} \exp( t (F(X) - F(Y)) ).$

It is tempting to use the fundamental theorem of calculus along a line segment,

$\displaystyle F(X) - F(Y) = \int_0^1 \frac{d}{dt} F((1-t) Y + t X)\ dt,$

to estimate ${F(X)-F(Y)}$ , but it turns out for technical reasons to be better to use a circular arc instead,

$\displaystyle F(X) - F(Y) = \int_0^{\pi/2} \frac{d}{d\theta} F(Y \cos \theta + X \sin \theta)\ d\theta,$

The reason for this is that ${X_\theta := Y \cos \theta + X \sin \theta}$ is another gaussian random variable equivalent to ${X}$ , as is its derivative ${X'_\theta := -Y \sin \theta + X \cos \theta}$ (by Exercise 9); furthermore, and crucially, these two random variables are independent (by Exercise 10).

To exploit this, we first use Jensen’s inequality to bound

$\displaystyle \exp( t (F(X) - F(Y))) \leq \frac{2}{\pi} \int_0^{\pi/2} \exp( \frac{2t}{\pi} \frac{d}{d\theta} F( X_\theta ) )\ d\theta.$

Applying the chain rule and taking expectations, we have

$\displaystyle {\bf E} \exp( t (F(X) - F(Y))) \leq \frac{2}{\pi} \int_0^{\pi/2} {\bf E} \exp( \frac{2t}{\pi} \nabla F( X_\theta ) \cdot X'_\theta )\ d\theta.$

Let us condition ${X_\theta}$ to be fixed, then ${X'_\theta \equiv X}$ ; applying Exercise 9 and (17), we conclude that ${\frac{2t}{\pi} \nabla F( X_\theta ) \cdot X'_\theta}$ is normally distributed with standard deviation at most ${\frac{2t}{\pi}}$ . As such we have

$\displaystyle {\bf E} \exp( \frac{2t}{\pi} \nabla F( X_\theta ) \cdot X'_\theta ) \leq \exp( C t^2 )$

for some absolute constant ${C}$ ; integrating out the conditioning on ${X_\theta}$ we obtain the claim. $\Box$

Exercise 11 Show that Theorem 8 is equivalent to the inequality

$\displaystyle {\bf P}(X \in A) {\bf P}(X \not \in A_\lambda) \leq C \exp(-c \lambda^2)$

holding for all ${\lambda > 0}$ and all measurable sets ${A}$ , where ${X = (X_1,\ldots,X_n)}$ is an ${{\bf R}^n}$ -valued random variable with iid gaussian components ${X_1,\ldots,X_n \equiv N(0,1)_{\bf R}}$ , and ${A_\lambda}$ is the ${\lambda}$ -neighbourhood of ${A}$ .

Now we give a powerful concentration inequality of Talagrand, which we will rely heavily on later in this course.

Theorem 9 (Talagrand concentration inequality) Let ${K > 0}$ , and let ${X_1,\ldots,X_n}$ be independent complex variables with ${|X_i| \leq K}$ for all ${1 \leq i \leq n}$ . Let ${F: {\bf C}^n \rightarrow {\bf R}}$ be a ${1}$ -Lipschitz convex function (where we identify ${{\bf C}^n}$ with ${{\bf R}^{2n}}$ for the purposes of defining “Lipschitz” and “convex”). Then for any ${\lambda}$ one has

$\displaystyle {\bf P}( |F(X) - {\bf M} F(X)| \geq \lambda K ) \leq C \exp(-c \lambda^2 ) \ \ \ \ \ (18)$

and

$\displaystyle {\bf P}( |F(X) - {\bf E} F(X)| \geq \lambda K ) \leq C \exp(-c \lambda^2 ) \ \ \ \ \ (19)$

for some absolute constants ${C, c > 0}$ , where ${{\bf M} F(X)}$ is a median of ${F(X)}$ .

We now prove the theorem, following the remarkable argument of Talagrand.

By dividing through by ${K}$ we may normalise ${K=1}$ . ${X}$ now takes values in the convex set ${\Omega^n \subset {\bf C}^n}$ , where ${\Omega}$ is the unit disk in ${{\bf C}}$ . It will suffice to establish the inequality

$\displaystyle {\bf E} \exp( c d(X,A)^2 ) \leq \frac{1}{{\bf P}(X \in A) } \ \ \ \ \ (20)$

for any convex set ${A}$ in ${\Omega^n}$ and some absolute constant ${c>0}$ , where ${d(X,A)}$ is the Euclidean distance between ${X}$ and ${A}$ . Indeed, if one obtains this estimate, then one has

$\displaystyle {\bf P}( F(X) \leq x ) {\bf P}( F(X) \geq y ) \leq \exp( - c |x-y|^2 )$

for any ${y > x}$ (as can be seen by applying (20) to the convex set ${A := \{ z \in \Omega^n: F(z) \leq x \}}$ ). Applying this inequality of one of ${x,y}$ equal to the median ${{\bf M} F(X)}$ of ${F(X)}$ yields (18), which in turn implies that

$\displaystyle {\bf E} F(X) = {\bf M} F(X) + O( 1 ),$

which then gives (19).

We would like to establish (20) by induction on dimension ${n}$ . In the case when ${X_1,\ldots,X_n}$ are Bernoulli variables, this can be done; see this previous blog post. In the general case, it turns out that in order to close the induction properly, one must strengthen (20) by replacing the Euclidean distance ${d(X,A)}$ by an essentially larger quantity, which I will call the combinatorial distance ${d_c(X,A)}$ from ${X}$ to ${A}$ . For each vector ${z = (z_1,\ldots,z_n) \in {\bf C}^n}$ and ${\omega = (\omega_1,\ldots,\omega_n) \in \{0,1\}^n}$ , we say that ${\omega}$ supports ${z}$ if ${z_i}$ is non-zero only when ${\omega_i}$ is non-zero. Define the combinatorial support ${U_A(X)}$ of ${A}$ relative to ${X}$ to be all the vectors in ${\{0,1\}^n}$ that support at least one vector in ${A-X}$ . Define the combinatorial hull ${V_A(X)}$ of ${A}$ relative to ${X}$ to be the convex hull of ${U_A(X)}$ , and then define the combinatorial distance ${d_c(X,A)}$ to be the distance between ${V_A(X)}$ and the origin.

Lemma 10 (Combinatorial distance controls Euclidean distance) Let ${A}$ be a convex subset of ${\Omega^n}$ . ${d(X,A) \leq 2 d_c(X,A)}$ .

Proof: Suppose ${d_c(X,A) \leq r}$ . Then there exists a convex combination ${t = (t_1,\ldots,t_n)}$ of elements ${\omega \in U_A(X) \subset \{0,1\}^n}$ which has magnitude at most ${r}$ . For each such ${\omega \in U_A(X)}$ , we can find a vector ${z_\omega \in A-X}$ supported by ${\omega}$ . As ${A, X}$ both lie in ${\Omega^n}$ , every coefficient of ${z_\omega}$ has magnitude at most ${2}$ , and is thus bounded in magnitude by twice the corresponding coefficent of ${\omega}$ . If we then let ${z_t}$ be the convex combination of the ${z_\omega}$ indicated by ${t}$ , then the magnitude of each coefficient of ${z_t}$ is bounded by twice the corresponding coefficient of ${t}$ , and so ${|z_t| \leq 2r}$ . On the other hand, as ${A}$ is convex, ${z_t}$ lies in ${A-X}$ , and so ${d(X,A) \leq 2r}$ . The claim follows. $\Box$

Thus to show (20) it suffices (after a modification of the constant ${c}$ ) to show that

$\displaystyle {\bf E} \exp( c d_c(X,A)^2 ) \leq \frac{1}{{\bf P}(X \in A)}. \ \ \ \ \ (21)$

We first verify the one-dimensional case. In this case, ${d_c(X,A)}$ equals ${1}$ when ${X \not \in A}$ , and ${0}$ otherwise, and the claim follows from elementary calculus (for ${c}$ small enough).

Now suppose that ${n > 1}$ and the claim has already been proven for ${n-1}$ . We write ${X=(X',X_n)}$ , and let ${A_{X_n} := \{ z' \in \Omega^{n-1}: (z',X_n) \in A \}}$ be a slice of ${A}$ . We also let ${B := \{ z' \in \Omega^{n-1}: (z',t) \in A \hbox{ for some } t \in \Omega \}}$ . We have the following basic inequality:

Lemma 11 For any ${0 \leq \lambda \leq 1}$ , we have

$\displaystyle d_c(X,A)^2 \leq (1-\lambda)^2 + \lambda d_c(X',A_{X_n})^2 + (1-\lambda) d_c(X',B)^2.$

Proof: Observe that ${U_A(X)}$ contains both ${U_{A_{X_n}}(X') \times \{0\}}$ and ${(U_{B}(X') \backslash U_{A_{X_n}}(X')) \times \{1\}}$ , and so by convexity, ${V_A(X)}$ contains one of ${(\lambda t + (1-\lambda) u, 1-\lambda)}$ or ${(\lambda t + (1-\lambda) u, 0)}$ whenever ${t \in V_{A_{X_n}}(X')}$ and ${u \in V_{B}(X')}$ . The claim then follows from Pythagoras’ theorem and the Cauchy-Schwarz inequality. $\Box$

Let us now freeze ${X_n}$ and consider the conditional expectation

$\displaystyle {\bf E} (\exp( c d_c(X,A)^2 )|X_n).$

Using the above lemma (with some ${\lambda}$ depending on ${X_n}$ to be chosen later), we may bound the left-hand side of (21) by

$\displaystyle e^{c(1-\lambda)^2} {\bf E}((e^{c d_c(X',A_{X_n})})^\lambda (e^{c d_c(X',B)})^{1-\lambda}|X_n);$

applying Hölder’s inequality and the induction hypothesis (21), we can bound this by

$\displaystyle e^{c(1-\lambda)^2} \frac{1}{{\bf P}(X' \in A_{X_n}|X_n)^\lambda {\bf P}(X' \in B|X_n)^{1-\lambda}}$

which we can rearrange as

$\displaystyle \frac{1}{{\bf P}(X' \in B)} e^{c(1-\lambda)^2} r^{-\lambda}$

where ${r := {\bf P}(X' \in A_{X_n}|X_n) / {\bf P}(X' \in B)}$ (here we note that the event ${X' \in B}$ is independent of ${X_n}$ ). Note that ${0 \leq r \leq 1}$ . We then apply the elementary inequality

$\displaystyle \inf_{0 \leq \lambda \leq 1} e^{c(1-\lambda)^2} r^{-\lambda} \leq 2-r,$

which can be verified by elementary calculus if ${c}$ is small enough (in fact one can take ${c=1/4}$ ). We conclude that

$\displaystyle {\bf E} (\exp( c d_c(X,A)^2 )|X_n) \leq \frac{1}{{\bf P}(X' \in B)} ( 2 - \frac{{\bf P}(X' \in A_{X_n}|X_n)}{{\bf P}(X' \in B)} ).$

Taking expectations in ${n}$ we conclude that

$\displaystyle {\bf E} (\exp( c d_c(X,A)^2 )) \leq \frac{1}{{\bf P}(X' \in B)} ( 2 - \frac{{\bf P}(X \in A)}{{\bf P}(X' \in B)} ).$

Using the inequality ${x(2-x) \leq 1}$ with ${x := \frac{{\bf P}(X \in A)}{{\bf P}(X' \in B)}}$ we conclude (21) as desired.

The above argument was elementary, but rather “magical” in nature. Let us now give a somewhat different argument of Ledoux, based on log-Sobolev inequalities, which gives the upper tail bound

$\displaystyle {\bf P}( F(X) - {\bf E} F(X) \geq \lambda K ) \leq C \exp(-c \lambda^2 ), \ \ \ \ \ (22)$

but curiously does not give the lower tail bound. (The situation is not symmetric, due to the convexity hypothesis on ${F}$ .)

Once again we can normalise ${K=1}$ . By regularising ${F}$ we may assume that ${F}$ is smooth. The first step is to establish the following log-Sobolev inequality:

Lemma 12 (Log-Sobolev inequality) Let ${F: {\bf C}^n \rightarrow {\bf R}}$ be a smooth convex function. Then

$\displaystyle {\bf E} F(X) e^{F(X)} \leq ({\bf E} e^{F(X)}) (\log {\bf E} e^{F(X)}) + C {\bf E} e^{F(X)} |\nabla F(X)|^2$

for some absolute constant ${C}$ (independent of ${n}$ ).

Remark 5 If one sets ${f := e^{F/2}}$ and normalises ${{\bf E} f(X)^2=1}$ , this inequality becomes

$\displaystyle {\bf E} |f(X)|^2 \log |f(X)|^2 \leq 4C {\bf E} |\nabla f(X)|^2$

which more closely resembles the classical log-Sobolev inequality of Gross. The constant ${C}$ here can in fact be taken to be ${2}$ ; see Ledoux’s paper.

Proof: We first establish the ${1}$ -dimensional case. If we let ${Y}$ be an independent copy of ${X}$ , observe that the left-hand side can be rewritten as

$\displaystyle \frac{1}{2} {\bf E} ((F(X)-F(Y)) (e^{F(X)} - e^{F(Y)})) + ({\bf E} F(X)) (({\bf E} e^{F(X)}).$

From Jensen’s inequality, ${{\bf E} F(X) \leq \log {\bf E} e^{F(X)}}$ , so it will suffice to show that

$\displaystyle {\bf E} ((F(X)-F(Y)) (e^{F(X)} - e^{F(Y)})) \leq 2C {\bf E} e^{F(X)} |\nabla F(X)|^2.$

From convexity of ${F}$ (and hence of ${e^F}$ ) and the bounded nature of ${X,Y}$ , we have

$\displaystyle F(X)-F(Y) = O( |\nabla F(X)|)$

and

$\displaystyle e^{F(X)}-e^{F(Y)} = O( |\nabla F(X)| e^{F(X)})$

when ${F(X) \geq F(Y)}$ , which leads to

$\displaystyle ((F(X)-F(Y)) (e^{F(X)} - e^{F(Y)})) = O( e^{F(X)} |\nabla F(X)|^2 )$

in this case. Similarly when ${F(X) < F(Y)}$ (swapping ${X}$ and ${Y}$ ). The claim follows.

To show the general case, we induct on ${n}$ (keeping care to ensure that the constant ${C}$ does not change in this induction process). Write ${X = (X',X_n)}$ , where ${X' := (X_1,\ldots,X_{n-1})}$ . From induction hypothesis, we have

$\displaystyle {\bf E}(F(X) e^{F(X)}|X_n) \leq f(X_n) e^{f(X_n)} + C {\bf E}(e^{F(X)} |\nabla' F(X)|^2|X_n)$

where ${\nabla'}$ is the ${n-1}$ -dimensional gradient and ${f(X_n) := \log {\bf E}(e^{F(X)}|X_n)}$ . Taking expectations, we conclude that

$\displaystyle {\bf E} F(X) e^{F(X)} \leq {\bf E} f(X_n) e^{f(X_n)} + C {\bf E} e^{F(X)} |\nabla' F(X)|^2. \ \ \ \ \ (23)$

From the convexity of ${F}$ and Hölder’s inequality we see that ${f}$ is also convex, and ${{\bf E} e^{f(X_n)} = {\bf E} e^{F(X)}}$ . By the ${n=1}$ case already established, we have

$\displaystyle {\bf E} f(X_n) e^{f(X_n)} \leq ({\bf E} e^{F(X)}) (\log {\bf E} e^{F(X)}) + C {\bf E} e^{f(X_n)} |f'(X_n)|^2. \ \ \ \ \ (24)$

Now, by the chain rule

$\displaystyle e^{f(X_n)} |f'(X_n)|^2 = e^{-f(X_n)} | {\bf E}(e^{F(X)} F_{x_n}(X)|X_n)|^2$

where ${F_{x_n}}$ is the derivative of ${F}$ in the ${x_n}$ direction. Applying Cauchy-Schwarz, we conclude

$\displaystyle e^{f(X_n)} |f'(X_n)|^2 \leq {\bf E}(e^{F(X)} |F_{x_n}(X)|^2|X_n).$

Inserting this into (23), (24) we close the induction. $\Box$

Now let ${F}$ be convex and ${1}$ -Lipschitz. Applying the above lemma to ${tF}$ for any ${t>0}$ , we conclude that

$\displaystyle {\bf E} tF(X) e^{tF(X)} \leq ({\bf E} e^{tF(X)}) (\log {\bf E} e^{tF(X)}) + C t^2 {\bf E} e^{tF(X)};$

setting ${H(t) := {\bf E} e^{tF(X)}}$ , we can rewrite this as a differential inequality

$\displaystyle t H'(t) \leq H(t) \log H(t) + C t^2 H(t)$

which we can rewrite as

$\displaystyle \frac{d}{dt} (\frac{1}{t} \log H(t) ) \leq C.$

From Taylor expansion we see that

$\displaystyle \frac{1}{t} \log H(t) \rightarrow {\bf E} F(X)$

as ${t \rightarrow 0}$ , and thus

$\displaystyle \frac{1}{t} \log H(t) \leq {\bf E} F(X) + Ct$

for any ${t>0}$ . In other words,

$\displaystyle {\bf E} e^{tF(X)} \leq \exp( t {\bf E} F(X) + C t^2 ).$

By Markov’s inequality, we conclude that

$\displaystyle {\bf P}( F(X) - {\bf E} F(X) > \lambda ) \leq \exp( Ct^2 - t \lambda);$

optimising in ${t}$ gives (22).

Remark 6 The same argument, starting with Gross’s log-Sobolev inequality for the gaussian measure, gives the upper tail component of Theorem 8, with no convexity hypothesis on ${F}$ . The situation is now symmetric with respect to reflections ${F \mapsto -F}$ , and so one obtains the lower tail component as well. The method of obtaining concentration inequalities from log-Sobolev inequalities (or related inequalities, such as Poincaré-type ienqualities) by combining the latter with the exponential moment method is known as Herbst’s argument, and can be used to establish a number of other functional inequalities of interest.

We now close with a simple corollary of the Talagrand concentration inequality, which will be extremely useful in the sequel.

Corollary 13 (Distance between random vector and a subspace) Let ${X_1,\ldots,X_n}$ be independent complex-valued random variables with mean zero and variance ${1}$ , and bounded almost surely in magnitude by ${K}$ . Let ${V}$ be a subspace of ${{\bf C}^n}$ of dimension ${d}$ . Then for any ${\lambda > 0}$ , one has

$\displaystyle {\bf P}( |d(X,V) - \sqrt{n-d}| \geq \lambda K ) \leq C \exp( - c \lambda^2 )$

for some absolute constants ${C, c > 0}$ .

Informally, this corollary asserts that the distance between a random vector ${X}$ and an arbitrary subspace ${V}$ is typically equal to ${\sqrt{n - \hbox{dim}(V)} + O(1)}$ .

Proof: The function ${z \mapsto d(z,V)}$ is convex and ${1}$ -Lipschitz. From Theorem 9, one has

$\displaystyle {\bf P}( |d(X,V) - M d(X,V)| \geq \lambda K ) \leq C \exp(-c \lambda^2 ).$

To finish the argument, it then suffices to show that

$\displaystyle M d(X,V) = \sqrt{n-d} + O( K ).$

We begin with a second moment calculation. Observe that

$\displaystyle d(X,V)^2 = \| \pi(X) \|^2 = \sum_{1 \leq i,j \leq n} p_{ij} X_i \overline{X_j},$

where ${\pi}$ is the orthogonal projection matrix to the complement ${V^\perp}$ of ${V}$ , and ${p_{ij}}$ are the components of ${\pi}$ . Taking expectations, we obtain

$\displaystyle {\bf E} d(X,V)^2 = \sum_{i=1}^n p_{ii} = \hbox{tr}(\pi) = n-d \ \ \ \ \ (25)$

where the latter follows by representing ${\pi}$ in terms of an orthonormal basis of ${V^\perp}$ . This is close to what we need, but to finish the task we need to obtain some concentration of ${d(X,V)^2}$ around its mean. For this, we write

$\displaystyle d(X,V)^2 - {\bf E} d(X,V)^2 = \sum_{1 \leq i,j \leq n} p_{ij} (X_i \overline{X_j} - \delta_{ij})$

where ${\delta_{ij}}$ is the Kronecker delta. The summands here are pairwise uncorrelated for ${1 \leq i \leq j \leq n}$ , and the ${i>j}$ cases can be combined with the ${i<j}$ cases by symmetry. Each summand also has a variance of ${O( K^2 )}$ . We thus have the variance bound

$\displaystyle {\bf Var}( d(X,V)^2 ) = O( K^2 \sum_{1 \leq i,j \leq n} |p_{ij}|^2 ) = O( K^2 (n-d) ),$

where the latter bound comes from representing ${\pi}$ in terms of an orthonormal basis of ${V^\perp}$ . From this, (25), and Chebyshev’s inequality, we see that the median of ${d(X,V)^2}$ is equal to ${n-d + O( \sqrt{K^2 (n-d)} )}$ , which implies on taking square roots that the median of ${d(X,V)}$ is ${\sqrt{n-d} + O(K)}$ , as desired. $\Box$

116 comments

Comments feed for this article

4 January, 2010 at 1:40 pm

Michael Lugo

I’m enjoying these notes. I just want to point out a technical issue. This post, and also the post Notes 0, did not appear in Google Reader, although Notes 0a does appear there, and all three posts (0, 0a, 1) appear if I go directly to https://terrytao.wordpress.com/feed/.

I don’t know what’s causing this (and the problem may be my fault, or Google’s), but I thought I’d mention this here in case other people have the same issue.

4 January, 2010 at 10:58 pm

harrison

Google Reader’s doing the same for me. It doesn’t seem like an uncommon bug — for instance, looking at my feed to Tim Gowers’ blog it doesn’t list the post on Littlewood’s conjecture. Two dropped posts in three days does seem high, though.

7 January, 2010 at 8:19 am

Jason Rute

The trouble seems to be something in the content item of the feed (the item containing the full HTML of the post). Using Yahoo Pipes, I created a copy of the feed for this blog and removed the content item. It seems to work fine in Google Reader. The RSS feed is here:

http://pipes.yahoo.com/pipes/pipe.run?_id=ec21ff6b5d982e2f244ca9fd7d10dfac&_render=rss

and the Yahoo Pipe (which I made public) is here:

http://pipes.yahoo.com/pipes/pipe.info?_id=ec21ff6b5d982e2f244ca9fd7d10dfac

Note that you will have to read the article in WordPress rather than in Google Reader.

4 January, 2010 at 8:48 pm

Kelly

Aloha Terry,

I am new to this blog and quite blown away by the sheer amount of fascinating math topics here… Just wondering- how long does it normally take to put these notes together? You don’t seem to sleep!

5 January, 2010 at 1:03 am

Anonymous

Dear Prof. Tao,

I enjoyed this yet another excellent post.

A remark – theorems 4 and 5 seem to be phrased identically – probably a copy-paste typo.

[Corrected, thanks – T.]

5 January, 2010 at 3:59 pm

mmailliw/william

The improved bound you want us to establish in Exercise 3,
(lambda K/sigma)^(-c lambda sigma), is not scale-invariant; if you multiply the X_i by a constant A, then the K, mu_i, sigma_i, mu, and sigma (and therefore the LHS of the desired inequality) remains unchanged.

However, the term (lambda K/sigma)^(-c lambda sigma) is raised to the power of A (as lambda K/sigma is unchanged but -c lambda sigma is multiplied by A).

Am I missing something here, and if not, should the bound be changed to something which is invariant under such scaling?

5 January, 2010 at 4:25 pm

Terence Tao

Ah, the exponent should be $c \lambda \sigma/ K$ instead. I’ve changed this accordingly.

6 January, 2010 at 1:25 am

Arnab

Dear Prof. Tao,
Such wonderful notes!

In Corollary 13, I think when you did the variance bound of d(X, V)^2,
you mean the summand are ‘pairwise uncorrelated’ instead of ‘pairwise independent’?

[Well, either would work here, so I reworded the text accordingly. -T.]

6 January, 2010 at 5:24 am

Akito Nagasaki

Dear Professor Tao,

Inequality(1) seems not always true!
Pick up a r.v. X taking 1 with probability 1/8, -1 with 1/8 and 0 with 3/4
and Y a copy of X but independent one.
Then P(X+Y not equal to zero) = 38/64 and P(X not equal to zero) +
P(Y not equal to zero)=1/2 ??

6 January, 2010 at 12:06 pm

Terence Tao

I think you may have double-counted some of the probabilities here; my computations show that X+Y is non-zero with probability 26/64.

The proof of the inequality is quite simple in this case, because the event that X+Y is nonzero is clearly contained in the union of the events that X is nonzero and Y is nonzero, thus the probability of the former is at most the sum of the probabilities of the latter.

6 January, 2010 at 10:32 am

John Sidles

For a seminar our UW QSE Group is giving this quarter, So you want to be a quantum system engineer, it would be *very* helpful to have a generalized version of Corollary 13, in which $V$ is not a linear subspace, but rather a rank- $r$ join space of spin- $j$ product states of order- $m$ .

Physicists would call $V$ a restriction of spin- $j$ order- $m$ matrix product states (MPS) to states whose matrices are diagonal of Schmidt rank $r$ … the physical point being that $r$ then bounds the Schmidt rank of all of the $2^(m-1)$ state-space bipartitions. MPS’s like $V$ are natural in general-purpose quantum simulation precisely because they have (due to their diagonal restriction) no natural ordering among the spins.

Since we engineers are going to be exploring Corollary 13 in large dimensions numerically, it would be useful for us to know (in advance) whether we might simply replace $d \to f(j,m,r)$ for some specified function $f$ .

Might $d \to f(j,n,r) =?= (2jm+1)r$ … as follows if we approximate $V$ as a linear subspace? Here we welcome all the mathematical guidance we can get, from *any* reader(s) of this weblog!

And please accept also our apology, in advance, should it happen that the function $f(j,m,r)$ is well-known, or obvious (or the latex of this post doesn’t render properly).

6 January, 2010 at 11:59 am

254A, Notes 2: The central limit theorem « What’s new

[…] the previous set of notes, we were able to establish various tail bounds on . For instance, from Chebyshev’s inequality […]

6 January, 2010 at 5:49 pm

Pietro Poggi-Corradini

The display after “Applying (10), we conclude that” in the proof of McDiarmids Inequality seems to be missing a less-or-equal sign.

[Corrected, thanks – T.]

7 January, 2010 at 2:01 am

arno

Hi!
nice entry… some comments:
– the way to derive concentration from logarithmic Sobolev inequality is called Herbst’s argument as you surely know… and as the same technique may be applied (with technical details) to other functional inequalities… you should perhaps mention it…
– Mc Diarmid’s method, as well as Hoeffding’s inequality, may be considered in the larger framework of transportation’s inequality as studied initially By Marton and also Talagrand, and a very elegant way to derive concentration property… Mc Diarmid’s being then a way to tensorize these inequalities… however, it perhaps implies to consider other quantities (such as wasserstein’s distance) that you do not want to use here…

best regards

[Good suggestions, thanks – T.]

7 January, 2010 at 3:08 am

karabasov

The link to “divide and conquer argument” right before Theorem 4 is not working

[Fixed, thanks – T.]

9 January, 2010 at 12:02 pm

254A, Notes 3: The operator norm of a random matrix « What’s new

[…] bounding can be viewed as a non-commutative analogue of upper bounding the quantity studied in Notes 1. (The analogue of the central limit theorem in Notes 2 is the Wigner semi-circular law, which will […]

10 January, 2010 at 8:54 am

Anonymous

in equation $(3),$ there is an extra ${\bf E}$

[Corrected, thanks – T.]

10 January, 2010 at 9:08 am

Anonymous

in Theorem 2, $(11)$ on the right hand side, we are taking maximum but I do not see with respect to which variable the max is taken.

10 January, 2010 at 9:14 am

Terence Tao

max(x,y) is simply the larger of the two quantities x and y.

10 January, 2010 at 9:18 am

Anonymous

in exercise $(2)$ , is it $\leq$ or $\geq$ ?

10 January, 2010 at 9:25 am

Terence Tao

It is $\geq$ . The idea here is to show that Stirling’s formula can be used to provide a lower bound to complement the upper bounds proven in the text.

10 January, 2010 at 9:34 am

Anonymous

I see. Thanks Prof. Tao

10 January, 2010 at 11:46 am

Steven Heilman

some pedantic typos/details:

1.”gives a crude upper bound on[sic] when”

2. Hoeffding’s inequality (exercise 4): P not E

3. I suppose it’s no coincidence that Theorems 2,3 are (essentially) the crux of the proof of Khintchine’s inequality (on the unit interval). Kahane’s inequality even can be dealt with using “exponential-type” estimates of a distribution function, though the argument I know is more combinatorial (and perhaps “more basic”) in nature.

4(a). [inconsequential detail] proof of theorem 8, first use of Jensen’s,
some pi/2’s (and 2/pi’s) need to be inverted? e.g.

\displaystyle \exp( t (f(X) – f(Y))) \leq \frac{2}{\pi} \int_0^{\pi/2} \exp( \frac{\pi t}{2} \frac{d}{d\theta} f( X_\theta ) )\ d\theta.

etc.

4(b). f should be F

4(c). final bound should be exp(Ct^2)?
(Laplace transform of Gaussian is, essentially, a Gaussian)?

5. definition of combinatorial support: “to be the[sic] all”

6. final equation: errant E on the left, errant \leq in the middle

[Thanks for the corrections! Yes, Khintchine’s inequality can be viewed as part of the family of large deviation inequalities proven by the exponential moment method; I’ve added a remark to this effect -T.]

18 January, 2010 at 6:29 pm

254A, Notes 3b: Brownian motion and Dyson Brownian motion « What’s new

[…] all , then one easily verifies (using Exercise 9 of Notes 1) that is a Wiener […]

21 January, 2010 at 6:24 pm

Sean

At the risk of everyone saying “Oh no, not this guy again” are you aware of my idea of combining the Walsh Hadamard transform and randomly selected permutations to transform arbitrary numerical data into data with a Gaussian distribution? Basically it maps one point on a hypersphere to another random point on the hypersphere. The mapping is reversible. If you look up how to pick a point uniformly at random on the surface of a hypersphere you will see that one method involves random numbers with a Gaussian distribution.
I only do informal hobby research but I hope that is useful.
http://code.google.com/p/lemontree/downloads/list

Sean O’Connor

23 January, 2010 at 11:05 am

Anonymous

In the comment following equation (8) it seems that that statement “so we may assume that $\lambda$ is large compared to this quantity”, should read “\lambda” is small compared to this quantity” (otherwise we have the null statement $|S_n| >>n$)

Best

[Thanks – T.]

26 January, 2010 at 8:06 am

Anonymous

Can someone please post the solution to exercise 11.

2 February, 2010 at 1:34 pm

254A, Notes 4: The semi-circular law « What’s new

[…] As will hopefully become clearer in the next set of notes, the semi-circular law is the noncommutative (or free probability) analogue of the central limit theorem, with the semi-circular distribution (1) taking on the role of the normal distribution. Of course, there is a striking difference between the two distributions, in that the former is compactly supported while the latter is merely subgaussian. One reason for this is that the concentration of measure phenomenon is more powerful in the case of ESDs of Wigner matrices than it is for averages of iid variables; compare the concentration of measure results in Notes 3 with those in Notes 1. […]

10 February, 2010 at 9:16 am

PDEbeginner

Dear Prof. Tao,

I finished reading this chapter. I had some problems:

1. In the proof of the strong LLN, if we choose $N_m=n_m$ , I didn’t see why $\sum \frac{1}{n_m} E|X_{\leq N_m}|^2<\infty$ since we only assume the first order moment for $X$ .

2. In Ex 7, I can get the bounds $\exp\{-c_A n^{p/2}\}$ .

10 February, 2010 at 9:23 am

Terence Tao

1. This follows from the pointwise bound $\sum_m \frac{1}{n_m} |X_{\leq n_m}|^2 \leq C |X|$ which ultimately comes from the lacunary nature of the $n_m$ .

2. Hmm, that’s strange, because one should get exponential bounds when p >= 1. (For instance, when p=1, one can use the fact that E exp(cX) is bounded for small c to get exponential bounds, see e.g. Lemma 1 of Notes 3.) It may be that your choice of parameters is not fully optimal.

10 February, 2010 at 3:06 pm

PDEbeginner

Thanks!

I understood 2, but still have some problem for 1: the constant $C$ should depend on the sample $\omega$ , $E C|X|=\infty$ is possible. To apply Borel-Cantelli Lemma, we need the expectation to be strictly less than $\infty$ .

10 February, 2010 at 3:19 pm

Terence Tao

The constant C is uniform. This is because the expression $\sum_m \frac{1}{n_m} |X_{\leq n_m}| = |X| \sum_{m: n_m \geq |X|} \frac{1}{n_m}$ is uniformly bounded (e.g. if the $n_m$ are powers of 2, then this quantity is always bounded by 2, by the geometric series formula.)

10 February, 2010 at 10:56 pm

245A, Notes 5: Free probability « What’s new

[…] probability, though if free probability is combined with tools such as concentration of measure (Notes 1) then such rate information can often be recovered. For similar reasons, free probability lets one […]

19 February, 2010 at 4:30 am

Anonymous

Dear Prof Tao,

thanks for these very nice lectures.
Shouldn’t \sigma^2 be a \sigma in McDiarmid’s inequality ?

[Corrected, thanks – T.]

5 March, 2010 at 1:47 pm

254A, Notes 7: The least singular value « What’s new

[…] Talagrand’s inequality (Notes 1), we expect each to be of size on the average, which suggests that ; this is consistent with the […]

16 April, 2010 at 7:00 am

Anonymous

Suppose one weakens the hypotheses of the above concentration of measure results, e.g.,by removing the assumption of finite mean and variance, or by weakening independence assumptions. It seems that such weaker assumptions are needed in certain interesting applications, such as financial modelling. Is there still some sort of universal behavior, such as convergence in distribution to some universal “fat tailed” distribution, that reasonable combinations of such random variables exhibit?

17 April, 2010 at 11:44 pm

Terence Tao

I believe the theory of stable laws addresses these sorts of issues.

18 April, 2010 at 9:55 am

Anonymous

Thanks for the reference.

3 May, 2010 at 8:10 am

Anonymous

In Exercise 11, I got the proof for one direction, but do not know how to prove that the statement in Exercise 11 implies Theorem 8. Could you give a relatively detailed hint?

by the way, one of the “dt” in the proof of Theorem 8 should be replaced with “d\theta”

3 May, 2010 at 8:19 am

Terence Tao

Thanks for the correction!

To get Theorem 8 from Exercise 11, first prove a variant of Theorem 8 in which the expectation is replaced by the median. To prove that variant, argue by contradiction and look at various level sets of F.

3 May, 2010 at 11:23 am

Anonymous

Would it be right to say that Azuma’s inequality is already present in Hoeffding’s 1963 paper (see top of page 18 there), ditto for McDiarmid’s inequality?

3 May, 2010 at 12:51 pm

Terence Tao

Yes, the attribution here can become somewhat complicated; for instance, one can make the case that Hoeffding’s inequality, Azuma’s inequality, and McDiarmid’s inequality were all implicitly present in the work of Bernstein several decades earlier (and are not far off from the work of Chernoff either). Certainly I have seen Azuma’s inequality, for instance, referred to instead as the Azuma-Hoeffding inequality.

Assigning attribution to a result is not a completely precise science; one has to draw the line somewhere between speculating that the result is true, asserting the result without proof, giving a nearly complete sketch, implicitly stating and proving the result en route to some other goal, giving the proof with full details, to giving applications and popularising the result (for instance by explicitly stating it as the main theorem of a paper). At a more practical level, it is also a matter of what name has taken hold in the community (it is unlikely, for instance, that L’Hopital’s rule or Stokes’ theorem will ever be renamed after their original discoverers); currently Azuma’s inequality seems to have a slight edge over Azuma-Hoeffding, though both are acceptable in my view.

See also “Stigler’s law of eponymy“.

3 May, 2010 at 10:58 pm

Anonymous

Dear Professor Tao,

Is the convex function requirement for the function F necessary? (In the Talagrand concentration inequality and also in the Log-Solobev inequality?)

Thanks.

4 May, 2010 at 7:47 am

Terence Tao

The condition for convexity can be relaxed somewhat, but I believe there are counterexamples to show that it cannot be dispensed with entirely. Ledoux’s book will surely have a thorough discussion of this issue.

30 November, 2011 at 8:40 am

Terence Tao

I’m belatedly returning to this question to record a concrete counterexample. On $\{0,1\}^n$ , consider the function $F(x) := \max( \min( |x|, n/2 + \sqrt{n} ), n/2 - \sqrt{n} ) / n^{1/4}$ , where $|x| := |x_1| + \ldots + |x_n|$ is the l^1 (or Hamming) norm. This is O(1)-Lipschitz on $\{0,1\}^n$ , and can thus be extended (in a non-convex manner) to a O(1)-Lipschitz function on ${\bf R}^n$ , but concentrates at scale $O(n^{1/4})$ rather than at scale O(1).

2 December, 2011 at 11:43 am

Nick Cook

Do you want to swap the order of max and min there? I am also not seeing that it is 1-Lipschitz (wrt Euclidean distance). I get $|F(x)-F(y)|\le ||x|-|y||/n^{1/4}\le |x-y|/n^{1/4}\le \sqrt{n}|x-y|_E/n^{1/4}$ , and all of these are sharp, getting a Lipschitz constant of $n^{1/4}$ , consistent with the scale of concentration.

2 December, 2011 at 11:47 am

Nick Cook

this reply is so nested the last inequality disappeared! $|x-y|/n^{1/4}\le \sqrt{n}|x-y|_E/n^{1/4}$

2 December, 2011 at 12:45 pm

Terence Tao

Thanks for the correction! To establish the Lipschitz property, note that F only has a range of $O(n^{1/4})$ , so it suffices to verify the Lipschitz claim when $|x-y|_E = O(n^{1/4})$ , which on the unit cube then gives $|x-y|_{\ell^1} = |x-y|_E^2 \ll n^{1/4} |x-y|_E$ . F has a Lipschitz constant of $n^{-1/4}$ wrt the $\ell^1$ norm, and hence of norm $O(1)$ wrt the Euclidean norm.

2 December, 2011 at 1:24 pm

Nick Cook

Ah right, I see now how my inequalities forget the range of $F$ . Thanks!

11 January, 2012 at 12:49 pm

Nick Cook

Ledoux’s example is also on $\{0,1\}^n$ . Let $n$ even and let $A$ be the “hereditary” set $\{y:\sum y_i\le n/2\}$ (such sets $\{y:\sum y_i\le \epsilon \}$ are extremal in the sense of isoperimetry for the Hamming metric on the discrete cube). Let $F(x)=d(x,A)$ be the Euclidean distance from $x\in {\bf R}^n$ to $A$ . $F$ is 1-Lipschitz but not convex.

Now let $P$ be the uniform product measure on $\{0,1\}^n$ and consider the subset $B_\delta = \{x: \sum x_i - n/2\ge \delta\sqrt{n} \}$ with $\delta$ to be chosen later. Then for any $x\in B_\delta \subset \{0,1\}^n$ and any $y\in A$ , $\delta\sqrt{n}\le \sum x_i-n/2 \le \sum (x_i-y_i) \le \sum |x_i-y_i|^2$ , so that $B_\delta\subset \{d(x,A)\ge\sqrt{\delta}n^{1/4}\}$ . Hence, $P(\{F(x)\ge\sqrt{\delta}n^{1/4}\})\ge P(\{\frac{\sum x_i - n/2}{\sqrt{n}}\ge \delta\}) \ge 1/10$ for $\delta$ sufficiently small independent of $n$ , by the Central Limit theorem (or just Stirling’s formula).

28 August, 2010 at 1:58 am

Anonymous

Dear Prof. Tao

I have a question about Gaussian Concentration Inequality for Lipschitz Function.

Let $F_i=\frac{\sum_{i=1}^{n}z_{ij}^2}{\sqrt n}(i=1,\ldots,m)$ , where $z_{ij}\sim N(0,1)(j=1,\ldots,n)$ are iid real Gaussian variables. We have already known $F_i^2\sim\frac{\chi_n^2}{n}(i=1,\ldots,m)$ and can prove $F_i$ is Lipschitz Function with Lipschitz Constant $\frac{1}{\sqrt n}$ .

According to the proof of Theorem 8, we can get
$E\exp(\frac{\pi t}{2}\nabla F_i(X_\theta)\cdot X'_\theta)\leq\exp(\frac{\pi^2 t^2}{8n})$ ,
then
$P(F_i-EF_i\geq\lambda)\leq \exp(\frac{\pi^2 t^2}{8n}-t\lambda)$ .
Optimising in t , we have
$P(F_i-EF_i\geq\lambda)\leq \exp(-\frac{2n\lambda^2}{\pi^2})$ .
Since
$EF_i=\frac{\sqrt2\Gamma(\frac{n+1}{2})}{\sqrt n\Gamma(\frac{n}{2})}$ ,
we can get
$P(F_i\geq\frac{\sqrt2\Gamma(\frac{n+1}{2})}{\sqrt n\Gamma(\frac{n}{2})}+\lambda)\leq\exp(-\frac{2n\lambda^2}{\pi^2})$ ,
then
$P(\max_i F_i\geq\frac{\sqrt2\Gamma(\frac{n+1}{2})}{\sqrt n\Gamma(\frac{n}{2})}+\lambda)\leq m\exp(-\frac{2n\lambda^2}{\pi^2})$ .

Above mentioned are what I can get by Theorem 8. But I have saw a result that one can get
$P(\max_i F_i\geq1+\lambda)\leq \exp(-\frac{n\lambda^2}{2})$
by Gaussian Concentration. Can we get this result in your opinion? If your answer is YES. Can you tell me why? Some hints will be OK.

31 August, 2010 at 12:07 am

Anonymous

I met this question when read one of Donoho’s papers.

http://www-stat.stanford.edu/~donoho/Reports/2004/l1l0EquivCorrected.pdf

It seems that the question which has haunted me nearly a week has not yet been settled. Is it so difficult?

30 August, 2010 at 1:07 am

Anonymous

Dear Prof. Tao
I hope I can have your advice about the question mentioned in above comment. Your experience will be important to a student interested in Concentration of Measure.

13 October, 2010 at 6:51 am

Camilo Chaparro

Prof. Tao. I’m doing a research about matrices and measure theory. Can you send me directions or websites where I can find information about those topics? Thanks a lot.

26 January, 2011 at 5:16 pm

yucao

Dear Prof. Tao,

I cannot fully understand what a “sharp” inequality EXACTLY mean here. I read your post on Google buzz about sharp estimate. And there is another passage on Wikipedia which mentions the mathematical jargon “sharp”. By I get confused when I try to give examples. Like “ $(a+b)^2\geq 0$ is sharp” but “ $(a+b)^2\geq -1$ is not sharp”? What about $a^2+b^2\geq 2ab$ and $a^2+b^2\geq ab (a\geq 0,b\geq 0)$ ? In the finite dimension space, one has $\|a\|_14\leq\|a\|_6$ where $a\in {\Bbb R}^n$ . But as long as $6<p<14$ , one has $\|a\|_14\leq\|a\|_p\leq \|a\|_6$ . So $\|a\|_14\leq\|a\|_6$ is not sharp?

You mentioned in your Google buzz that "These are exact inequalities such as X <= Y without any unspecified constants or error terms (or X <= CY with an extremely explicit C, typically involving special constants such as pi or e). " It seems that this is only a issue about the constant C. (Even when one has X<=Z<=Y, X<=Y can still be sharp?)

27 January, 2011 at 1:50 am

Terence Tao

There are varying degrees of sharpness. An inequality $X \leq Y$ is usually considered (exactly) sharp if $X$ can be equal to $Y$ in some non-trivial cases. (The more non-trivial cases for which equality is nearly attained, the sharper the inequality becomes; thus equalities $X = Y$ are the sharpest inequalities of all.) A weaker notion of sharpness than exact sharpness is sharpness up to constants: $X \leq CY$ is sharp up to constants if one has $X \geq cY$ in non-trivial cases. One can also have sharpness up to logarithms, sharpness up to epsilon factors in the exponents, etc.

One can also consider sharpness in various exponent parameters; if an estimate holds for all exponents p in a certain range, and that range is best possible in that the estimate breaks down outside that range, then the endpoints of that range are considered sharp exponents for the inequality.

29 January, 2011 at 6:01 pm

Pan

Dear Professor:

I have a question about Sobolev Spaces. Suppose there exists a sequence of functions u_n is bounded in W^{2,\infty}. Then we know, by compactness, there exists a subsequence u_k which weakly converges to a function u in W^{2,\infty}. But is that possible that the 1st derivative of u_k converges weakly to the 1st derivative of u? As well as the 2nd derivative of u_k?

Thank you very much professor!

11 February, 2011 at 12:31 pm

Meng

Dear Prof. Tao,

I have a question about the decay rate of the sum of i.i.d. random variables.

If x_i are i.i.d. N(0,1), S_n =\sum_i |x_i|. What is the sharpest bound of

P(|S_n-nE[|x_i|]|>cn) for ANY c>0?

Could I apply Proposition 6? It requires |x_i| to be subgaussian, and c sufficiently large though. Can I use it here?

Thank you!

13 April, 2011 at 1:37 am

Xiaodong

Dear Prof. Tao,

I have a question about Theorem 8 and 9. Do we have a similar result for the concentration of the 1-Lipschitz function when the probability space is a sub-Gaussian product measure.

26 October, 2011 at 7:59 am

Anthony Quas

Hi Terry,

In the introductory section, I guess you mean one is *within* $O(\log^{\frac12}n)$ standard deviations with high probability and *within* $O(\log^{\frac12+\epsilon}n)$ standard deviations with overwhelming probability.

26 October, 2011 at 8:10 am

Terence Tao

Yes, this is correct. With my conventions for O() notation, a quantity which is $O(X)$ has an upper bound by a constant times X, but does not necessarily have a lower bound. (I occasionally use $\Theta(X)$ for a quantity which has both an upper and lower bound, though nowadays I prefer to avoid using such notation as it is not as widely understood as the O() notation.)

27 October, 2014 at 4:26 am

Martin Scorsese

Concerning your comment from the 26 October, 2011 at 8:10 am: The way you defined asymptotic notation in the first Definition from “Notes 0”, is contradictory to your comment, I believe: Here you define “$Z$ is $O(X)$” if $Z\leq CX$, but in the first definition a lower bound is also provided: $|Z|\leq CX$.

27 October, 2014 at 9:09 am

Terence Tao

In my comment, I was referring to a lower bound of the form $Z > cX$ (or $|Z| > cX$ , if Z is signed) for some strictly positive constant c (such a lower bound is assumed in some variants of the O() notation that one occasionally sees in the literature).

30 December, 2011 at 11:31 am

Raj

Dear Prof. Tao,

Consider the function

$f(z) = 1/( u^{H} (zI – X_n)^{-2} u)

where u is a n x 1 unit norm vector with uniform distribution on the sphere and X is an independent random diagonal matrix with real eigenvalues \lambda_{1}, \lambda_{n}. Assume that the spectral measure on the eigenvalues on X_n converges almost surely as n-> to a non-random measure \mu_X that is compactly supported on [a,b].

For arbitrary z \in [a,b],, it seems that f(z) – a.s. -> 0 because the numerator of u^{H} (zI – X_n)^{-2} u is O(1/n) while the denominator is O(1/n^2).

What would be the easiest way to make the above argument rigorous? Can one do so without requiring any level repulsion type assumption on the eigenvalues of X_n?

I’ve enjoyed reading your notes and the elegance of your presentations.

Thanks,

Raj

10 February, 2012 at 9:07 am

Michael

Dear Prof. Tao,

I enjoyed your excellent post.
However, I did not find anything about Khinchine-Kahane or Khinchine inequalities I am also interested in. Please, lead me to your posts or give me an advise for a good book.

Thank you very much.

4 May, 2012 at 12:22 pm

Nick Cook

I think the line under equation (24) should have conditioning on $X_n$ : $e^{f(X_n)}|f'(X_n)|^2=e^{-f(X_n)}|{\bf E}(e^{F(X)}F_{x_n}(X)|X_n)|^2$ . It is to this conditional expectation we apply Cauchy-Schwarz. Then we can take expectations and need an ${\bf E}$ on the left hand side of the next line: ${\bf E}e^{f(X_n)}|f'(X_n)|^2\le {\bf E}e^{F(X)}|F_{x_n}(X)|^2$ .

[Corrected, thanks – T.]

3 July, 2012 at 1:02 am

Ahriman

Dear Prof. Tao,

I don’t understand fully your proof of the McDiarmid’s inequality.
How do you show that $tY$ fluctuates by $tc_n$ for latex $X_1, …, X_n$ fixed, and then, how do you apply (10), which says nothing about conditionnal expectations ?

Maybe I’m not familiar enough with conditional expectations …

Thank you very much,
Ahriman.

3 July, 2012 at 7:47 am

Terence Tao

If $X_1,\ldots,X_{n-1}$ are fixed, then ${\bf E}(F(X)|X_1,\ldots,X_n)$ is deterministic (i.e. it is just a scalar constant, rather than a random variable), and by hypothesis $F(X)$ only fluctuates by $c_n$ , so $Y$ does also. One then applies (10) to the random variable Y (which is a random variable in the conditioned probability space arising after fixing $X_1,\ldots,X_{n-1}$ ).

4 July, 2012 at 8:29 am

Ahriman

I think the problem comes from the fact that I don’t understand what “ $X_1, ..., X_{n-1}$ are fixed” means.
I don’t see also why $F_{n-1}$ satisfies the same hypotheses as $F$ .

4 July, 2012 at 8:50 am

Terence Tao

Conditional expectation is discussed in Section 4 of Notes 0. If one is unfamiliar with conditional expectation, it is probably best to begin with the discrete case, when all the X_i are discrete random variables. In this case, fixing the X_i means selecting deterministic elements $x_1,...,x_{n-1}$ of $R_1,...,R_{n-1}$ and working with conditional expectations such as $F_{n-1}(x_1,\ldots,x_n) := E(F(X)|X_1=x_1,...,X_{n-1}=x_{n-1})$ , which (by the independence) is also equal to $E( F(x_1,\ldots,x_{n-1},X_n) )$ ; the random variable Y then has the distribution of $F(x_1,\ldots,x_{n-1},X_n) - E(F(x_1,\ldots,x_{n-1},X_n)$ for each fixed choice of values $x_1,\ldots,x_{n-1}$ of $X_1,\ldots,X_{n-1}$ . From the triangle inequality for expectations we see that fluctuation properties of F are inherited by the average $F_{n-1}(x_1,\ldots,x_n) = E( F(x_1,\ldots,x_{n-1},X_n) )$ ; for instance, if $|F(x_1,\ldots,x_{n-2},x_{n-1},x_n)-F(x_1,\ldots,x_{n-2},x'_{n-1},x_n)| \leq c_{n-1}$ for all $x_1,\ldots,x_n, x'_{n-1}$ , then by the triangle inequality $E |F(x_1,\ldots,x_{n-2},x_{n-1},X_n)-F(x_1,\ldots,x_{n-2},x'_{n-1},X_n)| \leq c_{n-1}$ and thus $|E F(x_1,\ldots,x_{n-2},x_{n-1},X_n) - F(x_1,\ldots,x_{n-2},x'_{n-1},X_n)| \leq c_{n-1}$ , so that $F_{n-1}$ only fluctuates by at most $c_{n-1}$ in the $x_{n-1}$ variable.

If you are more familiar with measure theory than with probability theory, it can be an instructive exercise to write out the argument in measure-theoretic terms, say in the simple case when n=2 and the variable X_1, X_2 are just Bernoulli distributions on {0,1} with a probability 1/2 of each, avoiding all use of probabilistic language. While this is ultimately not the most efficient way to think about such arguments, it can serve as a stepping stone towards a more probabilistic way of thinking.

4 July, 2012 at 11:16 am

Ahriman

Thank you a lot for yours answers, and time you spent writing it. The case of a finite probability space is clear for me.
Your definition of conditional expectation is not the same as the one I know. I have to rethink about it. In particular, I always tried to keep away those notions of disintegration.
Thank you again.

29 August, 2012 at 7:15 pm

Anonymous

Dear Professor Tao,

I see most of the results here are about indepdendent random variables. What is your opinion and knowledge of any literature on concentration for random variables which are not independent? Thank you very much!

29 August, 2012 at 9:32 pm

Nick Cook

I can offer some buzz words! For measures on manifolds other than product spaces, the logarithmic Sobolev inequality machinery can be employed – check out Ledoux’s book. “Dumber” methods like spectral gap / Poincare inequality may be sufficient at times. See also Sourav Chatterjee’s PhD thesis on using exchangeable pairs to get concentration inequalities, with applications to e.g. spin systems. Ledoux’s book also seems to cover transportation cost inequalities.

Sometimes there is a trick to express the variables in terms of independent variables. For example, the coordinates of a uniform random point on the simplex $X=(X_1,\dots,X_n)$ (with the dependence relation $X_1+\cdots +X_n=1$ ) can be expressed in terms of independent rate $n$ exponential random variables $Y_1,\dots,Y_n$ via $X_i=Y_i/(\sum_{j=1}^n Y_j)$ . (That is, the coordinates $X_i$ have beta distribution.)

It really depends on the flavor of the dependence – dependent random variables seem to be like nonlinear PDE in that there can’t be any general methodology.

14 October, 2012 at 5:44 pm

The Chowla conjecture and the Sarnak conjecture « What’s new

[…] Finally, this exponentially high concentration can be achieved by the moment method, using a slight variant of the moment method proof of the large deviation estimates such as the Chernoff inequality or Hoeffding inequality (as discussed in this blog post). […]

15 October, 2012 at 10:48 pm

Hoeffding bound | blayz

[…] sections of the book Topics in Random Matrix Theory by Terry Tao, with his draft and relevant notes available online, and the Hoeffding’s original paper along with the paper by Serfling. I […]

1 December, 2012 at 10:54 am

Jon

Dear Prof. Tao,

I am a bit unsure of what Exercise 7 is asking – is it asking to prove the result only for sufficiently large A (as in Proposition 6), or for all A > 0 (as in Exercise 6)?

Thanks.

[The former; one could consider combining both generalisations, but this would be a separate problem. -T.]

18 December, 2012 at 9:23 pm

The Rosenblog » Azuma’s Inequality and Concentration

[…] I just posted an essay which gives some applications of Azuma’s inequality to combinatorics and theoretical computer science, which is available here. Azuma’s inequality is an example of the concentration of measure phenomenon, which has rich applications in combinatorics, probability theory and Banach space theory. This book gives a very thorough survey of the phenomenon, although it approaches the subject from a very geometric/measure theoretic standpoint. A more condensed (and perhaps user-friendly) overview is available on Terence Tao’s blog. […]

5 February, 2013 at 2:47 pm

Some notes on Bakry-Emery theory « What’s new

[…] inequalities can also be used to establish concentration of measure inequalities; see for instance this previous blog post for an instance of […]

13 May, 2013 at 12:00 pm

חסם צ'רנוף, חסם אנטרופיה ומה שביניהם | One and One

[…] לקריאה נוספת: פוסט של טרי טאו על ריכוז של מידה. […]

14 November, 2013 at 10:57 pm

Anonymous

Are the summands for last applicational result really independent or merely uncorrelated?

[Corrected, thanks – T.]

24 October, 2014 at 12:26 am

Anonymous

Do you want the variance to be “at least 1” or “at most 1”. The current formulation seems inconsistent with the note right after this line.

[“At most”. Note clarified to remove the confusion. -T.]

20 September, 2015 at 10:11 am

Entropy and rare events | What's new

[…] inequality, but there are of course many other estimates of this type (see e.g. this previous blog post for some others). Roughly speaking, concentration of measure inequalities allow one to make […]

21 September, 2015 at 1:22 pm

Jiasen Yang

Dear Professor Tao,

Thank you for the detailed post! I’ve been going through the proof of McDiarmid’s inequality, and I don’t see why it is necessary to assume that the $X_i$ ‘s are independent. I wonder if you could point out which step(s) I missed?

Thanks very much!

[One needs the independence to ensure that (say) $X_n$ continues to have mean zero even after conditioning on $X_1,\dots,X_{n-1}$ . -T. Note also that the theorem fails quite badly if for instance one has the very strong coupling $X_1=\dots=X_n$ . -T.]

21 September, 2015 at 7:23 pm

Jiasen Yang

Dear Professor Tao,

Thank you for your timely reply! Your coupling argument certainly makes sense, but I’m still having trouble determining which step of the proof uses independence directly. Following your point, I agree that $E[X_n] \neq E[X_n|X_1,\ldots,X_{n-1}]$ in general, but I don’t see where $X_n$ is assumed to have mean zero?

Actually, my question originally arose as I was reading a paper which claims to use McDiarmid’s inequality for dependent $X_i$’s after replacing the assumption
$$ |F(x_1,\ldots,x_{i-1},x_i,x_{i+1},\ldots,x_n) – F(x_1,\ldots,x_{i-1},x_i’,x_{i+1},\ldots,x_n)| \leq c_i $$
by
$$ |\bf{E}[f(X)|x_1,\ldots, x_{i-1},x_i] – \bf{E}[f(X)|x_1,\ldots, x_{i-1},x_i’]| \le c_i $$, but I don’t see why this new assumption resolves the issue.

Thank you again, and please forgive me for my stubbornness!

21 September, 2015 at 7:39 pm

Terence Tao

Sorry, my previous reply was quite incorrect, I was thinking of a different concentration equality. For McDiarmid, the claim that the conditioned function $F_{n-1}$ obeys the same hypotheses as the original function $F_n$ requires the independence hypothesis, as one will find if one expands out the proof of this claim.

21 September, 2015 at 8:08 pm

Jiasen Yang

Ah! I finally see your point. Thank you Professor!

23 October, 2015 at 8:06 am

275A, Notes 3: The weak and strong law of large numbers | What's new

[…] theory and high dimensional geometry. We will not discuss these topics much in this course, but see this previous blog post for some further […]

6 November, 2015 at 4:19 pm

Mahmood

Dear Professor Tao,

In the proof of Lemma 11 and the definition of set $B:=\{z'\in\Omega^{n-1}: (z',t)\in A \text{ for some } t\in\Omega\}$ . What happens if such $t$ is equal to $X_n$ ? Is it still valid to say that $U_A(X) \text{contains} U_B(X')\times\{1\}$ . For example, when the set $A$ has the points whose $n\text{th}$ coordinates are all equal to $X_n$ , then $U_A(X)$ does not have any element with the last coordinate 1. Am I missing something?

Thanks.

6 November, 2015 at 9:46 pm

Terence Tao

Oops, you’re right, the $t=X_n$ case has to be handled separately, but the bound is better in that case (one can stay in the ${\bf R}^{n-1} \times \{0\}$ slice). I’ve updated the argument accordingly.

7 November, 2015 at 8:51 am

mazrouei

Thanks for your reply.

19 November, 2015 at 2:51 pm

275A, Notes 5: Variants of the central limit theorem | What's new

[…] in which the underlying random variable is not bounded, but enjoys good moment bounds. See this previous blog post for these inequalities and some further discussion. Last, but certainly not least, there is an […]

17 February, 2016 at 6:59 pm

Anonymous

Hello Professor Tao,

In the proof of SLLN, I am not sure what do you mean by ‘countable additivity’ in building the connections bewteen convergence of two sequences. Does it mean adding O(\varepsilon)?

Thanks!

Jack

17 February, 2016 at 7:22 pm

Terence Tao

If $S_{n_m}/n_m$ is almost surely convergent to ${\bf E} X$ , then almost surely it is the case that $S_n/n$ fluctuates by at most $O(\varepsilon)$ around ${\bf E} X$ (in the sense that the limit superior and limit inferior are both almost surely ${\bf X}+O(\varepsilon)$ . Setting $\varepsilon= 1/n$ (say) for $n=1,2,3,\dots$ and using countable additivity (which implies that the countable intersection of almost sure events is still almost sure, we conclude that the limit superior and limit inferior are both almost surely ${\bf E}$ , giving the SLLN.

17 February, 2016 at 8:33 pm

Anonymous

Ah, I see. Thanks a lot for your reply!

Best,
Jack

9 April, 2016 at 7:44 am

Anonymous

Dear Prof. Tao, I believe your notes are just impressive.

What can we say on the lower bound on $Pr[|S_n|\geq \lambda]\geq ?$,depending on the moments of the distribution of the jointly independent, zero mean, variables $X_i$?

11 April, 2016 at 8:50 am

Terence Tao

This is the realm of large deviation theory; these bounds tend to depend in various subtle ways on the precise distribution of the independent variables. See for instance this paper of Nagaev for a classical survey of results; probably there are more up to date surveys also.

14 April, 2016 at 10:39 am

gninrepoli

I think that the probability of a recursive nature, so this phenomenon is possible. Probability – it’s just part of the recursion. Any probabilistic model is necessary to approximate recursion, which we can control. For example the set of prime numbers is recursive. But how to prove it.

25 April, 2016 at 3:24 pm

Nathan

Dear Prof. Tao,

First I would like to thank you for your notes, which are quite impressive!

I do not understand why each summand has a variance of $O(K^2)$ in the computation of the variance of $d(X,V)^2$ (corollary 13). Since $|X_i| \leq K$ and a term in the computation has the form $E[X_i^2X_j^2]$ , shouldn’t we have an $O(K^4)$ ?

Thanks!

26 April, 2016 at 8:34 am

Terence Tao

${\bf E}( X_i^2 X_j^2 ) \leq {\bf E}( K^2 X_j^2 ) = K^2$ , since $X_j$ has mean zero and variance one.

26 April, 2016 at 11:27 am

Nathan

Thank you!

2 March, 2017 at 12:17 am

keej

I was also stuck on this point; thanks for clarifying!

5 June, 2016 at 4:49 am

Vaibhav

Hi Prof. Terrence Tao,

I am a very simple question. In, (McDiarmid’s inequality) it is not clear how does it depend upon N, the number of random variables concerned. Intuitively, and as you mention elsewhere, the inequality should become stronger. That is, as the number of random variables increase, the deviation from the mean of the function should be less likely. Could you kindly clarify.

Quoting you:

“The basic intuition here is that it is difficult for a large number of independent variables {X_1,\ldots,X_n} to “work together” to simultaneously pull a sum {X_1+\ldots+X_n} or a more general combination {F(X_1,\ldots,X_n)} too far away from its mean. Independence here is the key; concentration of measure results typically fail if the {X_i} are too highly correlated with each other.”

I fail to see this effect.

6 June, 2016 at 1:53 pm

Terence Tao

Let’s say we are working in the normalisation $c_i=1$ . The hypothesis of Theorem 7 allows $F$ to range over an interval of size $n$ ; but McDiarmid’s inequality shows that concentration instead occurs at a shorter interval at the scale of $\sigma =\sqrt{n}$ .

6 June, 2016 at 6:19 pm

Vaibhav

Dear Prof. Tao, Thanks a lot. This helps most certainly.

6 June, 2016 at 6:51 pm

Vaibhav

Dear Prof. Tao,

I had a following question about Levy’s Lemma (another celebreated concentration of measure result).

First the Levy’s Lemma.

Let $f : S^k \rightarrow R$
be a function with Lipschitz constant $\eta$ (with respect to the Euclidean norm) and $X \in k$
and a point $X \in S^{k}$ be chosen uniformly at random. Then
\begin{align}
\label{levy}
Pr\{|f(X) – \bar{f}| > \alpha\}\le exp (-C(k+1)\alpha^{2}/\eta^2 )
\end{align}
for some constant $C >0$ and $\bar{f}$ is the mean value of the function over the sphere.

Now, here is my question: This Lemma seems to hold for a point chosen
uniformly at random over a sphere.
My question is….suppose I choose a point on an N dimensional sphere (X_1, X_2,…, X_N) such that (X_1^2, X_2^2, …, X_N^2) is chosen from a uniform distribution.
Certainly (X_1^2, X_2^2, …, X_N^2) chosen from a uniform distribution does not imply (X_1, X_2,…, X_N) will be a uniformly random point on the sphere.
But intuitively, I will expect Levy’s Lemma (or say a weaker version) to hold as I expect it to hold
for almost all points on the sphere.
My computer simulations also show this to be the case.
But, I cannot make mathematical arguments to justify my intuition and my simulations.

Best,

vaibhav

Ps: If I can show this, I can show a neat result in evolutionary biology, which I will be happy to show it to you if you would like.
Many thanks to you!

28 June, 2016 at 5:41 am

Ahn

Dear prof. Tao,

While I read the proof of proposition 6, I could not follow the step at the end where you applied chernoff bound. For example, what did you choose for lambda?

I would appreciate your help.

29 June, 2016 at 6:51 am

Terence Tao

There is a lot of latitude here in what to choose for $\lambda$ , for instance one can take $\lambda = c'' A \exp( c' 2^{2m} / 2 )$ for some small $c'' > 0$ . Note that the bound on the RHS is not optimal, but suffices for the application at hand.

8 November, 2016 at 8:40 am

Fast Randomized SVD – Facebook Research

[…] our approximation by appealing to concentration of measure results for random matrices – see Terry Tao’s lecture notes on the topic for some useful […]

12 February, 2017 at 11:53 am

keej

Could anyone please explain why in the proof of Hoeffding’s lemma, the first Taylor expansion is $e^(tX) = 1 + tX + O(t^2 X^2 exp(O(t))$ and not just the naive $e^(tX) = 1 + tX + O(t^2 X^2)$ ?

12 February, 2017 at 3:39 pm

Anonymous

The simpler estimate $O(t^2 X^2)$ for the remainder term applies only for bounded $t X$ .

12 February, 2017 at 5:01 pm

keej

Of course, thank you.

13 May, 2017 at 5:28 pm

Zahra

Hello Prof. Tao,

Any known results for the extension of theorem 8 to the case when $(X_1,\ldots, X_n)$ be a vector of iid sub-gaussian variables? Many Thanks.

[Probably. I don’t have references handy, but I would recommend checking Ledoux’s book on the subject. -T.]

22 May, 2017 at 5:55 pm

Quantitative continuity estimates | What's new

[…] is the proof by Maurey and Pisier of the gaussian concentration inequality, given in Theorem 8 of this previous blog post. In a similar vein, if one wishes to compare a scalar random variable of mean zero and variance […]

24 December, 2017 at 1:19 pm

AL Ray

I don’t understand something in the proof of the Lemma 10 why is $z_\omega \in X\setminus A$ and not $z_w\in A\setminus X$ ?

Thanks in advance!

[This is a typo, now fixed – T.]

30 December, 2017 at 10:41 pm

Tim

Dear Prof. Tao,

Thanks for the insightful notes. I have two questions:

1. When calculating the variance of d(X, V)^2, a term in the computation will be E[X_i^2 X_j^2], which I think should be 1 instead of O(K^2) since X_i and X_j are independent.
2. Are there any more direct ways to calculate / estimate the expectation of d(X, V)?

Thanks in advance!

31 December, 2017 at 10:29 am

Terence Tao

It’s true one can improve the bound on the variance of $d(X,V)^2$ , but unfortunately this does not significantly improve the concentration bound because of the uncertainty of $O(K)$ coming from the use of Theorem 9.

I don’t know of much sharper ways to control the expectation, but there are several routes to the concentration property at least, starting with the classic work of Hanson and Wright.

	How valuable is a Fi… on Birkar, Figalli, Scholze,…
	Karl Keppler on The Poisson-Dirichlet process,…
	Tatenda Kubalalika on Heat flow and zeroes of polyno…
	Terence Tao on Gamifying propositional logic:…
	Antoine Deleforge on Gamifying propositional logic:…
	Anonymous on Polymath15, ninth thread: goin…
	Terence Tao on Polymath15, ninth thread: goin…
	Terence Tao on 254B, Notes 3: Linear pat…
	KM on Polymath15, ninth thread: goin…
	Mixkino on Compressed sensing and single-…
	Irfan Ali on The De Bruijn-Newman constant…
	farlabb on 254B, Notes 3: Linear pat…
	farlabb on 254B, Notes 3: Linear pat…
	Terence Tao on 254B, Notes 3: Linear pat…
	farlabb on 254B, Notes 3: Linear pat…

254A, Notes 1: Concentration of measure

Recent Comments

Articles by others

Diversions

Mathematics

Selected articles

Software

The sciences

Top Posts

Archives

Categories

The Polymath Blog

116 comments

Leave a Reply Cancel reply

For commenters

254A, Notes 1: Concentration of measure

Share this:

Like this:

Recent Comments

Articles by others

Diversions

Mathematics

Selected articles

Software

The sciences

Top Posts

Archives

Categories

The Polymath Blog

116 comments

Leave a Reply Cancel reply

For commenters