# Conditional Expectations

The conditional expectation of a random variable ${\displaystyle Y}$ with respect to an event ${\displaystyle {\mathcal {E}}}$ is defined by

${\displaystyle \mathbf {E} [Y\mid {\mathcal {E}}]=\sum _{y}y\Pr[Y=y\mid {\mathcal {E}}].}$

In particular, if the event ${\displaystyle {\mathcal {E}}}$ is ${\displaystyle X=a}$, the conditional expectation

${\displaystyle \mathbf {E} [Y\mid X=a]}$

defines a function

${\displaystyle f(a)=\mathbf {E} [Y\mid X=a].}$

Thus, ${\displaystyle \mathbf {E} [Y\mid X]}$ can be regarded as a random variable ${\displaystyle f(X)}$.

Example
Suppose that we uniformly sample a human from all human beings. Let ${\displaystyle Y}$ be his/her height, and let ${\displaystyle X}$ be the country where he/she is from. For any country ${\displaystyle a}$, ${\displaystyle \mathbf {E} [Y\mid X=a]}$ gives the average height of that country. And ${\displaystyle \mathbf {E} [Y\mid X]}$ is the random variable which can be defined in either ways:
• We choose a human uniformly at random from all human beings, and ${\displaystyle \mathbf {E} [Y\mid X]}$ is the average height of the country where he/she comes from.
• We choose a country at random with a probability proportional to its population, and ${\displaystyle \mathbf {E} [Y\mid X]}$ is the average height of the chosen country.

The following proposition states some fundamental facts about conditional expectation.

 Proposition (fundamental facts about conditional expectation) Let ${\displaystyle X,Y}$ and ${\displaystyle Z}$ be arbitrary random variables. Let ${\displaystyle f}$ and ${\displaystyle g}$ be arbitrary functions. Then ${\displaystyle \mathbf {E} [X]=\mathbf {E} [\mathbf {E} [X\mid Y]]}$. ${\displaystyle \mathbf {E} [X\mid Z]=\mathbf {E} [\mathbf {E} [X\mid Y,Z]\mid Z]}$. ${\displaystyle \mathbf {E} [\mathbf {E} [f(X)g(X,Y)\mid X]]=\mathbf {E} [f(X)\cdot \mathbf {E} [g(X,Y)\mid X]]}$.

The proposition can be formally verified by computing these expectations. Although these equations look formal, the intuitive interpretations to them are very clear.

The first equation:

${\displaystyle \mathbf {E} [X]=\mathbf {E} [\mathbf {E} [X\mid Y]]}$

says that there are two ways to compute an average. Suppose again that ${\displaystyle X}$ is the height of a uniform random human and ${\displaystyle Y}$ is the country where he/she is from. There are two ways to compute the average human height: one is to directly average over the heights of all humans; the other is that first compute the average height for each country, and then average over these heights weighted by the populations of the countries.

The second equation:

${\displaystyle \mathbf {E} [X\mid Z]=\mathbf {E} [\mathbf {E} [X\mid Y,Z]\mid Z]}$

is the same as the first one, restricted to a particular subspace. As the previous example, inaddition to the height ${\displaystyle X}$ and the country ${\displaystyle Y}$, let ${\displaystyle Z}$ be the gender of the individual. Thus, ${\displaystyle \mathbf {E} [X\mid Z]}$ is the average height of a human being of a given sex. Again, this can be computed either directly or on a country-by-country basis.

The third equation:

${\displaystyle \mathbf {E} [\mathbf {E} [f(X)g(X,Y)\mid X]]=\mathbf {E} [f(X)\cdot \mathbf {E} [g(X,Y)\mid X]]}$.

looks obscure at the first glance, especially when considering that ${\displaystyle X}$ and ${\displaystyle Y}$ are not necessarily independent. Nevertheless, the equation follows the simple fact that conditioning on any ${\displaystyle X=a}$, the function value ${\displaystyle f(X)=f(a)}$ becomes a constant, thus can be safely taken outside the expectation due to the linearity of expectation. For any value ${\displaystyle X=a}$,

${\displaystyle \mathbf {E} [f(X)g(X,Y)\mid X=a]=\mathbf {E} [f(a)g(X,Y)\mid X=a]=f(a)\cdot \mathbf {E} [g(X,Y)\mid X=a].}$

The proposition holds in more general cases when ${\displaystyle X,Y}$ and ${\displaystyle Z}$ are a sequence of random variables.

# Martingales

"Martingale" originally refers to a betting strategy in which the gambler doubles his bet after every loss. Assuming unlimited wealth, this strategy is guaranteed to eventually have a positive net profit. For example, starting from an initial stake 1, after ${\displaystyle n}$ losses, if the ${\displaystyle (n+1)}$th bet wins, then it gives a net profit of

${\displaystyle 2^{n}-\sum _{i=1}^{n}2^{i-1}=1,}$

which is a positive number.

However, the assumption of unlimited wealth is unrealistic. For limited wealth, with geometrically increasing bet, it is very likely to end up bankrupt. You should never try this strategy in real life.

Suppose that the gambler is allowed to use any strategy. His stake on the next beting is decided based on the results of all the bettings so far. This gives us a highly dependent sequence of random variables ${\displaystyle X_{0},X_{1},\ldots ,}$, where ${\displaystyle X_{0}}$ is his initial capital, and ${\displaystyle X_{i}}$ represents his capital after the ${\displaystyle i}$th betting. Up to different betting strategies, ${\displaystyle X_{i}}$ can be arbitrarily dependent on ${\displaystyle X_{0},\ldots ,X_{i-1}}$. However, as long as the game is fair, namely, winning and losing with equal chances, conditioning on the past variables ${\displaystyle X_{0},\ldots ,X_{i-1}}$, we will expect no change in the value of the present variable ${\displaystyle X_{i}}$ on average. Random variables satisfying this property is called a martingale sequence.

 Definition (martingale) A sequence of random variables ${\displaystyle X_{0},X_{1},\ldots }$ is a martingale if for all ${\displaystyle i>0}$, {\displaystyle {\begin{aligned}\mathbf {E} [X_{i}\mid X_{0},\ldots ,X_{i-1}]=X_{i-1}.\end{aligned}}}

## Examples

coin flips
A fair coin is flipped for a number of times. Let ${\displaystyle Z_{j}\in \{-1,1\}}$ denote the outcome of the ${\displaystyle j}$th flip. Let
${\displaystyle X_{0}=0\quad {\mbox{ and }}\quad X_{i}=\sum _{j\leq i}Z_{j}}$.
The random variables ${\displaystyle X_{0},X_{1},\ldots }$ defines a martingale.
Proof
We first observe that ${\displaystyle \mathbf {E} [X_{i}\mid X_{0},\ldots ,X_{i-1}]=\mathbf {E} [X_{i}\mid X_{i-1}]}$, which intuitively says that the next number of HEADs depends only on the current number of HEADs. This property is also called the Markov property in statistic processes.
{\displaystyle {\begin{aligned}\mathbf {E} [X_{i}\mid X_{0},\ldots ,X_{i-1}]&=\mathbf {E} [X_{i}\mid X_{i-1}]\\&=\mathbf {E} [X_{i-1}+Z_{i}\mid X_{i-1}]\\&=\mathbf {E} [X_{i-1}\mid X_{i-1}]+\mathbf {E} [Z_{i}\mid X_{i-1}]\\&=X_{i-1}+\mathbf {E} [Z_{i}\mid X_{i-1}]\\&=X_{i-1}+\mathbf {E} [Z_{i}]&\quad ({\mbox{independence of coin flips}})\\&=X_{i-1}\end{aligned}}}
Polya's urn scheme
Consider an urn (just a container) that initially contains ${\displaystyle b}$ balck balls and ${\displaystyle w}$ white balls. At each step, we uniformly select a ball from the urn, and replace the ball with ${\displaystyle c}$ balls of the same color. Let ${\displaystyle X_{0}=b/(b+w)}$, and ${\displaystyle X_{i}}$ be the fraction of black balls in the urn after the ${\displaystyle i}$th step. The sequence ${\displaystyle X_{0},X_{1},\ldots }$ is a martingale.
edge exposure in a random graph
Consider a random graph ${\displaystyle G}$ generated as follows. Let ${\displaystyle [n]}$ be the set of vertices, and let ${\displaystyle [m]={[n] \choose 2}}$ be the set of all possible edges. For convenience, we enumerate these potential edges by ${\displaystyle e_{1},\ldots ,e_{m}}$. For each potential edge ${\displaystyle e_{j}}$, we independently flip a fair coin to decide whether the edge ${\displaystyle e_{j}}$ appears in ${\displaystyle G}$. Let ${\displaystyle I_{j}}$ be the random variable that indicates whether ${\displaystyle e_{j}\in G}$. We are interested in some graph-theoretical parameter, say chromatic number, of the random graph ${\displaystyle G}$. Let ${\displaystyle \chi (G)}$ be the chromatic number of ${\displaystyle G}$. Let ${\displaystyle X_{0}=\mathbf {E} [\chi (G)]}$, and for each ${\displaystyle i\geq 1}$, let ${\displaystyle X_{i}=\mathbf {E} [\chi (G)\mid I_{1},\ldots ,I_{i}]}$, namely, the expected chromatic number of the random graph after fixing the first ${\displaystyle i}$ edges. This process is called edges exposure of a random graph, as we "exposing" the edges one by one in a random graph.

