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

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

Example: 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.
Example: 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.

## Azuma's inequality -- general version

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 is almost identical to the proof of the original Azuma's inequality. We also work on the sum of the martingale differences (this time the differences are ${\displaystyle (Y_{i}-Y_{i-1})}$), yet conditioning on ${\displaystyle X_{0},\ldots ,X_{n-1}}$. The rest of the proof proceeds in the same way.

Application: 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.

Application: 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 }$

# 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}.}$