It is nontrivial to formally verify that the edge exposure sequence for a random graph is a martingale. However, we will later see that this construction can be put into a more general context.

## Generalizations

The martingale can be generalized to be with respect to another sequence of random variables.

 Definition (martingale, general version) A sequence of random variables ${\displaystyle Y_{0},Y_{1},\ldots }$ is a martingale with respect to the sequence ${\displaystyle X_{0},X_{1},\ldots }$ if, for all ${\displaystyle i\geq 0}$, the following conditions hold: ${\displaystyle Y_{i}}$ is a function of ${\displaystyle X_{0},X_{1},\ldots ,X_{i}}$; {\displaystyle {\begin{aligned}\mathbf {E} [Y_{i+1}\mid X_{0},\ldots ,X_{i}]=Y_{i}.\end{aligned}}}

Therefore, a sequence ${\displaystyle X_{0},X_{1},\ldots }$ is a martingale if it is a martingale with respect to itself.

The purpose of this generalization is that we are usually more interested in a function of a sequence of random variables, rather than the sequence itself.

# Azuma's Inequality

We introduce a martingale tail inequality, called Azuma's inequality.

 Azuma's Inequality Let ${\displaystyle X_{0},X_{1},\ldots }$ be a martingale such that, for all ${\displaystyle k\geq 1}$, ${\displaystyle |X_{k}-X_{k-1}|\leq c_{k},}$ Then {\displaystyle {\begin{aligned}\Pr \left[|X_{n}-X_{0}|\geq t\right]\leq 2\exp \left(-{\frac {t^{2}}{2\sum _{k=1}^{n}c_{k}^{2}}}\right).\end{aligned}}}

Before formally proving this theorem, some comments are in order. First, unlike the Chernoff bounds, there is no assumption of independence. This shows the power of martingale inequalities.

Second, the condition that

${\displaystyle |X_{k}-X_{k-1}|\leq c_{k}}$

is central to the proof. This condition is sometimes called the bounded difference condition. If we think of the martingale ${\displaystyle X_{0},X_{1},\ldots }$ as a process evolving through time, where ${\displaystyle X_{i}}$ gives some measurement at time ${\displaystyle i}$, the bounded difference condition states that the process does not make big jumps. The Azuma's inequality says that if so, then it is unlikely that process wanders far from its starting point.

A special case is when the differences are bounded by a constant. The following corollary is directly implied by the Azuma's inequality.

 Corollary Let ${\displaystyle X_{0},X_{1},\ldots }$ be a martingale such that, for all ${\displaystyle k\geq 1}$, ${\displaystyle |X_{k}-X_{k-1}|\leq c,}$ Then {\displaystyle {\begin{aligned}\Pr \left[|X_{n}-X_{0}|\geq ct{\sqrt {n}}\right]\leq 2e^{-t^{2}/2}.\end{aligned}}}

This corollary states that for any martingale sequence whose diferences are bounded by a constant, the probability that it deviates ${\displaystyle \omega ({\sqrt {n}})}$ far away from the starting point after ${\displaystyle n}$ steps is bounded by ${\displaystyle o(1)}$.

### Generalization

Azuma's inequality can be generalized to a martingale with respect another sequence.

 Azuma's Inequality (general version) Let ${\displaystyle Y_{0},Y_{1},\ldots }$ be a martingale with respect to the sequence ${\displaystyle X_{0},X_{1},\ldots }$ such that, for all ${\displaystyle k\geq 1}$, ${\displaystyle |Y_{k}-Y_{k-1}|\leq c_{k},}$ Then {\displaystyle {\begin{aligned}\Pr \left[|Y_{n}-Y_{0}|\geq t\right]\leq 2\exp \left(-{\frac {t^{2}}{2\sum _{k=1}^{n}c_{k}^{2}}}\right).\end{aligned}}}

### The Proof of Azuma's Inueqality

We will only give the formal proof of the non-generalized version. The proof of the general version is almost identical, with the only difference that we work on random sequence ${\displaystyle Y_{i}}$ conditioning on sequence ${\displaystyle X_{i}}$.

The proof of Azuma's Inequality uses several ideas which are used in the proof of the Chernoff bounds. We first observe that the total deviation of the martingale sequence can be represented as the sum of deferences in every steps. Thus, as the Chernoff bounds, we are looking for a bound of the deviation of the sum of random variables. The strategy of the proof is almost the same as the proof of Chernoff bounds: we first apply Markov's inequality to the moment generating function, then we bound the moment generating function, and at last we optimize the parameter of the moment generating function. However, unlike the Chernoff bounds, the martingale differences are not independent any more. So we replace the use of the independence in the Chernoff bound by the martingale property. The proof is detailed as follows.

In order to bound the probability of ${\displaystyle |X_{n}-X_{0}|\geq t}$, we first bound the upper tail ${\displaystyle \Pr[X_{n}-X_{0}\geq t]}$. The bound of the lower tail can be symmetrically proved with the ${\displaystyle X_{i}}$ replaced by ${\displaystyle -X_{i}}$.

#### Represent the deviation as the sum of differences

We define the martingale difference sequence: for ${\displaystyle i\geq 1}$, let

${\displaystyle Y_{i}=X_{i}-X_{i-1}.}$

It holds that

{\displaystyle {\begin{aligned}\mathbf {E} [Y_{i}\mid X_{0},\ldots ,X_{i-1}]&=\mathbf {E} [X_{i}-X_{i-1}\mid X_{0},\ldots ,X_{i-1}]\\&=\mathbf {E} [X_{i}\mid X_{0},\ldots ,X_{i-1}]-\mathbf {E} [X_{i-1}\mid X_{0},\ldots ,X_{i-1}]\\&=X_{i-1}-X_{i-1}\\&=0.\end{aligned}}}

The second to the last equation is due to the fact that ${\displaystyle X_{0},X_{1},\ldots }$ is a martingale and the definition of conditional expectation.

Let ${\displaystyle Z_{n}}$ be the accumulated differences

${\displaystyle Z_{n}=\sum _{i=1}^{n}Y_{i}.}$

The deviation ${\displaystyle (X_{n}-X_{0})}$ can be computed by the accumulated differences:

{\displaystyle {\begin{aligned}X_{n}-X_{0}&=(X_{1}-X_{0})+(X_{2}-X_{1})+\cdots +(X_{n}-X_{n-1})\\&=\sum _{i=1}^{n}Y_{i}\\&=Z_{n}.\end{aligned}}}

We then only need to upper bound the probability of the event ${\displaystyle Z_{n}\geq t}$.

#### Apply Markov's inequality to the moment generating function

The event ${\displaystyle Z_{n}\geq t}$ is equivalent to that ${\displaystyle e^{\lambda Z_{n}}\geq e^{\lambda t}}$ for ${\displaystyle \lambda >0}$. Apply Markov's inequality, we have

{\displaystyle {\begin{aligned}\Pr \left[Z_{n}\geq t\right]&=\Pr \left[e^{\lambda Z_{n}}\geq e^{\lambda t}\right]\\&\leq {\frac {\mathbf {E} \left[e^{\lambda Z_{n}}\right]}{e^{\lambda t}}}.\end{aligned}}}

This is exactly the same as what we did to prove the Chernoff bound. Next, we need to bound the moment generating function ${\displaystyle \mathbf {E} \left[e^{\lambda Z_{n}}\right]}$.

#### Bound the moment generating functions

The moment generating function

{\displaystyle {\begin{aligned}\mathbf {E} \left[e^{\lambda Z_{n}}\right]&=\mathbf {E} \left[\mathbf {E} \left[e^{\lambda Z_{n}}\mid X_{0},\ldots ,X_{n-1}\right]\right]\\&=\mathbf {E} \left[\mathbf {E} \left[e^{\lambda (Z_{n-1}+Y_{n})}\mid X_{0},\ldots ,X_{n-1}\right]\right]\\&=\mathbf {E} \left[\mathbf {E} \left[e^{\lambda Z_{n-1}}\cdot e^{\lambda Y_{n}}\mid X_{0},\ldots ,X_{n-1}\right]\right]\\&=\mathbf {E} \left[e^{\lambda Z_{n-1}}\cdot \mathbf {E} \left[e^{\lambda Y_{n}}\mid X_{0},\ldots ,X_{n-1}\right]\right]\end{aligned}}}

The first and the last equations are due to the fundamental facts about conditional expectation which are proved by us in the first section.

We then upper bound the ${\displaystyle \mathbf {E} \left[e^{\lambda Y_{n}}\mid X_{0},\ldots ,X_{n-1}\right]}$ by a constant. To do so, we need the following technical lemma which is proved by the convexity of ${\displaystyle e^{\lambda Y_{n}}}$.

 Lemma Let ${\displaystyle X}$ be a random variable such that ${\displaystyle \mathbf {E} [X]=0}$ and ${\displaystyle |X|\leq c}$. Then for ${\displaystyle \lambda >0}$, ${\displaystyle \mathbf {E} [e^{\lambda X}]\leq e^{\lambda ^{2}c^{2}/2}.}$
Proof.
 Observe that for ${\displaystyle \lambda >0}$, the function ${\displaystyle e^{\lambda X}}$ of the variable ${\displaystyle X}$ is convex in the interval ${\displaystyle [-c,c]}$. We draw a line between the two endpoints points ${\displaystyle (-c,e^{-\lambda c})}$ and ${\displaystyle (c,e^{\lambda c})}$. The curve of ${\displaystyle e^{\lambda X}}$ lies entirely below this line. Thus, {\displaystyle {\begin{aligned}e^{\lambda X}&\leq {\frac {c-X}{2c}}e^{-\lambda c}+{\frac {c+X}{2c}}e^{\lambda c}\\&={\frac {e^{\lambda c}+e^{-\lambda c}}{2}}+{\frac {X}{2c}}(e^{\lambda c}-e^{-\lambda c}).\end{aligned}}} Since ${\displaystyle \mathbf {E} [X]=0}$, we have {\displaystyle {\begin{aligned}\mathbf {E} [e^{\lambda X}]&\leq \mathbf {E} [{\frac {e^{\lambda c}+e^{-\lambda c}}{2}}+{\frac {X}{2c}}(e^{\lambda c}-e^{-\lambda c})]\\&={\frac {e^{\lambda c}+e^{-\lambda c}}{2}}+{\frac {e^{\lambda c}-e^{-\lambda c}}{2c}}\mathbf {E} [X]\\&={\frac {e^{\lambda c}+e^{-\lambda c}}{2}}.\end{aligned}}} By expanding both sides as Taylor's series, it can be verified that ${\displaystyle {\frac {e^{\lambda c}+e^{-\lambda c}}{2}}\leq e^{\lambda ^{2}c^{2}/2}}$.
${\displaystyle \square }$

Apply the above lemma to the random variable

${\displaystyle (Y_{n}\mid X_{0},\ldots ,X_{n-1})}$

We have already shown that its expectation ${\displaystyle \mathbf {E} [(Y_{n}\mid X_{0},\ldots ,X_{n-1})]=0,}$ and by the bounded difference condition of Azuma's inequality, we have ${\displaystyle |Y_{n}|=|(X_{n}-X_{n-1})|\leq c_{n}.}$ Thus, due to the above lemma, it holds that

${\displaystyle \mathbf {E} [e^{\lambda Y_{n}}\mid X_{0},\ldots ,X_{n-1}]\leq e^{\lambda ^{2}c_{n}^{2}/2}.}$

Back to our analysis of the expectation ${\displaystyle \mathbf {E} \left[e^{\lambda Z_{n}}\right]}$, we have

{\displaystyle {\begin{aligned}\mathbf {E} \left[e^{\lambda Z_{n}}\right]&=\mathbf {E} \left[e^{\lambda Z_{n-1}}\cdot \mathbf {E} \left[e^{\lambda Y_{n}}\mid X_{0},\ldots ,X_{n-1}\right]\right]\\&\leq \mathbf {E} \left[e^{\lambda Z_{n-1}}\cdot e^{\lambda ^{2}c_{n}^{2}/2}\right]\\&=e^{\lambda ^{2}c_{n}^{2}/2}\cdot \mathbf {E} \left[e^{\lambda Z_{n-1}}\right].\end{aligned}}}

Apply the same analysis to ${\displaystyle \mathbf {E} \left[e^{\lambda Z_{n-1}}\right]}$, we can solve the above recursion by

{\displaystyle {\begin{aligned}\mathbf {E} \left[e^{\lambda Z_{n}}\right]&\leq \prod _{k=1}^{n}e^{\lambda ^{2}c_{k}^{2}/2}\\&=\exp \left(\lambda ^{2}\sum _{k=1}^{n}c_{k}^{2}/2\right).\end{aligned}}}

Go back to the Markov's inequality,

{\displaystyle {\begin{aligned}\Pr \left[Z_{n}\geq t\right]&\leq {\frac {\mathbf {E} \left[e^{\lambda Z_{n}}\right]}{e^{\lambda t}}}\\&\leq \exp \left(\lambda ^{2}\sum _{k=1}^{n}c_{k}^{2}/2-\lambda t\right).\end{aligned}}}

We then only need to choose a proper ${\displaystyle \lambda >0}$.

#### Optimization

By choosing ${\displaystyle \lambda ={\frac {t}{\sum _{k=1}^{n}c_{k}^{2}}}}$, we have that

${\displaystyle \exp \left(\lambda ^{2}\sum _{k=1}^{n}c_{k}^{2}/2-\lambda t\right)=\exp \left(-{\frac {t^{2}}{2\sum _{k=1}^{n}c_{k}^{2}}}\right).}$

Thus, the probability

{\displaystyle {\begin{aligned}\Pr \left[X_{n}-X_{0}\geq t\right]&=\Pr \left[Z_{n}\geq t\right]\\&\leq \exp \left(\lambda ^{2}\sum _{k=1}^{n}c_{k}^{2}/2-\lambda t\right)\\&=\exp \left(-{\frac {t^{2}}{2\sum _{k=1}^{n}c_{k}^{2}}}\right).\end{aligned}}}

The upper tail of Azuma's inequality is proved. By replacing ${\displaystyle X_{i}}$ by ${\displaystyle -X_{i}}$, the lower tail can be treated just as the upper tail. Applying the union bound, Azuma's inequality is proved.

# The Doob martingales

The following definition describes a very general approach for constructing an important type of martingales.

 Definition (The Doob sequence) The Doob sequence of a function ${\displaystyle f}$ with respect to a sequence of random variables ${\displaystyle X_{1},\ldots ,X_{n}}$ is defined by ${\displaystyle Y_{i}=\mathbf {E} [f(X_{1},\ldots ,X_{n})\mid X_{1},\ldots ,X_{i}],\quad 0\leq i\leq n.}$ In particular, ${\displaystyle Y_{0}=\mathbf {E} [f(X_{1},\ldots ,X_{n})]}$ and ${\displaystyle Y_{n}=f(X_{1},\ldots ,X_{n})}$.

The Doob sequence of a function defines a martingale. That is

${\displaystyle \mathbf {E} [Y_{i}\mid X_{1},\ldots ,X_{i-1}]=Y_{i-1},}$

for any ${\displaystyle 0\leq i\leq n}$.

To prove this claim, we recall the definition that ${\displaystyle Y_{i}=\mathbf {E} [f(X_{1},\ldots ,X_{n})\mid X_{1},\ldots ,X_{i}]}$, thus,

{\displaystyle {\begin{aligned}\mathbf {E} [Y_{i}\mid X_{1},\ldots ,X_{i-1}]&=\mathbf {E} [\mathbf {E} [f(X_{1},\ldots ,X_{n})\mid X_{1},\ldots ,X_{i}]\mid X_{1},\ldots ,X_{i-1}]\\&=\mathbf {E} [f(X_{1},\ldots ,X_{n})\mid X_{1},\ldots ,X_{i-1}]\\&=Y_{i-1},\end{aligned}}}

where the second equation is due to the fundamental fact about conditional expectation introduced in the first section.

The Doob martingale describes a very natural procedure to determine a function value of a sequence of random variables. Suppose that we want to predict the value of a function ${\displaystyle f(X_{1},\ldots ,X_{n})}$ of random variables ${\displaystyle X_{1},\ldots ,X_{n}}$. The Doob sequence ${\displaystyle Y_{0},Y_{1},\ldots ,Y_{n}}$ represents a sequence of refined estimates of the value of ${\displaystyle f(X_{1},\ldots ,X_{n})}$, gradually using more information on the values of the random variables ${\displaystyle X_{1},\ldots ,X_{n}}$. The first element ${\displaystyle Y_{0}}$ is just the expectation of ${\displaystyle f(X_{1},\ldots ,X_{n})}$. Element ${\displaystyle Y_{i}}$ is the expected value of ${\displaystyle f(X_{1},\ldots ,X_{n})}$ when the values of ${\displaystyle X_{1},\ldots ,X_{i}}$ are known, and ${\displaystyle Y_{n}=f(X_{1},\ldots ,X_{n})}$ when ${\displaystyle f(X_{1},\ldots ,X_{n})}$ is fully determined by ${\displaystyle X_{1},\ldots ,X_{n}}$.

The following two Doob martingales arise in evaluating the parameters of random graphs.

edge exposure martingale
Let ${\displaystyle G}$ be a random graph on ${\displaystyle n}$ vertices. Let ${\displaystyle f}$ be a real-valued function of graphs, such as, chromatic number, number of triangles, the size of the largest clique or independent set, etc. Denote that ${\displaystyle m={n \choose 2}}$. Fix an arbitrary numbering of potential edges between the ${\displaystyle n}$ vertices, and denote the edges as ${\displaystyle e_{1},\ldots ,e_{m}}$. Let
${\displaystyle X_{i}={\begin{cases}1&{\mbox{if }}e_{i}\in G,\\0&{\mbox{otherwise}}.\end{cases}}}$
Let ${\displaystyle Y_{0}=\mathbf {E} [f(G)]}$ and for ${\displaystyle i=1,\ldots ,m}$, let ${\displaystyle Y_{i}=\mathbf {E} [f(G)\mid X_{1},\ldots ,X_{i}]}$.
The sequence ${\displaystyle Y_{0},Y_{1},\ldots ,Y_{n}}$ gives a Doob martingale that is commonly called the edge exposure martingale.
vertex exposure martingale
Instead of revealing edges one at a time, we could reveal the set of edges connected to a given vertex, one vertex at a time. Suppose that the vertex set is ${\displaystyle [n]}$. Let ${\displaystyle X_{i}}$ be the subgraph of ${\displaystyle G}$ induced by the vertex set ${\displaystyle [i]}$, i.e. the first ${\displaystyle i}$ vertices.
Let ${\displaystyle Y_{0}=\mathbf {E} [f(G)]}$ and for ${\displaystyle i=1,\ldots ,n}$, let ${\displaystyle Y_{i}=\mathbf {E} [f(G)\mid X_{1},\ldots ,X_{i}]}$.
The sequence ${\displaystyle Y_{0},Y_{1},\ldots ,Y_{n}}$ gives a Doob martingale that is commonly called the vertex exposure martingale.

### Chromatic number

The random graph ${\displaystyle G(n,p)}$ is the graph on ${\displaystyle n}$ vertices ${\displaystyle [n]}$, obtained by selecting each pair of vertices to be an edge, randomly and independently, with probability ${\displaystyle p}$. We denote ${\displaystyle G\sim G(n,p)}$ if ${\displaystyle G}$ is generated in this way.

 Theorem [Shamir and Spencer (1987)] Let ${\displaystyle G\sim G(n,p)}$. Let ${\displaystyle \chi (G)}$ be the chromatic number of ${\displaystyle G}$. Then {\displaystyle {\begin{aligned}\Pr \left[|\chi (G)-\mathbf {E} [\chi (G)]|\geq t{\sqrt {n}}\right]\leq 2e^{-t^{2}/2}.\end{aligned}}}
Proof.
 Consider the vertex exposure martingale ${\displaystyle Y_{i}=\mathbf {E} [\chi (G)\mid X_{1},\ldots ,X_{i}]}$ where each ${\displaystyle X_{k}}$ exposes the induced subgraph of ${\displaystyle G}$ on vertex set ${\displaystyle [k]}$. A single vertex can always be given a new color so that the graph is properly colored, thus the bounded difference condition ${\displaystyle |Y_{i}-Y_{i-1}|\leq 1}$ is satisfied. Now apply the Azuma's inequality for the martingale ${\displaystyle Y_{1},\ldots ,Y_{n}}$ with respect to ${\displaystyle X_{1},\ldots ,X_{n}}$.
${\displaystyle \square }$

For ${\displaystyle t=\omega (1)}$, the theorem states that the chromatic number of a random graph is tightly concentrated around its mean. The proof gives no clue as to where the mean is. This actually shows how powerful the martingale inequalities are: we can prove that a distribution is concentrated to its expectation without actually knowing the expectation.

### Hoeffding's Inequality

The following theorem states the so-called Hoeffding's inequality. It is a generalized version of the Chernoff bounds. Recall that the Chernoff bounds hold for the sum of independent trials. When the random variables are not trials, the Hoeffding's inequality is useful, since it holds for the sum of any independent random variables whose ranges are bounded.

 Hoeffding's inequality Let ${\displaystyle X=\sum _{i=1}^{n}X_{i}}$, where ${\displaystyle X_{1},\ldots ,X_{n}}$ are independent random variables with ${\displaystyle a_{i}\leq X_{i}\leq b_{i}}$ for each ${\displaystyle 1\leq i\leq n}$. Let ${\displaystyle \mu =\mathbf {E} [X]}$. Then ${\displaystyle \Pr[|X-\mu |\geq t]\leq 2\exp \left(-{\frac {t^{2}}{2\sum _{i=1}^{n}(b_{i}-a_{i})^{2}}}\right).}$
Proof.
 Define the Doob martingale sequence ${\displaystyle Y_{i}=\mathbf {E} \left[\sum _{j=1}^{n}X_{j}\,{\Big |}\,X_{1},\ldots ,X_{i}\right]}$. Obviously ${\displaystyle Y_{0}=\mu }$ and ${\displaystyle Y_{n}=X}$. {\displaystyle {\begin{aligned}|Y_{i}-Y_{i-1}|&=\left|\mathbf {E} \left[\sum _{j=1}^{n}X_{j}\,{\Big |}\,X_{0},\ldots ,X_{i}\right]-\mathbf {E} \left[\sum _{j=1}^{n}X_{j}\,{\Big |}\,X_{0},\ldots ,X_{i-1}\right]\right|\\&=\left|\sum _{j=1}^{i}X_{i}+\sum _{j=i+1}^{n}\mathbf {E} [X_{j}]-\sum _{j=1}^{i-1}X_{i}-\sum _{j=i}^{n}\mathbf {E} [X_{j}]\right|\\&=\left|X_{i}-\mathbf {E} [X_{i}]\right|\\&\leq b_{i}-a_{i}\end{aligned}}} Apply Azuma's inequality for the martingale ${\displaystyle Y_{0},\ldots ,Y_{n}}$ with respect to ${\displaystyle X_{1},\ldots ,X_{n}}$, the Hoeffding's inequality is proved.
${\displaystyle \square }$

# The Bounded Difference Method

Combining Azuma's inequality with the construction of Doob martingales, we have the powerful Bounded Difference Method for concentration of measures.

## For arbitrary random variables

Given a sequence of random variables ${\displaystyle X_{1},\ldots ,X_{n}}$ and a function ${\displaystyle f}$. The Doob sequence constructs a martingale from them. Combining this construction with Azuma's inequality, we can get a very powerful theorem called "the method of averaged bounded differences" which bounds the concentration for arbitrary function on arbitrary random variables (not necessarily a martingale).

 Theorem (Method of averaged bounded differences) Let ${\displaystyle {\boldsymbol {X}}=(X_{1},\ldots ,X_{n})}$ be arbitrary random variables and let ${\displaystyle f}$ be a function of ${\displaystyle X_{0},X_{1},\ldots ,X_{n}}$ satisfying that, for all ${\displaystyle 1\leq i\leq n}$, ${\displaystyle |\mathbf {E} [f({\boldsymbol {X}})\mid X_{1},\ldots ,X_{i}]-\mathbf {E} [f({\boldsymbol {X}})\mid X_{1},\ldots ,X_{i-1}]|\leq c_{i},}$ Then {\displaystyle {\begin{aligned}\Pr \left[|f({\boldsymbol {X}})-\mathbf {E} [f({\boldsymbol {X}})]|\geq t\right]\leq 2\exp \left(-{\frac {t^{2}}{2\sum _{i=1}^{n}c_{i}^{2}}}\right).\end{aligned}}}
Proof.
 Define the Doob Martingale sequence ${\displaystyle Y_{0},Y_{1},\ldots ,Y_{n}}$ by setting ${\displaystyle Y_{0}=\mathbf {E} [f(X_{1},\ldots ,X_{n})]}$ and, for ${\displaystyle 1\leq i\leq n}$, ${\displaystyle Y_{i}=\mathbf {E} [f(X_{1},\ldots ,X_{n})\mid X_{1},\ldots ,X_{i}]}$. Then the above theorem is a restatement of the Azuma's inequality holding for ${\displaystyle Y_{0},Y_{1},\ldots ,Y_{n}}$.
${\displaystyle \square }$

## For independent random variables

The condition of bounded averaged differences is usually hard to check. This severely limits the usefulness of the method. To overcome this, we introduce a property which is much easier to check, called the Lipschitz condition.

 Definition (Lipschitz condition) A function ${\displaystyle f(x_{1},\ldots ,x_{n})}$ satisfies the Lipschitz condition, if for any ${\displaystyle x_{1},\ldots ,x_{n}}$ and any ${\displaystyle y_{i}}$, {\displaystyle {\begin{aligned}|f(x_{1},\ldots ,x_{i-1},x_{i},x_{i+1},\ldots ,x_{n})-f(x_{1},\ldots ,x_{i-1},y_{i},x_{i+1},\ldots ,x_{n})|\leq 1.\end{aligned}}}

In other words, the function satisfies the Lipschitz condition if an arbitrary change in the value of any one argument does not change the value of the function by more than 1.

The diference of 1 can be replaced by arbitrary constants, which gives a generalized version of Lipschitz condition.

 Definition (Lipschitz condition, general version) A function ${\displaystyle f(x_{1},\ldots ,x_{n})}$ satisfies the Lipschitz condition with constants ${\displaystyle c_{i}}$, ${\displaystyle 1\leq i\leq n}$, if for any ${\displaystyle x_{1},\ldots ,x_{n}}$ and any ${\displaystyle y_{i}}$, {\displaystyle {\begin{aligned}|f(x_{1},\ldots ,x_{i-1},x_{i},x_{i+1},\ldots ,x_{n})-f(x_{1},\ldots ,x_{i-1},y_{i},x_{i+1},\ldots ,x_{n})|\leq c_{i}.\end{aligned}}}

The following "method of bounded differences" can be developed for functions satisfying the Lipschitz condition. Unfortunately, in order to imply the condition of averaged bounded differences from the Lipschitz condition, we have to restrict the method to independent random variables.

 Corollary (Method of bounded differences) Let ${\displaystyle {\boldsymbol {X}}=(X_{1},\ldots ,X_{n})}$ be ${\displaystyle n}$ independent random variables and let ${\displaystyle f}$ be a function satisfying the Lipschitz condition with constants ${\displaystyle c_{i}}$, ${\displaystyle 1\leq i\leq n}$. Then {\displaystyle {\begin{aligned}\Pr \left[|f({\boldsymbol {X}})-\mathbf {E} [f({\boldsymbol {X}})]|\geq t\right]\leq 2\exp \left(-{\frac {t^{2}}{2\sum _{i=1}^{n}c_{i}^{2}}}\right).\end{aligned}}}
Proof.
 For convenience, we denote that ${\displaystyle {\boldsymbol {X}}_{[i,j]}=(X_{i},X_{i+1},\ldots ,X_{j})}$ for any ${\displaystyle 1\leq i\leq j\leq n}$. We first show that the Lipschitz condition with constants ${\displaystyle c_{i}}$, ${\displaystyle 1\leq i\leq n}$, implies another condition called the averaged Lipschitz condition (ALC): for any ${\displaystyle a_{i},b_{i}}$, ${\displaystyle 1\leq i\leq n}$, ${\displaystyle \left|\mathbf {E} \left[f({\boldsymbol {X}})\mid {\boldsymbol {X}}_{[1,i-1]},X_{i}=a_{i}\right]-\mathbf {E} \left[f({\boldsymbol {X}})\mid {\boldsymbol {X}}_{[1,i-1]},X_{i}=b_{i}\right]\right|\leq c_{i}.}$ And this condition implies the averaged bounded difference condition: for all ${\displaystyle 1\leq i\leq n}$, ${\displaystyle \left|\mathbf {E} \left[f({\boldsymbol {X}})\mid {\boldsymbol {X}}_{[1,i]}\right]-\mathbf {E} \left[f({\boldsymbol {X}})\mid {\boldsymbol {X}}_{[1,i-1]}\right]\right|\leq c_{i}.}$ Then by applying the method of averaged bounded differences, the corollary can be proved. For any ${\displaystyle a}$, by the law of total expectation, {\displaystyle {\begin{aligned}&\quad \,\mathbf {E} \left[f({\boldsymbol {X}})\mid {\boldsymbol {X}}_{[1,i-1]},X_{i}=a\right]\\&=\sum _{a_{i+1},\ldots ,a_{n}}\mathbf {E} \left[f({\boldsymbol {X}})\mid {\boldsymbol {X}}_{[1,i-1]},X_{i}=a,{\boldsymbol {X}}_{[i+1,n]}={\boldsymbol {a}}_{[i+1,n]}\right]\cdot \Pr \left[{\boldsymbol {X}}_{[i+1,n]}={\boldsymbol {a}}_{[i+1,n]}\mid {\boldsymbol {X}}_{[1,i-1]},X_{i}=a\right]\\&=\sum _{a_{i+1},\ldots ,a_{n}}\mathbf {E} \left[f({\boldsymbol {X}})\mid {\boldsymbol {X}}_{[1,i-1]},X_{i}=a,{\boldsymbol {X}}_{[i+1,n]}={\boldsymbol {a}}_{[i+1,n]}\right]\cdot \Pr \left[{\boldsymbol {X}}_{[i+1,n]}={\boldsymbol {a}}_{[i+1,n]}\right]\qquad ({\mbox{independence}})\\&=\sum _{a_{i+1},\ldots ,a_{n}}f({\boldsymbol {X}}_{[1,i-1]},a,{\boldsymbol {a}}_{[i+1,n]})\cdot \Pr \left[{\boldsymbol {X}}_{[i+1,n]}={\boldsymbol {a}}_{[i+1,n]}\right].\end{aligned}}} Let ${\displaystyle a=a_{i}}$ and ${\displaystyle b_{i}}$, and take the diference. Then {\displaystyle {\begin{aligned}&\quad \,\left|\mathbf {E} \left[f({\boldsymbol {X}})\mid {\boldsymbol {X}}_{[1,i-1]},X_{i}=a_{i}\right]-\mathbf {E} \left[f({\boldsymbol {X}})\mid {\boldsymbol {X}}_{[1,i-1]},X_{i}=b_{i}\right]\right|\\&=\left|\sum _{a_{i+1},\ldots ,a_{n}}\left(f({\boldsymbol {X}}_{[1,i-1]},a_{i},{\boldsymbol {a}}_{[i+1,n]})-f({\boldsymbol {X}}_{[1,i-1]},b_{i},{\boldsymbol {a}}_{[i+1,n]})\right)\Pr \left[{\boldsymbol {X}}_{[i+1,n]}={\boldsymbol {a}}_{[i+1,n]}\right]\right|\\&\leq \sum _{a_{i+1},\ldots ,a_{n}}\left|f({\boldsymbol {X}}_{[1,i-1]},a_{i},{\boldsymbol {a}}_{[i+1,n]})-f({\boldsymbol {X}}_{[1,i-1]},b_{i},{\boldsymbol {a}}_{[i+1,n]})\right|\Pr \left[{\boldsymbol {X}}_{[i+1,n]}={\boldsymbol {a}}_{[i+1,n]}\right]\\&\leq \sum _{a_{i+1},\ldots ,a_{n}}c_{i}\Pr \left[{\boldsymbol {X}}_{[i+1,n]}={\boldsymbol {a}}_{[i+1,n]}\right]\qquad ({\mbox{Lipschitz condition}})\\&=c_{i}.\end{aligned}}} Thus, the Lipschitz condition is transformed to the ALC. We then deduce the averaged bounded difference condition from ALC. By the law of total expectation, ${\displaystyle \mathbf {E} \left[f({\boldsymbol {X}})\mid {\boldsymbol {X}}_{[1,i-1]}\right]=\sum _{a}\mathbf {E} \left[f({\boldsymbol {X}})\mid {\boldsymbol {X}}_{[1,i-1]},X_{i}=a\right]\cdot \Pr[X_{i}=a\mid {\boldsymbol {X}}_{[1,i-1]}].}$ We can trivially write ${\displaystyle \mathbf {E} \left[f({\boldsymbol {X}})\mid {\boldsymbol {X}}_{[1,i]}\right]}$ as ${\displaystyle \mathbf {E} \left[f({\boldsymbol {X}})\mid {\boldsymbol {X}}_{[1,i]}\right]=\sum _{a}\mathbf {E} \left[f({\boldsymbol {X}})\mid {\boldsymbol {X}}_{[1,i]}\right]\cdot \Pr \left[X_{i}=a\mid {\boldsymbol {X}}_{[1,i-1]}\right].}$ Hence, the difference is {\displaystyle {\begin{aligned}&\quad \left|\mathbf {E} \left[f({\boldsymbol {X}})\mid {\boldsymbol {X}}_{[1,i]}\right]-\mathbf {E} \left[f({\boldsymbol {X}})\mid {\boldsymbol {X}}_{[1,i-1]}\right]\right|\\&=\left|\sum _{a}\left(\mathbf {E} \left[f({\boldsymbol {X}})\mid {\boldsymbol {X}}_{[1,i]}\right]-\mathbf {E} \left[f({\boldsymbol {X}})\mid {\boldsymbol {X}}_{[1,i-1]},X_{i}=a\right]\right)\cdot \Pr \left[X_{i}=a\mid {\boldsymbol {X}}_{[1,i-1]}\right]\right|\\&\leq \sum _{a}\left|\mathbf {E} \left[f({\boldsymbol {X}})\mid {\boldsymbol {X}}_{[1,i]}\right]-\mathbf {E} \left[f({\boldsymbol {X}})\mid {\boldsymbol {X}}_{[1,i-1]},X_{i}=a\right]\right|\cdot \Pr \left[X_{i}=a\mid {\boldsymbol {X}}_{[1,i-1]}\right]\\&\leq \sum _{a}c_{i}\Pr \left[X_{i}=a\mid {\boldsymbol {X}}_{[1,i-1]}\right]\qquad ({\mbox{due to ALC}})\\&=c_{i}.\end{aligned}}} The averaged bounded diference condition is implied. Applying the method of averaged bounded diferences, the corollary follows.
${\displaystyle \square }$

## Applications

### Occupancy problem

Throwing ${\displaystyle m}$ balls uniformly and independently at random to ${\displaystyle n}$ bins, we ask for the occupancies of bins by the balls. In particular, we are interested in the number of empty bins.

This problem can be described equivalently as follows. Let ${\displaystyle f:[m]\rightarrow [n]}$ be a uniform random function from ${\displaystyle [m]\rightarrow [n]}$. We ask for the number of ${\displaystyle i\in [n]}$ that ${\displaystyle f^{-1}(i)}$ is empty.

For any ${\displaystyle i\in [n]}$, let ${\displaystyle X_{i}}$ indicate the emptiness of bin ${\displaystyle i}$. Let ${\displaystyle X=\sum _{i=1}^{n}X_{i}}$ be the number of empty bins.

${\displaystyle \mathbf {E} [X_{i}]=\Pr[{\mbox{bin }}i{\mbox{ is empty}}]=\left(1-{\frac {1}{n}}\right)^{m}.}$

By the linearity of expectation,

${\displaystyle \mathbf {E} [X]=\sum _{i=1}^{n}\mathbf {E} [X_{i}]=n\left(1-{\frac {1}{n}}\right)^{m}.}$

We want to know how ${\displaystyle X}$ deviates from this expectation. The complication here is that ${\displaystyle X_{i}}$ are not independent. So we alternatively look at a sequence of independent random variables ${\displaystyle Y_{1},\ldots ,Y_{m}}$, where ${\displaystyle Y_{j}\in [n]}$ represents the bin into which the ${\displaystyle j}$th ball falls. Clearly ${\displaystyle X}$ is function of ${\displaystyle Y_{1},\ldots ,Y_{m}}$.

We than observe that changing the value of any ${\displaystyle Y_{i}}$ can change the value of ${\displaystyle X}$ by at most 1, because one ball can affect the emptiness of at most one bin. Thus as a function of independent random variables ${\displaystyle Y_{1},\ldots ,Y_{m}}$, ${\displaystyle X}$ satisfies the Lipschitz condition. Apply the method of bounded differences, it holds that

${\displaystyle \Pr \left[\left|X-n\left(1-{\frac {1}{n}}\right)^{m}\right|\geq t{\sqrt {m}}\right]=\Pr[|X-\mathbf {E} [X]|\geq t{\sqrt {m}}]\leq 2e^{-t^{2}/2}}$

Thus, for sufficiently large ${\displaystyle n}$ and ${\displaystyle m}$, the number of empty bins is tightly concentrated around ${\displaystyle n\left(1-{\frac {1}{n}}\right)^{m}\approx {\frac {n}{e^{m/n}}}}$

### Pattern Matching

Let ${\displaystyle {\boldsymbol {X}}=(X_{1},\ldots ,X_{n})}$ be a sequence of characters chosen independently and uniformly at random from an alphabet ${\displaystyle \Sigma }$, where ${\displaystyle m=|\Sigma |}$. Let ${\displaystyle \pi \in \Sigma ^{k}}$ be an arbitrarily fixed string of ${\displaystyle k}$ characters from ${\displaystyle \Sigma }$, called a pattern. Let ${\displaystyle Y}$ be the number of occurrences of the pattern ${\displaystyle \pi }$ as a substring of the random string ${\displaystyle X}$.

By the linearity of expectation, it is obvious that

${\displaystyle \mathbf {E} [Y]=(n-k+1)\left({\frac {1}{m}}\right)^{k}.}$

We now look at the concentration of ${\displaystyle Y}$. The complication again lies in the dependencies between the matches. Yet we will see that ${\displaystyle Y}$ is well tightly concentrated around its expectation if ${\displaystyle k}$ is relatively small compared to ${\displaystyle n}$.

For a fixed pattern ${\displaystyle \pi }$, the random variable ${\displaystyle Y}$ is a function of the independent random variables ${\displaystyle (X_{1},\ldots ,X_{n})}$. Any character ${\displaystyle X_{i}}$ participates in no more than ${\displaystyle k}$ matches, thus changing the value of any ${\displaystyle X_{i}}$ can affect the value of ${\displaystyle Y}$ by at most ${\displaystyle k}$. ${\displaystyle Y}$ satisfies the Lipschitz condition with constant ${\displaystyle k}$. Apply the method of bounded differences,

${\displaystyle \Pr \left[\left|Y-{\frac {n-k+1}{m^{k}}}\right|\geq tk{\sqrt {n}}\right]=\Pr \left[\left|Y-\mathbf {E} [Y]\right|\geq tk{\sqrt {n}}\right]\leq 2e^{-t^{2}/2}}$

### Combining unit vectors

Let ${\displaystyle u_{1},\ldots ,u_{n}}$ be ${\displaystyle n}$ unit vectors from some normed space. That is, ${\displaystyle \|u_{i}\|=1}$ for any ${\displaystyle 1\leq i\leq n}$, where ${\displaystyle \|\cdot \|}$ denote the vector norm (e.g. ${\displaystyle \ell _{1},\ell _{2},\ell _{\infty }}$) of the space.

Let ${\displaystyle \epsilon _{1},\ldots ,\epsilon _{n}\in \{-1,+1\}}$ be independently chosen and ${\displaystyle \Pr[\epsilon _{i}=-1]=\Pr[\epsilon _{i}=1]=1/2}$.

Let

${\displaystyle v=\epsilon _{1}u_{1}+\cdots +\epsilon _{n}u_{n},}$

and

${\displaystyle X=\|v\|.}$

This kind of construction is very useful in combinatorial proofs of metric problems. We will show that by this construction, the random variable ${\displaystyle X}$ is well concentrated around its mean.

${\displaystyle X}$ is a function of independent random variables ${\displaystyle \epsilon _{1},\ldots ,\epsilon _{n}}$. By the triangle inequality for norms, it is easy to verify that changing the sign of a unit vector ${\displaystyle u_{i}}$ can only change the value of ${\displaystyle X}$ for at most 2, thus ${\displaystyle X}$ satisfies the Lipschitz condition with constant 2. The concentration result follows by applying the method of bounded differences:

${\displaystyle \Pr[|X-\mathbf {E} [X]|\geq 2t{\sqrt {n}}]\leq 2e^{-t^{2}/2}.}$

# The Johnson-Lindenstrauss Theorem

Consider a problem as follows: We have a set of ${\displaystyle n}$ points in a high-dimensional Euclidean space ${\displaystyle \mathbf {R} ^{d}}$. We want to project the points onto a space of low dimension ${\displaystyle \mathbf {R} ^{k}}$ in such a way that pairwise distances of the points are approximately the same as before.

Formally, we are looking for a map ${\displaystyle f:\mathbf {R} ^{d}\rightarrow \mathbf {R} ^{k}}$ such that for any pair of original points ${\displaystyle u,v}$, ${\displaystyle \|f(u)-f(v)\|}$ distorts little from ${\displaystyle \|u-v\|}$, where ${\displaystyle \|\cdot \|}$ is the Euclidean norm, i.e. ${\displaystyle \|u-v\|={\sqrt {(u_{1}-v_{1})^{2}+(u_{2}-v_{2})^{2}+\ldots +(u_{d}-v_{d})^{2}}}}$ is the distance between ${\displaystyle u}$ and ${\displaystyle v}$ in Euclidean space.

This problem has various important applications in both theory and practice. In many tasks, the data points are drawn from a high dimensional space, however, computations on high-dimensional data are usually hard due to the infamous "curse of dimensionality". The computational tasks can be greatly eased if we can project the data points onto a space of low dimension while the pairwise relations between the points are approximately preserved.

The Johnson-Lindenstrauss Theorem states that it is possible to project ${\displaystyle n}$ points in a space of arbitrarily high dimension onto an ${\displaystyle O(\log n)}$-dimensional space, such that the pairwise distances between the points are approximately preserved.

 Johnson-Lindenstrauss Theorem For any ${\displaystyle 0<\epsilon <1}$ and any positive integer ${\displaystyle n}$, let ${\displaystyle k}$ be a positive integer such that ${\displaystyle k\geq 4(\epsilon ^{2}/2-\epsilon ^{3}/3)^{-1}\ln n}$ Then for any set ${\displaystyle V}$ of ${\displaystyle n}$ points in ${\displaystyle \mathbf {R} ^{d}}$, there is a map ${\displaystyle f:\mathbf {R} ^{d}\rightarrow \mathbf {R} ^{k}}$ such that for all ${\displaystyle u,v\in V}$, ${\displaystyle (1-\epsilon )\|u-v\|^{2}\leq \|f(u)-f(v)\|^{2}\leq (1+\epsilon )\|u-v\|^{2}}$. Furthermore, this map can be found in expected polynomial time.

The map ${\displaystyle f:\mathbf {R} ^{d}\rightarrow \mathbf {R} ^{k}}$ is done by random projection. There are several ways of applying the random projection. We adopt the one in the original Johnson-Lindenstrauss paper.

 The projection (due to Johnson-Lindenstrauss) Let ${\displaystyle A}$ be a random ${\displaystyle k\times d}$ matrix that projects ${\displaystyle \mathbf {R} ^{d}}$ onto a uniform random k-dimensional subspace. Multiply ${\displaystyle A}$ by a fixed scalar ${\displaystyle {\sqrt {\frac {d}{k}}}}$. For every ${\displaystyle v\in \mathbf {R} ^{d}}$, ${\displaystyle v}$ is mapped to ${\displaystyle {\sqrt {\frac {d}{k}}}Av}$.

The projected point ${\displaystyle {\sqrt {\frac {d}{k}}}Av}$ is a vector in ${\displaystyle \mathbf {R} ^{k}}$.

The purpose of multiplying the scalar ${\displaystyle {\sqrt {\frac {d}{k}}}}$ is to guarantee that ${\displaystyle \mathbf {E} \left[\left\|{\sqrt {\frac {d}{k}}}Av\right\|^{2}\right]=\|v\|^{2}}$.

Besides the uniform random subspace, there are other choices of random projections known to have good performances, including:

• A matrix whose entries follow i.i.d. normal distributions. (Due to Indyk-Motwani)
• A matrix whose entries are i.i.d. ${\displaystyle \pm 1}$. (Due to Achlioptas)

In both cases, the matrix is also multiplied by a fixed scalar for normalization.

We present a proof due to Dasgupta-Gupta, which is much simpler than the original proof of Johnson-Lindenstrauss. The proof is for the projection onto uniform random subspace. The idea of the proof is outlined as follows:

1. To bound the distortions to pairwise distances, it is sufficient to bound the distortions to the length of unit vectors.
2. A uniform random subspace of a fixed unit vector is identically distributed as a fixed subspace of a uniform random unit vector. We can fix the subspace as the first k coordinates of the vector, thus it is sufficient to bound the length (norm) of the first k coordinates of a uniform random unit vector.
3. Prove that for a uniform random unit vector, the length of its first k coordinates is concentrated to the expectation.
From pairwise distances to norms of unit vectors

Let ${\displaystyle w\in \mathbf {R} ^{d}}$ be a vector in the original space, the random ${\displaystyle k\times d}$ matrix ${\displaystyle A}$ projects ${\displaystyle w}$ onto a uniformly random k-dimensional subspace of ${\displaystyle \mathbf {R} ^{d}}$. We only need to show that

{\displaystyle {\begin{aligned}\Pr \left[\left\|{\sqrt {\frac {d}{k}}}Aw\right\|^{2}<(1-\epsilon )\|w\|^{2}\right]&\leq {\frac {1}{n^{2}}};\quad {\mbox{and}}\\\Pr \left[\left\|{\sqrt {\frac {d}{k}}}Aw\right\|^{2}>(1+\epsilon )\|w\|^{2}\right]&\leq {\frac {1}{n^{2}}}.\end{aligned}}}

Think of ${\displaystyle w}$ as a ${\displaystyle w=u-v}$ for some ${\displaystyle u,v\in V}$. Then by applying the union bound to all ${\displaystyle {n \choose 2}}$ pairs of the ${\displaystyle n}$ points in ${\displaystyle V}$, the random projection ${\displaystyle A}$ violates the distortion requirement with probability at most

${\displaystyle {n \choose 2}\cdot {\frac {2}{n^{2}}}=1-{\frac {1}{n}},}$

so ${\displaystyle A}$ has the desirable low-distortion with probability at least ${\displaystyle {\frac {1}{n}}}$. Thus, the low-distortion embedding can be found by trying for expected ${\displaystyle n}$ times (recalling the analysis fo geometric distribution).

We can further simplify the problem by normalizing the ${\displaystyle w}$. Note that for nonzero ${\displaystyle w}$'s, the statement that

${\displaystyle (1-\epsilon )\|w\|^{2}\leq \left\|{\sqrt {\frac {d}{k}}}Aw\right\|^{2}\leq (1+\epsilon )\|w\|^{2}}$

is equivalent to that

${\displaystyle (1-\epsilon ){\frac {k}{d}}\leq \left\|A\left({\frac {w}{\|w\|}}\right)\right\|^{2}\leq (1+\epsilon ){\frac {k}{d}}.}$

Thus, we only need to bound the distortions for the unit vectors, i.e. the vectors ${\displaystyle w\in \mathbf {R} ^{d}}$ that ${\displaystyle \|w\|=1}$. The rest of the proof is to prove the following lemma for the unit vector in ${\displaystyle \mathbf {R} ^{d}}$.

 Lemma 3.1 For any unit vector ${\displaystyle w\in \mathbf {R} ^{d}}$, it holds that ${\displaystyle \Pr \left[\|Aw\|^{2}<(1-\epsilon ){\frac {k}{d}}\right]\leq {\frac {1}{n^{2}}};}$ ${\displaystyle \Pr \left[\|Aw\|^{2}>(1+\epsilon ){\frac {k}{d}}\right]\leq {\frac {1}{n^{2}}}.}$

As we argued above, this lemma implies the Johnson-Lindenstrauss Theorem.

Random projection of fixed unit vector ${\displaystyle \equiv }$ fixed projection of random unit vector

Let ${\displaystyle w\in \mathbf {R} ^{d}}$ be a fixed unit vector in ${\displaystyle \mathbf {R} ^{d}}$. Let ${\displaystyle A}$ be a random matrix which projects the points in ${\displaystyle \mathbf {R} ^{d}}$ onto a uniformly random ${\displaystyle k}$-dimensional subspace of ${\displaystyle \mathbf {R} ^{d}}$.

Let ${\displaystyle Y\in \mathbf {R} ^{d}}$ be a uniformly random unit vector in ${\displaystyle \mathbf {R} ^{d}}$. Let ${\displaystyle B}$ be such a fixed matrix which extracts the first ${\displaystyle k}$ coordinates of the vectors in ${\displaystyle \mathbf {R} ^{d}}$, i.e. for any ${\displaystyle Y=(Y_{1},Y_{2},\ldots ,Y_{d})}$, ${\displaystyle BY=(Y_{1},Y_{2},\ldots ,Y_{k})}$.

In other words, ${\displaystyle Aw}$ is a random projection of a fixed unit vector; and ${\displaystyle BY}$ is a fixed projection of a uniformly random unit vector.

A key observation is that:

 Observation The distribution of ${\displaystyle \|Aw\|}$ is the same as the distribution of ${\displaystyle \|BY\|}$.

The proof of this observation is omitted here.

With this observation, it is sufficient to work on the subspace of the first ${\displaystyle k}$ coordinates of the uniformly random unit vector ${\displaystyle Y\in \mathbf {R} ^{d}}$. Our task is now reduced to the following lemma.

 Lemma 3.2 Let ${\displaystyle Y=(Y_{1},Y_{2},\ldots ,Y_{d})}$ be a uniformly random unit vector in ${\displaystyle \mathbf {R} ^{d}}$. Let ${\displaystyle Z=(Y_{1},Y_{2},\ldots ,Y_{k})}$ be the projection of ${\displaystyle Y}$ to the subspace of the first ${\displaystyle k}$-coordinates of ${\displaystyle \mathbf {R} ^{d}}$. Then ${\displaystyle \Pr \left[\|Z\|^{2}<(1-\epsilon ){\frac {k}{d}}\right]\leq {\frac {1}{n^{2}}};}$ ${\displaystyle \Pr \left[\|Z\|^{2}>(1+\epsilon ){\frac {k}{d}}\right]\leq {\frac {1}{n^{2}}}.}$

Due to the above observation, Lemma 3.2 implies Lemma 3.1 and thus proves the Johnson-Lindenstrauss theorem.

Note that ${\displaystyle \|Z\|^{2}=\sum _{i=1}^{k}Y_{i}^{2}}$. Due to the linearity of expectations,

${\displaystyle \mathbf {E} [\|Z\|^{2}]=\sum _{i=1}^{k}\mathbf {E} [Y_{i}^{2}]}$.

Since ${\displaystyle Y}$ is a uniform random unit vector, it holds that ${\displaystyle \sum _{i=1}^{d}Y_{i}^{2}=\|Y\|^{2}=1}$. And due to the symmetry, all ${\displaystyle \mathbf {E} [Y_{i}^{2}]}$'s are equal. Thus, ${\displaystyle \mathbf {E} [Y_{i}^{2}]={\frac {1}{d}}}$ for all ${\displaystyle i}$. Therefore,

${\displaystyle \mathbf {E} [\|Z\|^{2}]=\sum _{i=1}^{k}\mathbf {E} [Y_{i}^{2}]={\frac {k}{d}}}$.

Lemma 3.2 actually states that ${\displaystyle \|Z\|^{2}}$ is well-concentrated to its expectation.

Concentration of the norm of the first ${\displaystyle k}$ entries of uniform random unit vector

We now prove Lemma 3.2. Specifically, we will prove the ${\displaystyle (1-\epsilon )}$ direction:

${\displaystyle \Pr[\|Z\|^{2}<(1-\epsilon ){\frac {k}{d}}]\leq {\frac {1}{n^{2}}}}$.

The ${\displaystyle (1+\epsilon )}$ direction is proved with the same argument.

Due to the discussion in the last section, this can be interpreted as a concentration bound for ${\displaystyle \|Z\|^{2}}$, which is a sum of ${\displaystyle Y_{1}^{2},Y_{2}^{2},\ldots ,Y_{k}^{2}}$. This hints us to use Chernoff-like bounds. However, for uniformly random unit vector ${\displaystyle Y}$, ${\displaystyle Y_{i}}$'s are not independent (because of the constraint that ${\displaystyle \|Y\|=1}$). We overcome this by generating uniform unit vectors from independent normal distributions.

The following is a very useful fact regarding the generation of uniform unit vectors.

 Generating uniform unit vector Let ${\displaystyle X_{1},X_{2},\ldots ,X_{d}}$ be i.i.d. random variables, each drawn from the normal distribution ${\displaystyle N(0,1)}$. Let ${\displaystyle X=(X_{1},X_{2},\ldots ,X_{d})}$. Then ${\displaystyle Y={\frac {1}{\|X\|}}X}$ is a uniformly random unit vector.

Then for ${\displaystyle Z=(Y_{1},Y_{2},\ldots ,Z_{k})}$,

${\displaystyle \|Z\|^{2}=Y_{1}^{2}+Y_{2}^{2}+\cdots +Y_{k}^{2}={\frac {X_{1}^{2}}{\|X\|^{2}}}+{\frac {X_{2}^{2}}{\|X\|^{2}}}+\cdots +{\frac {X_{k}^{2}}{\|X\|^{2}}}={\frac {X_{1}^{2}+X_{2}^{2}+\cdots +X_{k}^{2}}{X_{1}^{2}+X_{2}^{2}+\cdots +X_{d}^{2}}}}$.

To avoid writing a lot of ${\displaystyle (1-\epsilon )}$'s. We write ${\displaystyle \beta =(1-\epsilon )}$. The first inequality (the lower tail) of Lemma 3.2 can be written as:

{\displaystyle {\begin{aligned}\Pr \left[\|Z\|^{2}<{\frac {\beta k}{d}}\right]&=\Pr \left[{\frac {X_{1}^{2}+X_{2}^{2}+\cdots +X_{k}^{2}}{X_{1}^{2}+X_{2}^{2}+\cdots +X_{d}^{2}}}<{\frac {\beta k}{d}}\right]\\&=\Pr \left[d(X_{1}^{2}+X_{2}^{2}+\cdots +X_{k}^{2})<\beta k(X_{1}^{2}+X_{2}^{2}+\cdots +X_{d}^{2})\right]\\&=\Pr \left[(\beta k-d)\sum _{i=1}^{k}X_{i}^{2}+\beta k\sum _{i=k+1}^{d}X_{i}^{2}>0\right].&\qquad (**)\end{aligned}}}

The probability is a tail probability of the sum of ${\displaystyle d}$ independent variables. The ${\displaystyle X_{i}^{2}}$'s are not 0-1 variables, thus we cannot directly apply the Chernoff bounds. However, the following two key ingredients of the Chernoff bounds are satisfiable for the above sum:

• The ${\displaystyle X_{i}^{2}}$'s are independent.
• Because ${\displaystyle X_{i}^{2}}$'s are normal, it is known that the moment generating functions for ${\displaystyle X_{i}^{2}}$'s can be computed as follows:
 Fact 3.3 If ${\displaystyle X}$ follows the normal distribution ${\displaystyle N(0,1)}$, then ${\displaystyle \mathbf {E} \left[e^{\lambda X^{2}}\right]=(1-2\lambda )^{-{\frac {1}{2}}}}$, for ${\displaystyle \lambda \in \left(-\infty ,1/2\right)}$

Therefore, we can re-apply the technique of the Chernoff bound (applying Markov's inequality to the moment generating function and optimizing the parameter ${\displaystyle \lambda }$) to bound the probability ${\displaystyle (**)}$:

{\displaystyle {\begin{aligned}&\quad \,\Pr \left[(\beta k-d)\sum _{i=1}^{k}X_{i}^{2}+\beta k\sum _{i=k+1}^{d}X_{i}^{2}>0\right]\\&=\Pr \left[\exp \left\{(\beta k-d)\sum _{i=1}^{k}X_{i}^{2}+\beta k\sum _{i=k+1}^{d}X_{i}^{2}\right\}>1\right]\\&=\Pr \left[\exp \left\{\lambda \left((\beta k-d)\sum _{i=1}^{k}X_{i}^{2}+\beta k\sum _{i=k+1}^{d}X_{i}^{2}\right)\right\}>1\right]&\quad ({\text{for }}\lambda >0)\\&\leq \mathbf {E} \left[\exp \left\{\lambda \left((\beta k-d)\sum _{i=1}^{k}X_{i}^{2}+\beta k\sum _{i=k+1}^{d}X_{i}^{2}\right)\right\}\right]&\quad {\text{(by Markov inequality)}}\\&=\prod _{i=1}^{k}\mathbf {E} \left[e^{\lambda (\beta k-d)X_{i}^{2}}\right]\cdot \prod _{i=k+1}^{d}\mathbf {E} \left[e^{\lambda \beta kX_{i}^{2}}\right]&\quad ({\text{independence of }}X_{i})\\&=\mathbf {E} \left[e^{\lambda (\beta k-d)X_{1}^{2}}\right]^{k}\cdot \mathbf {E} \left[e^{\lambda \beta kX_{1}^{2}}\right]^{d-k}&\quad {\text{(symmetry)}}\\&=(1-2\lambda (\beta k-d))^{-{\frac {k}{2}}}(1-2\lambda \beta k)^{-{\frac {d-k}{2}}}&\quad {\text{(by Fact 3.3)}}\end{aligned}}}

The last term ${\displaystyle (1-2\lambda (\beta k-d))^{-{\frac {k}{2}}}(1-2\lambda \beta k)^{-{\frac {d-k}{2}}}}$ is minimized when

${\displaystyle \lambda ={\frac {1-\beta }{2\beta (d-k\beta )}},}$

so that

{\displaystyle {\begin{aligned}&\quad \,(1-2\lambda (\beta k-d))^{-{\frac {k}{2}}}(1-2\lambda \beta k)^{-{\frac {d-k}{2}}}\\&=\beta ^{\frac {k}{2}}\left(1+{\frac {(1-\beta )k}{(d-k)}}\right)^{\frac {d-k}{2}}\\&\leq \exp \left({\frac {k}{2}}(1-\beta +\ln \beta )\right)&\qquad ({\text{since }}\left(1+{\frac {(1-\beta )k}{(d-k)}}\right)^{\frac {d-k}{(1-\beta )k}}\leq e)\\&=\exp \left({\frac {k}{2}}(\epsilon +\ln(1-\epsilon ))\right)&\qquad (\beta =1-\epsilon )\\&\leq \exp \left(-{\frac {k\epsilon ^{2}}{4}}\right)&\qquad ({\text{by Taylor expansion }}\ln(1-\epsilon )\leq -\epsilon -{\frac {\epsilon ^{2}}{2}}),\end{aligned}}}

which is is ${\displaystyle \leq {\frac {1}{n^{2}}}}$ for the choice of k in the Johnson-Lindenstrauss theorem that

${\displaystyle k\geq 4(\epsilon ^{2}/2-\epsilon ^{3}/3)^{-1}\ln n}$.

So we have proved that

${\displaystyle \Pr[\|Z\|^{2}<(1-\epsilon ){\frac {k}{d}}]\leq {\frac {1}{n^{2}}}}$.

With the same argument, the other direction can be proved so that

${\displaystyle \Pr[\|Z\|^{2}>(1+\epsilon ){\frac {k}{d}}]\leq \exp \left({\frac {k}{2}}(-\epsilon +\ln(1+\epsilon ))\right)\leq \exp \left(-{\frac {k(\epsilon ^{2}/2-\epsilon ^{3}/3)}{2}}\right)}$,

which is also ${\displaystyle \leq {\frac {1}{n^{2}}}}$ for ${\displaystyle k\geq 4(\epsilon ^{2}/2-\epsilon ^{3}/3)^{-1}\ln n}$.

Lemma 3.2 is proved. As we discussed in the previous sections, Lemma 3.2 implies Lemma 3.1, which implies the Johnson-Lindenstrauss theorem.