Difference between revisions of "高级算法 (Fall 2019)/Concentration of measure"

From EtoneWiki
Jump to: navigation, search
(Created page with "= Conditional Expectations = The '''conditional expectation''' of a random variable <math>Y</math> with respect to an event <math>\mathcal{E}</math> is defined by :<math> \mat...")
 
(The Bounded Difference Method)
 
(9 intermediate revisions by the same user not shown)
Line 1: Line 1:
= Conditional Expectations =
+
=Chernoff Bound=
The '''conditional expectation''' of a random variable <math>Y</math> with respect to an event <math>\mathcal{E}</math> is defined by
+
 
 +
Suppose that we have a fair coin. If we toss it once, then the outcome is completely unpredictable. But if we toss it, say for 1000 times, then the number of HEADs is very likely to be around 500. This phenomenon, as illustrated in the following figure, is called the '''concentration''' of measure. The Chernoff bound is an inequality that characterizes the concentration phenomenon for the sum of independent trials.
 +
 
 +
[[File:Coinflip.png|border|450px|center]]
 +
 
 +
Before formally stating the Chernoff bound, let's introduce the '''moment generating function'''.
 +
 
 +
== Moment generating functions ==
 +
The more we know about the moments of a random variable <math>X</math>, the more information we would have about <math>X</math>. There is a so-called '''moment generating function''', which "packs" all the information about the moments of <math>X</math> into one function.
 +
 
 +
{{Theorem
 +
|Definition|
 +
:The moment generating function of a random variable <math>X</math> is defined as <math>\mathbf{E}\left[\mathrm{e}^{\lambda X}\right]</math> where <math>\lambda</math> is the parameter of the function.
 +
}}
 +
 
 +
By Taylor's expansion and the linearity of expectations,
 +
:<math>\begin{align}
 +
\mathbf{E}\left[\mathrm{e}^{\lambda X}\right]
 +
&=
 +
\mathbf{E}\left[\sum_{k=0}^\infty\frac{\lambda^k}{k!}X^k\right]\\
 +
&=\sum_{k=0}^\infty\frac{\lambda^k}{k!}\mathbf{E}\left[X^k\right]
 +
\end{align}</math>
 +
 
 +
The moment generating function <math>\mathbf{E}\left[\mathrm{e}^{\lambda X}\right]</math> is a function of <math>\lambda</math>.
 +
 
 +
== The Chernoff bound ==
 +
The Chernoff bounds are exponentially sharp tail inequalities for the sum of independent trials.
 +
The bounds are obtained by applying Markov's inequality to the moment generating function of the sum of independent trials, with some  appropriate choice of the parameter <math>\lambda</math>.
 +
{{Theorem
 +
|Chernoff bound (the upper tail)|
 +
:Let  <math>X=\sum_{i=1}^n X_i</math>, where <math>X_1, X_2, \ldots, X_n</math> are independent Poisson trials. Let <math>\mu=\mathbf{E}[X]</math>.
 +
:Then for any <math>\delta>0</math>,
 +
::<math>\Pr[X\ge (1+\delta)\mu]\le\left(\frac{e^{\delta}}{(1+\delta)^{(1+\delta)}}\right)^{\mu}.</math>
 +
}}
 +
{{Proof| For any <math>\lambda>0</math>, <math>X\ge (1+\delta)\mu</math> is equivalent to that <math>e^{\lambda X}\ge e^{\lambda (1+\delta)\mu}</math>, thus
 +
:<math>\begin{align}
 +
\Pr[X\ge (1+\delta)\mu]
 +
&=
 +
\Pr\left[e^{\lambda X}\ge e^{\lambda (1+\delta)\mu}\right]\\
 +
&\le
 +
\frac{\mathbf{E}\left[e^{\lambda X}\right]}{e^{\lambda (1+\delta)\mu}},
 +
\end{align}</math>
 +
where the last step follows by Markov's inequality.
 +
 
 +
Computing the moment generating function <math>\mathbf{E}[e^{\lambda X}]</math>:
 +
:<math>\begin{align}
 +
\mathbf{E}\left[e^{\lambda X}\right]
 +
&=
 +
\mathbf{E}\left[e^{\lambda \sum_{i=1}^n X_i}\right]\\
 +
&=
 +
\mathbf{E}\left[\prod_{i=1}^n e^{\lambda X_i}\right]\\
 +
&=
 +
\prod_{i=1}^n \mathbf{E}\left[e^{\lambda X_i}\right].
 +
& (\mbox{for independent random variables})
 +
\end{align}</math>
 +
 
 +
Let <math>p_i=\Pr[X_i=1]</math> for <math>i=1,2,\ldots,n</math>. Then,
 +
:<math>\mu=\mathbf{E}[X]=\mathbf{E}\left[\sum_{i=1}^n X_i\right]=\sum_{i=1}^n\mathbf{E}[X_i]=\sum_{i=1}^n p_i</math>.
 +
 
 +
We bound the moment generating function for each individual <math>X_i</math> as follows.
 +
:<math>\begin{align}
 +
\mathbf{E}\left[e^{\lambda X_i}\right]
 +
&=
 +
p_i\cdot e^{\lambda\cdot 1}+(1-p_i)\cdot e^{\lambda\cdot 0}\\
 +
&=
 +
1+p_i(e^\lambda -1)\\
 +
&\le
 +
e^{p_i(e^\lambda-1)},
 +
\end{align}</math>
 +
where in the last step we apply the Taylor's expansion so that <math>e^y\ge 1+y</math> where <math>y=p_i(e^\lambda-1)\ge 0</math>. (By doing this, we can transform the product to the sum of <math>p_i</math>, which is <math>\mu</math>.)
 +
 
 +
Therefore,
 +
:<math>\begin{align}
 +
\mathbf{E}\left[e^{\lambda X}\right]
 +
&=
 +
\prod_{i=1}^n \mathbf{E}\left[e^{\lambda X_i}\right]\\
 +
&\le
 +
\prod_{i=1}^n e^{p_i(e^\lambda-1)}\\
 +
&=
 +
\exp\left(\sum_{i=1}^n p_i(e^{\lambda}-1)\right)\\
 +
&=
 +
e^{(e^\lambda-1)\mu}.
 +
\end{align}</math>
 +
Thus, we have shown that for any <math>\lambda>0</math>,
 +
:<math>\begin{align}
 +
\Pr[X\ge (1+\delta)\mu]
 +
&\le
 +
\frac{\mathbf{E}\left[e^{\lambda X}\right]}{e^{\lambda (1+\delta)\mu}}\\
 +
&\le
 +
\frac{e^{(e^\lambda-1)\mu}}{e^{\lambda (1+\delta)\mu}}\\
 +
&=
 +
\left(\frac{e^{(e^\lambda-1)}}{e^{\lambda (1+\delta)}}\right)^\mu
 +
\end{align}</math>.
 +
For any <math>\delta>0</math>, we can let <math>\lambda=\ln(1+\delta)>0</math> to get
 +
:<math>\Pr[X\ge (1+\delta)\mu]\le\left(\frac{e^{\delta}}{(1+\delta)^{(1+\delta)}}\right)^{\mu}.</math>
 +
}}
 +
 
 +
The idea of the proof is actually quite clear: we apply Markov's inequality to <math>e^{\lambda X}</math> and for the rest, we just estimate the moment generating function <math>\mathbf{E}[e^{\lambda X}]</math>. To make the bound as tight as possible, we minimized the <math>\frac{e^{(e^\lambda-1)}}{e^{\lambda (1+\delta)}}</math> by setting <math>\lambda=\ln(1+\delta)</math>, which can be justified by taking derivatives of <math>\frac{e^{(e^\lambda-1)}}{e^{\lambda (1+\delta)}}</math>.
 +
 
 +
----
 +
 
 +
We then proceed to the lower tail, the probability that the random variable deviates below the mean value:
 +
 
 +
{{Theorem
 +
|Chernoff bound (the lower tail)|
 +
:Let  <math>X=\sum_{i=1}^n X_i</math>, where <math>X_1, X_2, \ldots, X_n</math> are independent Poisson trials. Let <math>\mu=\mathbf{E}[X]</math>.
 +
:Then for any <math>0<\delta<1</math>,
 +
::<math>\Pr[X\le (1-\delta)\mu]\le\left(\frac{e^{-\delta}}{(1-\delta)^{(1-\delta)}}\right)^{\mu}.</math>
 +
}}
 +
{{Proof| For any <math>\lambda<0</math>, by the same analysis as in the upper tail version,
 +
:<math>\begin{align}
 +
\Pr[X\le (1-\delta)\mu]
 +
&=
 +
\Pr\left[e^{\lambda X}\ge e^{\lambda (1-\delta)\mu}\right]\\
 +
&\le
 +
\frac{\mathbf{E}\left[e^{\lambda X}\right]}{e^{\lambda (1-\delta)\mu}}\\
 +
&\le
 +
\left(\frac{e^{(e^\lambda-1)}}{e^{\lambda (1-\delta)}}\right)^\mu.
 +
\end{align}</math>
 +
For any <math>0<\delta<1</math>, we can let <math>\lambda=\ln(1-\delta)<0</math> to get
 +
:<math>\Pr[X\ge (1-\delta)\mu]\le\left(\frac{e^{-\delta}}{(1-\delta)^{(1-\delta)}}\right)^{\mu}.</math>
 +
}}
 +
 
 +
== Useful forms of the Chernoff bounds==
 +
Some useful special forms of the bounds can be derived directly from the above general forms of the bounds. We now know better why we say that the bounds are exponentially sharp.
 +
 
 +
{{Theorem
 +
|Useful forms of the Chernoff bound|
 +
:Let  <math>X=\sum_{i=1}^n X_i</math>, where <math>X_1, X_2, \ldots, X_n</math> are independent Poisson trials. Let <math>\mu=\mathbf{E}[X]</math>. Then
 +
:1. for <math>0<\delta\le 1</math>,
 +
::<math>\Pr[X\ge (1+\delta)\mu]<\exp\left(-\frac{\mu\delta^2}{3}\right);</math>
 +
::<math>\Pr[X\le (1-\delta)\mu]<\exp\left(-\frac{\mu\delta^2}{2}\right);</math>
 +
:2. for <math>t\ge 2e\mu</math>,
 +
::<math>\Pr[X\ge t]\le 2^{-t}.</math>
 +
}}
 +
{{Proof| To obtain the bounds in (1), we need to show that for <math>0<\delta< 1</math>, <math>\frac{e^{\delta}}{(1+\delta)^{(1+\delta)}}\le e^{-\delta^2/3}</math> and <math>\frac{e^{-\delta}}{(1-\delta)^{(1-\delta)}}\le e^{-\delta^2/2}</math>. We can verify both inequalities by standard analysis techniques.
 +
 
 +
To obtain the bound in (2), let <math>t=(1+\delta)\mu</math>. Then <math>\delta=t/\mu-1\ge 2e-1</math>. Hence,
 +
:<math>\begin{align}
 +
\Pr[X\ge(1+\delta)\mu]
 +
&\le
 +
\left(\frac{e^\delta}{(1+\delta)^{(1+\delta)}}\right)^\mu\\
 +
&\le
 +
\left(\frac{e}{1+\delta}\right)^{(1+\delta)\mu}\\
 +
&\le
 +
\left(\frac{e}{2e}\right)^t\\
 +
&\le
 +
2^{-t}
 +
\end{align}</math>
 +
}}
 +
 
 +
== Applications to balls-into-bins ==
 +
Throwing <math>m</math> balls uniformly and independently to <math>n</math> bins, what is the maximum load of all bins with high probability? In the last class, we gave an analysis of this problem by using a counting argument.
 +
 
 +
Now we give a more "advanced" analysis by using Chernoff bounds.
 +
 
 +
 
 +
For any <math>i\in[n]</math> and <math>j\in[m]</math>, let <math>X_{ij}</math> be the indicator variable for the event that ball <math>j</math> is thrown to bin <math>i</math>. Obviously
 +
:<math>\mathbf{E}[X_{ij}]=\Pr[\mbox{ball }j\mbox{ is thrown to bin }i]=\frac{1}{n}</math>
 +
Let <math>Y_i=\sum_{j\in[m]}X_{ij}</math> be the load of bin <math>i</math>.
 +
 
 +
 
 +
Then the expected load of bin <math>i</math> is
 +
 
 +
<math>(*)\qquad  \mu=\mathbf{E}[Y_i]=\mathbf{E}\left[\sum_{j\in[m]}X_{ij}\right]=\sum_{j\in[m]}\mathbf{E}[X_{ij}]=m/n.  </math>
 +
 
 +
For the case <math>m=n</math>, it holds that <math>\mu=1</math>
 +
 
 +
Note that <math>Y_i</math> is a sum of <math>m</math> mutually independent indicator variable. Applying Chernoff bound, for any particular bin <math>i\in[n]</math>,
 +
:<math>
 +
\Pr[Y_i>(1+\delta)\mu] \le \left(\frac{e^{\delta}}{(1+\delta)^{1+\delta}}\right)^\mu.
 +
</math>
 +
 
 +
=== The <math>m=n</math> case ===
 +
 
 +
When <math>m=n</math>, <math>\mu=1</math>. Write <math>c=1+\delta</math>. The above bound can be written as
 +
:<math>
 +
\Pr[Y_i>c] \le \frac{e^{c-1}}{c^c}.
 +
</math>
 +
 
 +
Let <math>c=\frac{e\ln n}{\ln\ln n}</math>, we evaluate <math>\frac{e^{c-1}}{c^c}</math> by taking logarithm to its reciprocal.
 +
:<math>
 +
\begin{align}
 +
\ln\left(\frac{c^c}{e^{c-1}}\right)
 +
&=
 +
c\ln c-c+1\\
 +
&=
 +
c(\ln c-1)+1\\
 +
&=
 +
\frac{e\ln n}{\ln\ln n}\left(\ln\ln n-\ln\ln\ln n\right)+1\\
 +
&\ge
 +
\frac{e\ln n}{\ln\ln n}\cdot\frac{2}{e}\ln\ln n+1\\
 +
&\ge
 +
2\ln n.
 +
\end{align}
 +
</math>
 +
Thus,
 +
:<math>
 +
\Pr\left[Y_i>\frac{e\ln n}{\ln\ln n}\right] \le \frac{1}{n^2}.
 +
</math>
 +
 
 +
Applying the union bound, the probability that there exists a bin with load <math>>12\ln n</math> is
 +
:<math>n\cdot \Pr\left[Y_1>\frac{e\ln n}{\ln\ln n}\right] \le \frac{1}{n}</math>.
 +
Therefore, for <math>m=n</math>, with high probability, the maximum load is <math>O\left(\frac{e\ln n}{\ln\ln n}\right)</math>.
 +
 
 +
=== The <math>m> \ln n</math> case===
 +
When <math>m\ge n\ln n</math>, then according to <math>(*)</math>, <math>\mu=\frac{m}{n}\ge \ln n</math>
 +
 
 +
We can apply an easier form of the Chernoff bounds,
 +
:<math>
 +
\Pr[Y_i\ge 2e\mu]\le 2^{-2e\mu}\le 2^{-2e\ln n}<\frac{1}{n^2}.
 +
</math>
 +
By the union bound, the probability that there exists a bin with load <math>\ge 2e\frac{m}{n}</math> is,
 +
:<math>n\cdot \Pr\left[Y_1>2e\frac{m}{n}\right] = n\cdot \Pr\left[Y_1>2e\mu\right]\le \frac{1}{n}</math>.
 +
Therefore, for <math>m\ge n\ln n</math>, with high probability, the maximum load is <math>O\left(\frac{m}{n}\right)</math>.
 +
 
 +
= 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 <math>n</math> losses, if the <math>(n+1)</math>th bet wins, then it gives a net profit of
 +
:<math>
 +
2^n-\sum_{i=1}^{n}2^{i-1}=1,
 +
</math>
 +
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 <math>X_0,X_1,\ldots,</math>, where <math>X_0</math> is his initial capital, and <math>X_i</math> represents his capital after the <math>i</math>th betting. Up to different betting strategies, <math>X_i</math> can be arbitrarily dependent on <math>X_0,\ldots,X_{i-1}</math>. However, as long as the game is fair, namely, winning and losing with equal chances, conditioning on the past variables <math>X_0,\ldots,X_{i-1}</math>, we will expect no change in the value of the present variable <math>X_{i}</math> on average. Random variables satisfying this property is called a '''martingale''' sequence.
 +
 
 +
{{Theorem
 +
|Definition (martingale)|
 +
:A sequence of random variables <math>X_0,X_1,\ldots</math> is a '''martingale''' if for all <math>i> 0</math>,
 +
:: <math>\begin{align}
 +
\mathbf{E}[X_{i}\mid X_0,\ldots,X_{i-1}]=X_{i-1}.
 +
\end{align}</math>
 +
}}
 +
 
 +
The martingale can be generalized to be with respect to another sequence of random variables.
 +
{{Theorem
 +
|Definition (martingale, general version)|
 +
:A sequence of random variables <math>Y_0,Y_1,\ldots</math> is a martingale with respect to the sequence <math>X_0,X_1,\ldots</math> if, for all <math>i\ge 0</math>, the following conditions hold:
 +
:* <math>Y_i</math> is a function of <math>X_0,X_1,\ldots,X_i</math>;
 +
:* <math>\begin{align}
 +
\mathbf{E}[Y_{i+1}\mid X_0,\ldots,X_{i}]=Y_{i}.
 +
\end{align}</math>
 +
}}
 +
Therefore, a sequence <math>X_0,X_1,\ldots</math> 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==
 +
 
 +
The Azuma's inequality is a martingale tail inequality.
 +
 
 +
{{Theorem
 +
|Azuma's Inequality|
 +
:Let <math>X_0,X_1,\ldots</math> be a martingale such that, for all <math>k\ge 1</math>,
 +
::<math>
 +
|X_{k}-X_{k-1}|\le c_k,
 +
</math>
 +
:Then
 +
::<math>\begin{align}
 +
\Pr\left[|X_n-X_0|\ge t\right]\le 2\exp\left(-\frac{t^2}{2\sum_{k=1}^nc_k^2}\right).
 +
\end{align}</math>
 +
}}
 +
Unlike the Chernoff bounds, there is no assumption of independence, which makes the martingale inequalities more useful.
 +
 
 +
The following '''bounded difference condition'''
 +
:<math>
 +
|X_{k}-X_{k-1}|\le c_k
 +
</math>
 +
says that the martingale <math>X_0,X_1,\ldots</math> as a process evolving over time, never makes big change in a single step.
 +
 
 +
The Azuma's inequality says that for any martingale satisfying the bounded difference condition, 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.
 +
 
 +
{{Theorem
 +
|Corollary|
 +
:Let <math>X_0,X_1,\ldots</math> be a martingale such that, for all <math>k\ge 1</math>,
 +
::<math>
 +
|X_{k}-X_{k-1}|\le c,
 +
</math>
 +
:Then
 +
::<math>\begin{align}
 +
\Pr\left[|X_n-X_0|\ge ct\sqrt{n}\right]\le 2 e^{-t^2/2}.
 +
\end{align}</math>
 +
}}
 +
 
 +
This corollary states that for any martingale sequence whose diferences are bounded by a constant, the probability that it deviates <math>\omega(\sqrt{n})</math> far away from the starting point after <math>n</math> steps is bounded by <math>o(1)</math>.
 +
 
 +
=== Generalization ===
 +
 
 +
Azuma's inequality can be generalized to a martingale with respect another sequence.
 +
{{Theorem
 +
|Azuma's Inequality (general version)|
 +
:Let <math>Y_0,Y_1,\ldots</math> be a martingale with respect to the sequence <math>X_0,X_1,\ldots</math> such that, for all <math>k\ge 1</math>,
 +
::<math>
 +
|Y_{k}-Y_{k-1}|\le c_k,
 +
</math>
 +
:Then
 +
::<math>\begin{align}
 +
\Pr\left[|Y_n-Y_0|\ge t\right]\le 2\exp\left(-\frac{t^2}{2\sum_{k=1}^nc_k^2}\right).
 +
\end{align}</math>
 +
}}
 +
 
 +
=== 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 <math>Y_i</math> conditioning on sequence <math>X_i</math>.
 +
 
 +
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 <math>|X_n-X_0|\ge t</math>, we first bound the upper tail <math>\Pr[X_n-X_0\ge t]</math>. The bound of the lower tail can be symmetrically proved with the <math>X_i</math> replaced by <math>-X_i</math>.
 +
 
 +
==== Represent the deviation as the sum of differences ====
 +
We define the '''martingale difference sequence''': for <math>i\ge 1</math>, let
 +
:<math>
 +
Y_i=X_i-X_{i-1}.
 +
</math>
 +
It holds that
 +
:<math>
 +
\begin{align}
 +
\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{align}
 +
</math>
 +
The second to the last equation is due to the fact that <math>X_0,X_1,\ldots</math> is a martingale and the definition of conditional expectation.
 +
 
 +
Let <math>Z_n</math> be the accumulated differences
 +
:<math>
 +
Z_n=\sum_{i=1}^n Y_i.
 +
</math>
 +
 
 +
The deviation <math>(X_n-X_0)</math> can be computed by the accumulated differences:
 +
:<math>
 +
\begin{align}
 +
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{align}
 +
</math>
 +
 
 +
We then only need to upper bound the probability of the event <math>Z_n\ge t</math>.
 +
 
 +
==== Apply Markov's inequality to the moment generating function ====
 +
The event <math>Z_n\ge t</math> is equivalent to that <math>e^{\lambda Z_n}\ge e^{\lambda t}</math> for <math>\lambda>0</math>. Apply Markov's inequality, we have
 +
:<math>
 +
\begin{align}
 +
\Pr\left[Z_n\ge t\right]
 +
&=\Pr\left[e^{\lambda Z_n}\ge e^{\lambda t}\right]\\
 +
&\le \frac{\mathbf{E}\left[e^{\lambda Z_n}\right]}{e^{\lambda t}}.
 +
\end{align}
 +
</math>
 +
This is exactly the same as what we did to prove the Chernoff bound. Next, we need to bound the moment generating function <math>\mathbf{E}\left[e^{\lambda Z_n}\right]</math>.
 +
 
 +
==== Bound the moment generating functions ====
 +
The moment generating function
 +
:<math>
 +
\begin{align}
 +
\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{align}
 +
</math>
 +
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 <math>\mathbf{E}\left[e^{\lambda Y_n}\mid X_0,\ldots,X_{n-1}\right]</math> by a constant. To do so, we need the following technical lemma which is proved by the convexity of  <math>e^{\lambda Y_n}</math>.
 +
 
 +
{{Theorem
 +
|Lemma|
 +
:Let <math>X</math> be a random variable such that <math>\mathbf{E}[X]=0</math> and <math>|X|\le c</math>. Then for <math>\lambda>0</math>,
 +
::<math>
 +
\mathbf{E}[e^{\lambda X}]\le e^{\lambda^2c^2/2}.
 +
</math>
 +
}}
 +
{{Proof| Observe that for <math>\lambda>0</math>, the function <math>e^{\lambda X}</math> of the variable <math>X</math> is convex in the interval <math>[-c,c]</math>. We draw a line between the two endpoints points <math>(-c, e^{-\lambda c})</math> and <math>(c, e^{\lambda c})</math>. The curve of <math>e^{\lambda X}</math> lies entirely below this line. Thus,
 +
:<math>
 +
\begin{align}
 +
e^{\lambda X}
 +
&\le \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{align}
 +
</math>
 +
 
 +
Since <math>\mathbf{E}[X]=0</math>, we have
 
:<math>
 
:<math>
\mathbf{E}[Y\mid \mathcal{E}]=\sum_{y}y\Pr[Y=y\mid\mathcal{E}].
+
\begin{align}
 +
\mathbf{E}[e^{\lambda X}]
 +
&\le \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{align}
 
</math>
 
</math>
In particular, if the event <math>\mathcal{E}</math> is <math>X=a</math>, the conditional expectation
+
 
 +
By expanding both sides as Taylor's series, it can be verified that <math>\frac{e^{\lambda c}+e^{-\lambda c}}{2}\le e^{\lambda^2c^2/2}</math>.
 +
}}
 +
 
 +
Apply the above lemma to the random variable
 
:<math>
 
:<math>
\mathbf{E}[Y\mid X=a]
+
(Y_n \mid X_0,\ldots,X_{n-1})
 +
</math>
 +
 
 +
We have already shown that its expectation
 +
<math>
 +
\mathbf{E}[(Y_n \mid X_0,\ldots,X_{n-1})]=0,
 +
</math>
 +
and by the bounded difference condition of Azuma's inequality, we have
 +
<math>
 +
|Y_n|=|(X_n-X_{n-1})|\le c_n.
 +
</math>
 +
Thus, due to the above lemma, it holds that
 +
:<math>
 +
\mathbf{E}[e^{\lambda Y_n}\mid X_0,\ldots,X_{n-1}]\le e^{\lambda^2c_n^2/2}.
 +
</math>
 +
 
 +
Back to our analysis of the expectation <math>\mathbf{E}\left[e^{\lambda Z_n}\right]</math>, we have
 +
:<math>
 +
\begin{align}
 +
\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]\\
 +
&\le \mathbf{E}\left[e^{\lambda Z_{n-1}}\cdot e^{\lambda^2c_n^2/2}\right]\\
 +
&= e^{\lambda^2c_n^2/2}\cdot\mathbf{E}\left[e^{\lambda Z_{n-1}}\right] .
 +
\end{align}
 +
</math>
 +
 
 +
Apply the same analysis to <math>\mathbf{E}\left[e^{\lambda Z_{n-1}}\right]</math>, we can solve the above recursion by
 +
:<math>
 +
\begin{align}
 +
\mathbf{E}\left[e^{\lambda Z_n}\right]
 +
&\le \prod_{k=1}^n e^{\lambda^2c_k^2/2}\\
 +
&= \exp\left(\lambda^2\sum_{k=1}^n c_k^2/2\right).
 +
\end{align}
 +
</math>
 +
 
 +
Go back to the Markov's inequality,
 +
:<math>
 +
\begin{align}
 +
\Pr\left[Z_n\ge t\right]
 +
&\le \frac{\mathbf{E}\left[e^{\lambda Z_n}\right]}{e^{\lambda t}}\\
 +
&\le \exp\left(\lambda^2\sum_{k=1}^n c_k^2/2-\lambda t\right).
 +
\end{align}
 +
</math>
 +
 
 +
We then only need to choose a proper <math>\lambda>0</math>.
 +
 
 +
==== Optimization ====
 +
By choosing <math>\lambda=\frac{t}{\sum_{k=1}^n c_k^2}</math>, we have that
 +
:<math>
 +
\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).
 +
</math>
 +
Thus, the probability
 +
:<math>
 +
\begin{align}
 +
\Pr\left[X_n-X_0\ge t\right]
 +
&=\Pr\left[Z_n\ge t\right]\\
 +
&\le \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{align}
 +
</math>
 +
The upper tail of Azuma's inequality is proved. By replacing <math>X_i</math> by <math>-X_i</math>, 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.
 +
 
 +
{{Theorem
 +
|Definition (The Doob sequence)|
 +
: The Doob sequence of a function <math>f</math> with respect to a sequence of random variables <math>X_1,\ldots,X_n</math> is defined by
 +
::<math>
 +
Y_i=\mathbf{E}[f(X_1,\ldots,X_n)\mid X_1,\ldots,X_{i}], \quad 0\le i\le n.
 +
</math>
 +
:In particular, <math>Y_0=\mathbf{E}[f(X_1,\ldots,X_n)]</math> and <math>Y_n=f(X_1,\ldots,X_n)</math>.
 +
}}
 +
 
 +
The Doob sequence of a function defines a martingale. That is
 +
::<math>
 +
\mathbf{E}[Y_i\mid X_1,\ldots,X_{i-1}]=Y_{i-1},
 
</math>
 
</math>
defines a function
+
for any <math>0\le i\le n</math>.
 +
 
 +
To prove this claim, we recall the definition that <math>Y_i=\mathbf{E}[f(X_1,\ldots,X_n)\mid X_1,\ldots,X_{i}]</math>, thus,
 
:<math>
 
:<math>
f(a)=\mathbf{E}[Y\mid X=a].
+
\begin{align}
 +
\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{align}
 +
</math>
 +
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 <math>f(X_1,\ldots,X_n)</math> of random variables <math>X_1,\ldots,X_n</math>. The Doob sequence <math>Y_0,Y_1,\ldots,Y_n</math> represents a sequence of refined estimates of the value of <math>f(X_1,\ldots,X_n)</math>, gradually using more information on the values of the random variables <math>X_1,\ldots,X_n</math>. The first element <math>Y_0</math> is just the expectation of <math>f(X_1,\ldots,X_n)</math>. Element <math>Y_i</math> is the expected value of <math>f(X_1,\ldots,X_n)</math> when the values of <math>X_1,\ldots,X_{i}</math> are known, and <math>Y_n=f(X_1,\ldots,X_n)</math> when <math>f(X_1,\ldots,X_n)</math> is fully determined by <math>X_1,\ldots,X_n</math>.
 +
 
 +
The following two Doob martingales arise in evaluating the parameters of random graphs.
 +
 
 +
;edge exposure martingale
 +
:Let <math>G</math> be a random graph on <math>n</math> vertices. Let <math>f</math> 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 <math>m={n\choose 2}</math>. Fix an arbitrary numbering of potential edges between the <math>n</math> vertices, and denote the edges as <math>e_1,\ldots,e_m</math>. Let
 +
::<math>
 +
X_i=\begin{cases}
 +
1& \mbox{if }e_i\in G,\\
 +
0& \mbox{otherwise}.
 +
\end{cases}
 
</math>
 
</math>
Thus, <math>\mathbf{E}[Y\mid X]</math> can be regarded as a random variable <math>f(X)</math>.
+
:Let <math>Y_0=\mathbf{E}[f(G)]</math> and for <math>i=1,\ldots,m</math>, let <math>Y_i=\mathbf{E}[f(G)\mid X_1,\ldots,X_i]</math>.
 +
:The sequence <math>Y_0,Y_1,\ldots,Y_n</math> gives a Doob martingale that is commonly called the '''edge exposure martingale'''.
  
;Example
+
;vertex exposure martingale
:Suppose that we uniformly sample a human from all human beings. Let <math>Y</math> be his/her height, and let <math>X</math> be the country where he/she is from. For any country <math>a</math>, <math>\mathbf{E}[Y\mid X=a]</math> gives the average height of that country. And <math>\mathbf{E}[Y\mid X]</math> is the random variable which can be defined in either ways:
+
: 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 <math>[n]</math>. Let <math>X_i</math> be the subgraph of <math>G</math> induced by the vertex set <math>[i]</math>, i.e. the first <math>i</math> vertices.
:* We choose a human uniformly at random from all human beings, and <math>\mathbf{E}[Y\mid X]</math> is the average height of the country where he/she comes from.
+
:Let <math>Y_0=\mathbf{E}[f(G)]</math> and for <math>i=1,\ldots,n</math>, let <math>Y_i=\mathbf{E}[f(G)\mid X_1,\ldots,X_i]</math>.
:* We choose a country at random with a probability ''proportional to its population'', and <math>\mathbf{E}[Y\mid X]</math> is the average height of the chosen country.
+
:The sequence <math>Y_0,Y_1,\ldots,Y_n</math> gives a Doob martingale that is commonly called the '''vertex exposure martingale'''.
  
The following proposition states some fundamental facts about conditional expectation.
+
===Chromatic number===
 +
The random graph <math>G(n,p)</math> is the graph on <math>n</math> vertices <math>[n]</math>, obtained by selecting each pair of vertices to be an edge, randomly and independently, with probability <math>p</math>. We denote <math>G\sim G(n,p)</math> if <math>G</math> is generated in this way.
  
 
{{Theorem
 
{{Theorem
|Proposition (fundamental facts about conditional expectation)|
+
|Theorem [Shamir and Spencer (1987)]|
:Let <math>X,Y</math> and <math>Z</math> be arbitrary random variables. Let <math>f</math> and <math>g</math> be arbitrary functions. Then
+
:Let <math>G\sim G(n,p)</math>. Let <math>\chi(G)</math> be the chromatic number of <math>G</math>. Then
:# <math>\mathbf{E}[X]=\mathbf{E}[\mathbf{E}[X\mid Y]]</math>.
+
::<math>\begin{align}
:# <math>\mathbf{E}[X\mid Z]=\mathbf{E}[\mathbf{E}[X\mid Y,Z]\mid Z]</math>.
+
\Pr\left[|\chi(G)-\mathbf{E}[\chi(G)]|\ge t\sqrt{n}\right]\le 2e^{-t^2/2}.
:# <math>\mathbf{E}[\mathbf{E}[f(X)g(X,Y)\mid X]]=\mathbf{E}[f(X)\cdot \mathbf{E}[g(X,Y)\mid X]]</math>.
+
\end{align}</math>
 +
}}
 +
{{Proof| Consider the vertex exposure martingale
 +
:<math>
 +
Y_i=\mathbf{E}[\chi(G)\mid X_1,\ldots,X_i]
 +
</math>
 +
where each <math>X_k</math> exposes the induced subgraph of <math>G</math> on vertex set <math>[k]</math>. A single vertex can always be given a new color so that the graph is properly colored, thus the bounded difference condition
 +
:<math>
 +
|Y_i-Y_{i-1}|\le 1
 +
</math>
 +
is satisfied. Now apply the Azuma's inequality for the martingale <math>Y_1,\ldots,Y_n</math> with respect to <math>X_1,\ldots,X_n</math>.
 
}}
 
}}
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:
+
For <math>t=\omega(1)</math>, 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.  
:<math>\mathbf{E}[X]=\mathbf{E}[\mathbf{E}[X\mid Y]]</math>
 
says that there are two ways to compute an average. Suppose again that <math>X</math> is the height of a uniform random human and <math>Y</math> 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:
+
=== Hoeffding's Inequality===
:<math>\mathbf{E}[X\mid Z]=\mathbf{E}[\mathbf{E}[X\mid Y,Z]\mid Z]</math>
+
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.
is the same as the first one, restricted to a particular subspace. As the previous example, inaddition to the height <math>X</math> and the country <math>Y</math>, let <math>Z</math> be the gender of the individual. Thus, <math>\mathbf{E}[X\mid Z]</math> 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.
+
{{Theorem
 +
|Hoeffding's inequality|
 +
: Let <math>X=\sum_{i=1}^nX_i</math>, where <math>X_1,\ldots,X_n</math> are independent random variables with <math>a_i\le X_i\le b_i</math> for each <math>1\le i\le n</math>. Let <math>\mu=\mathbf{E}[X]</math>. Then
 +
::<math>
 +
\Pr[|X-\mu|\ge t]\le 2\exp\left(-\frac{t^2}{2\sum_{i=1}^n(b_i-a_i)^2}\right).
 +
</math>
 +
}}
 +
{{Proof| Define the Doob martingale sequence <math>Y_i=\mathbf{E}\left[\sum_{j=1}^n X_j\,\Big|\, X_1,\ldots,X_{i}\right]</math>. Obviously <math>Y_0=\mu</math> and <math>Y_n=X</math>.
  
The third equation:
 
:<math>\mathbf{E}[\mathbf{E}[f(X)g(X,Y)\mid X]]=\mathbf{E}[f(X)\cdot \mathbf{E}[g(X,Y)\mid X]]</math>.
 
looks obscure at the first glance, especially when considering that <math>X</math> and <math>Y</math> are not necessarily independent. Nevertheless, the equation follows the simple fact that conditioning on any <math>X=a</math>, the function value <math>f(X)=f(a)</math> becomes a constant, thus can be safely taken outside the expectation due to the linearity of expectation. For any value <math>X=a</math>,
 
 
:<math>
 
:<math>
\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].
+
\begin{align}
 +
|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|\\
 +
&\le b_i-a_i
 +
\end{align}
 +
</math>
 +
Apply Azuma's inequality for the martingale <math>Y_0,\ldots,Y_n</math> with respect to <math>X_1,\ldots, X_n</math>,  the Hoeffding's inequality is proved.
 +
}}
 +
 
 +
==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 <math>X_1,\ldots,X_n</math> and a function <math>f</math>.  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
 +
|Theorem (Method of averaged bounded differences)|
 +
:Let <math>\boldsymbol{X}=(X_1,\ldots, X_n)</math> be arbitrary random variables and let <math>f</math> be a function of <math>X_0,X_1,\ldots, X_n</math> satisfying that, for all <math>1\le i\le n</math>,
 +
::<math>
 +
|\mathbf{E}[f(\boldsymbol{X})\mid X_1,\ldots,X_i]-\mathbf{E}[f(\boldsymbol{X})\mid X_1,\ldots,X_{i-1}]|\le c_i,
 
</math>
 
</math>
 +
:Then
 +
::<math>\begin{align}
 +
\Pr\left[|f(\boldsymbol{X})-\mathbf{E}[f(\boldsymbol{X})]|\ge t\right]\le 2\exp\left(-\frac{t^2}{2\sum_{i=1}^nc_i^2}\right).
 +
\end{align}</math>
 +
}}
 +
{{Proof| Define the Doob Martingale sequence <math>Y_0,Y_1,\ldots,Y_n</math> by setting <math>Y_0=\mathbf{E}[f(X_1,\ldots,X_n)]</math> and, for <math>1\le i\le n</math>, <math>Y_i=\mathbf{E}[f(X_1,\ldots,X_n)\mid X_1,\ldots,X_i]</math>. Then the above theorem is a restatement of the Azuma's inequality holding for <math>Y_0,Y_1,\ldots,Y_n</math>.
 +
}}
 +
 +
=== 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.
  
The proposition holds in more general cases when <math>X, Y</math> and <math>Z</math> are a sequence of random variables.
+
{{Theorem
 +
|Definition (Lipschitz condition)|
 +
:A function <math>f(x_1,\ldots,x_n)</math> satisfies the Lipschitz condition, if for any <math>x_1,\ldots,x_n</math> and any <math>y_i</math>,
 +
::<math>\begin{align}
 +
|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)|\le 1.
 +
\end{align}</math>
 +
}}
 +
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.
 +
{{Theorem
 +
|Definition (Lipschitz condition, general version)|
 +
:A function <math>f(x_1,\ldots,x_n)</math> satisfies the Lipschitz condition with constants <math>c_i</math>, <math>1\le i\le n</math>, if for any <math>x_1,\ldots,x_n</math> and any <math>y_i</math>,
 +
::<math>\begin{align}
 +
|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)|\le c_i.
 +
\end{align}</math>
 +
}}
 +
 
 +
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.
 +
{{Theorem
 +
|Corollary (Method of bounded differences)|
 +
:Let <math>\boldsymbol{X}=(X_1,\ldots, X_n)</math> be <math>n</math> '''independent''' random variables and let <math>f</math> be a function satisfying the Lipschitz condition with constants <math>c_i</math>, <math>1\le i\le n</math>. Then
 +
::<math>\begin{align}
 +
\Pr\left[|f(\boldsymbol{X})-\mathbf{E}[f(\boldsymbol{X})]|\ge t\right]\le 2\exp\left(-\frac{t^2}{2\sum_{i=1}^nc_i^2}\right).
 +
\end{align}</math>
 +
}}
 +
 
 +
{{Proof| For convenience, we denote that <math>\boldsymbol{X}_{[i,j]}=(X_i,X_{i+1},\ldots, X_j)</math> for any <math>1\le i\le j\le n</math>.
 +
 
 +
We first show that the Lipschitz condition with constants <math>c_i</math>, <math>1\le i\le n</math>, implies another condition called the averaged Lipschitz condition (ALC): for any <math>a_i,b_i</math>, <math>1\le i\le n</math>,
 +
:<math>
 +
\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|\le c_i.
 +
</math>
 +
And this condition implies the averaged bounded difference condition: for all <math>1\le i\le n</math>,
 +
::<math>
 +
\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|\le c_i.
 +
</math>
 +
Then by applying the method of averaged bounded differences, the corollary can be proved.
 +
 
 +
For any <math>a</math>, by the law of total expectation,
 +
:<math>
 +
\begin{align}
 +
&\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{align}
 +
</math>
 +
 
 +
Let <math>a=a_i</math> and <math>b_i</math>, and take the diference. Then
 +
:<math>
 +
\begin{align}
 +
&\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|\\
 +
&\le \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]\\
 +
&\le \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{align}
 +
</math>
 +
 
 +
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,
 +
:<math>
 +
\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]}].
 +
</math>
 +
 
 +
We can trivially write <math>\mathbf{E}\left[f(\boldsymbol{X})\mid \boldsymbol{X}_{[1,i]}\right]</math> as
 +
:<math>
 +
\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].
 +
</math>
 +
 
 +
Hence, the difference is
 +
:<math>
 +
\begin{align}
 +
&\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| \\
 +
&\le \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] \\
 +
&\le \sum_a c_i\Pr\left[X_i=a\mid \boldsymbol{X}_{[1,i-1]}\right] \qquad (\mbox{due to ALC})\\
 +
&=c_i.
 +
\end{align}
 +
</math>
 +
 
 +
The averaged bounded diference condition is implied. Applying the method of averaged bounded diferences, the corollary follows.
 +
}}
 +
 
 +
=== Applications ===
 +
 
 +
==== Occupancy problem ====
 +
Throwing <math>m</math> balls uniformly and independently at random to <math>n</math> 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 <math>f:[m]\rightarrow[n]</math> be a uniform random function from <math>[m]\rightarrow[n]</math>. We ask for the number of <math>i\in[n]</math> that <math>f^{-1}(i)</math> is empty.
 +
 
 +
For any <math>i\in[n]</math>, let <math>X_i</math> indicate the emptiness of bin <math>i</math>. Let <math>X=\sum_{i=1}^nX_i</math> be the number of empty bins.
 +
:<math>
 +
\mathbf{E}[X_i]=\Pr[\mbox{bin }i\mbox{ is empty}]=\left(1-\frac{1}{n}\right)^m.
 +
</math>
 +
By the linearity of expectation,
 +
:<math>
 +
\mathbf{E}[X]=\sum_{i=1}^n\mathbf{E}[X_i]=n\left(1-\frac{1}{n}\right)^m.
 +
</math>
 +
 
 +
We want to know how <math>X</math> deviates from this expectation. The complication here is that <math>X_i</math> are not independent. So we alternatively look at a sequence of independent random variables <math>Y_1,\ldots, Y_m</math>, where <math>Y_j\in[n]</math> represents the bin into which the <math>j</math>th ball falls. Clearly <math>X</math> is function of <math>Y_1,\ldots, Y_m</math>.
 +
 
 +
We than observe that changing the value of any <math>Y_i</math> can change the value of <math>X</math> by at most 1, because one ball can affect the emptiness of at most one bin.
 +
Thus as a function of independent random variables <math>Y_1,\ldots, Y_m</math>, <math>X</math> satisfies the Lipschitz condition. Apply the method of bounded differences, it holds that
 +
:<math>
 +
\Pr\left[\left|X-n\left(1-\frac{1}{n}\right)^m\right|\ge t\sqrt{m}\right]=\Pr[|X-\mathbf{E}[X]|\ge t\sqrt{m}]\le 2e^{-t^2/2}
 +
</math>
 +
 
 +
Thus, for sufficiently large <math>n</math> and <math>m</math>, the number of empty bins is tightly concentrated around <math>n\left(1-\frac{1}{n}\right)^m\approx \frac{n}{e^{m/n}}</math>
 +
 
 +
==== Pattern Matching ====
 +
Let <math>\boldsymbol{X}=(X_1,\ldots,X_n)</math> be a sequence of characters chosen independently and uniformly at random from an alphabet <math>\Sigma</math>, where <math>m=|\Sigma|</math>. Let <math>\pi\in\Sigma^k</math> be an arbitrarily fixed string of <math>k</math> characters from <math>\Sigma</math>, called a ''pattern''. Let <math>Y</math> be the number of occurrences of the pattern <math>\pi</math> as a substring of the random string <math>X</math>.
 +
 
 +
By the linearity of expectation, it is obvious that
 +
:<math>
 +
\mathbf{E}[Y]=(n-k+1)\left(\frac{1}{m}\right)^k.
 +
</math>
 +
 
 +
We now look at the concentration of <math>Y</math>. The complication again lies in the dependencies between the matches. Yet we will see that <math>Y</math> is well tightly concentrated around its expectation if <math>k</math> is relatively small compared to <math>n</math>.
 +
 
 +
For a fixed pattern <math>\pi</math>, the random variable <math>Y</math> is a function of the independent random variables <math>(X_1,\ldots,X_n)</math>. Any character <math>X_i</math> participates in no more than <math>k</math> matches, thus changing the value of any <math>X_i</math> can affect the value of <math>Y</math> by at most <math>k</math>. <math>Y</math> satisfies the Lipschitz condition with constant <math>k</math>. Apply the method of bounded differences,
 +
:<math>
 +
\Pr\left[\left|Y-\frac{n-k+1}{m^k}\right|\ge tk\sqrt{n}\right]=\Pr\left[\left|Y-\mathbf{E}[Y]\right|\ge  tk\sqrt{n}\right]\le 2e^{-t^2/2}
 +
</math>
 +
 
 +
==== Combining unit vectors ====
 +
Let <math>u_1,\ldots,u_n</math> be <math>n</math> unit vectors from some normed space. That is, <math>\|u_i\|=1</math> for any <math>1\le i\le n</math>, where <math>\|\cdot\|</math> denote the vector norm (e.g. <math>\ell_1,\ell_2,\ell_\infty</math>) of the space.
 +
 
 +
Let <math>\epsilon_1,\ldots,\epsilon_n\in\{-1,+1\}</math> be independently chosen and <math>\Pr[\epsilon_i=-1]=\Pr[\epsilon_i=1]=1/2</math>.
 +
 
 +
Let
 +
:<math>v=\epsilon_1u_1+\cdots+\epsilon_nu_n,
 +
</math>
 +
and
 +
:<math>
 +
X=\|v\|.
 +
</math>
 +
This kind of construction is very useful in combinatorial proofs of metric problems. We will show that by this construction, the random variable <math>X</math> is well concentrated around its mean.
 +
 
 +
<math>X</math> is a function of independent random variables <math>\epsilon_1,\ldots,\epsilon_n</math>.
 +
By the triangle inequality for norms, it is easy to verify that changing the sign of a unit vector <math>u_i</math> can only change the value of <math>X</math> for at most 2, thus <math>X</math> satisfies the Lipschitz condition with constant 2. The concentration result follows by applying the method of bounded differences:
 +
:<math>
 +
\Pr[|X-\mathbf{E}[X]|\ge 2t\sqrt{n}]\le 2e^{-t^2/2}.
 +
</math>

Latest revision as of 06:10, 8 October 2019

Chernoff Bound

Suppose that we have a fair coin. If we toss it once, then the outcome is completely unpredictable. But if we toss it, say for 1000 times, then the number of HEADs is very likely to be around 500. This phenomenon, as illustrated in the following figure, is called the concentration of measure. The Chernoff bound is an inequality that characterizes the concentration phenomenon for the sum of independent trials.

Coinflip.png

Before formally stating the Chernoff bound, let's introduce the moment generating function.

Moment generating functions

The more we know about the moments of a random variable , the more information we would have about . There is a so-called moment generating function, which "packs" all the information about the moments of into one function.

Definition
The moment generating function of a random variable is defined as where is the parameter of the function.

By Taylor's expansion and the linearity of expectations,

The moment generating function is a function of .

The Chernoff bound

The Chernoff bounds are exponentially sharp tail inequalities for the sum of independent trials. The bounds are obtained by applying Markov's inequality to the moment generating function of the sum of independent trials, with some appropriate choice of the parameter .

Chernoff bound (the upper tail)
Let , where are independent Poisson trials. Let .
Then for any ,
Proof.
For any , is equivalent to that , thus

where the last step follows by Markov's inequality.

Computing the moment generating function :

Let for . Then,

.

We bound the moment generating function for each individual as follows.

where in the last step we apply the Taylor's expansion so that where . (By doing this, we can transform the product to the sum of , which is .)

Therefore,

Thus, we have shown that for any ,

.

For any , we can let to get

The idea of the proof is actually quite clear: we apply Markov's inequality to and for the rest, we just estimate the moment generating function . To make the bound as tight as possible, we minimized the by setting , which can be justified by taking derivatives of .


We then proceed to the lower tail, the probability that the random variable deviates below the mean value:

Chernoff bound (the lower tail)
Let , where are independent Poisson trials. Let .
Then for any ,
Proof.
For any , by the same analysis as in the upper tail version,

For any , we can let to get

Useful forms of the Chernoff bounds

Some useful special forms of the bounds can be derived directly from the above general forms of the bounds. We now know better why we say that the bounds are exponentially sharp.

Useful forms of the Chernoff bound
Let , where are independent Poisson trials. Let . Then
1. for ,
2. for ,
Proof.
To obtain the bounds in (1), we need to show that for , and . We can verify both inequalities by standard analysis techniques.

To obtain the bound in (2), let . Then . Hence,

Applications to balls-into-bins

Throwing balls uniformly and independently to bins, what is the maximum load of all bins with high probability? In the last class, we gave an analysis of this problem by using a counting argument.

Now we give a more "advanced" analysis by using Chernoff bounds.


For any and , let be the indicator variable for the event that ball is thrown to bin . Obviously

Let be the load of bin .


Then the expected load of bin is

For the case , it holds that

Note that is a sum of mutually independent indicator variable. Applying Chernoff bound, for any particular bin ,

The case

When , . Write . The above bound can be written as

Let , we evaluate by taking logarithm to its reciprocal.

Thus,

Applying the union bound, the probability that there exists a bin with load is

.

Therefore, for , with high probability, the maximum load is .

The case

When , then according to ,

We can apply an easier form of the Chernoff bounds,

By the union bound, the probability that there exists a bin with load is,

.

Therefore, for , with high probability, the maximum load is .

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 losses, if the th bet wins, then it gives a net profit of

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 , where is his initial capital, and represents his capital after the th betting. Up to different betting strategies, can be arbitrarily dependent on . However, as long as the game is fair, namely, winning and losing with equal chances, conditioning on the past variables , we will expect no change in the value of the present variable on average. Random variables satisfying this property is called a martingale sequence.

Definition (martingale)
A sequence of random variables is a martingale if for all ,

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

Definition (martingale, general version)
A sequence of random variables is a martingale with respect to the sequence if, for all , the following conditions hold:
  • is a function of ;

Therefore, a sequence 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

The Azuma's inequality is a martingale tail inequality.

Azuma's Inequality
Let be a martingale such that, for all ,
Then

Unlike the Chernoff bounds, there is no assumption of independence, which makes the martingale inequalities more useful.

The following bounded difference condition

says that the martingale as a process evolving over time, never makes big change in a single step.

The Azuma's inequality says that for any martingale satisfying the bounded difference condition, 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 be a martingale such that, for all ,
Then

This corollary states that for any martingale sequence whose diferences are bounded by a constant, the probability that it deviates far away from the starting point after steps is bounded by .

Generalization

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

Azuma's Inequality (general version)
Let be a martingale with respect to the sequence such that, for all ,
Then

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 conditioning on sequence .

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 , we first bound the upper tail . The bound of the lower tail can be symmetrically proved with the replaced by .

Represent the deviation as the sum of differences

We define the martingale difference sequence: for , let

It holds that

The second to the last equation is due to the fact that is a martingale and the definition of conditional expectation.

Let be the accumulated differences

The deviation can be computed by the accumulated differences:

We then only need to upper bound the probability of the event .

Apply Markov's inequality to the moment generating function

The event is equivalent to that for . Apply Markov's inequality, we have

This is exactly the same as what we did to prove the Chernoff bound. Next, we need to bound the moment generating function .

Bound the moment generating functions

The moment generating function

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 by a constant. To do so, we need the following technical lemma which is proved by the convexity of .

Lemma
Let be a random variable such that and . Then for ,
Proof.
Observe that for , the function of the variable is convex in the interval . We draw a line between the two endpoints points and . The curve of lies entirely below this line. Thus,

Since , we have

By expanding both sides as Taylor's series, it can be verified that .

Apply the above lemma to the random variable

We have already shown that its expectation and by the bounded difference condition of Azuma's inequality, we have Thus, due to the above lemma, it holds that

Back to our analysis of the expectation , we have

Apply the same analysis to , we can solve the above recursion by

Go back to the Markov's inequality,

We then only need to choose a proper .

Optimization

By choosing , we have that

Thus, the probability

The upper tail of Azuma's inequality is proved. By replacing by , 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 with respect to a sequence of random variables is defined by
In particular, and .

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

for any .

To prove this claim, we recall the definition that , thus,

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 of random variables . The Doob sequence represents a sequence of refined estimates of the value of , gradually using more information on the values of the random variables . The first element is just the expectation of . Element is the expected value of when the values of are known, and when is fully determined by .

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

edge exposure martingale
Let be a random graph on vertices. Let 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 . Fix an arbitrary numbering of potential edges between the vertices, and denote the edges as . Let
Let and for , let .
The sequence 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 . Let be the subgraph of induced by the vertex set , i.e. the first vertices.
Let and for , let .
The sequence gives a Doob martingale that is commonly called the vertex exposure martingale.

Chromatic number

The random graph is the graph on vertices , obtained by selecting each pair of vertices to be an edge, randomly and independently, with probability . We denote if is generated in this way.

Theorem [Shamir and Spencer (1987)]
Let . Let be the chromatic number of . Then
Proof.
Consider the vertex exposure martingale

where each exposes the induced subgraph of on vertex set . A single vertex can always be given a new color so that the graph is properly colored, thus the bounded difference condition

is satisfied. Now apply the Azuma's inequality for the martingale with respect to .

For , 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 , where are independent random variables with for each . Let . Then
Proof.
Define the Doob martingale sequence . Obviously and .

Apply Azuma's inequality for the martingale with respect to , the Hoeffding's inequality is proved.

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 and a function . 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 be arbitrary random variables and let be a function of satisfying that, for all ,
Then
Proof.
Define the Doob Martingale sequence by setting and, for , . Then the above theorem is a restatement of the Azuma's inequality holding for .

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 satisfies the Lipschitz condition, if for any and any ,

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 satisfies the Lipschitz condition with constants , , if for any and any ,

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 be independent random variables and let be a function satisfying the Lipschitz condition with constants , . Then
Proof.
For convenience, we denote that for any .

We first show that the Lipschitz condition with constants , , implies another condition called the averaged Lipschitz condition (ALC): for any , ,

And this condition implies the averaged bounded difference condition: for all ,

Then by applying the method of averaged bounded differences, the corollary can be proved.

For any , by the law of total expectation,

Let and , and take the diference. Then

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,

We can trivially write as

Hence, the difference is

The averaged bounded diference condition is implied. Applying the method of averaged bounded diferences, the corollary follows.

Applications

Occupancy problem

Throwing balls uniformly and independently at random to 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 be a uniform random function from . We ask for the number of that is empty.

For any , let indicate the emptiness of bin . Let be the number of empty bins.

By the linearity of expectation,

We want to know how deviates from this expectation. The complication here is that are not independent. So we alternatively look at a sequence of independent random variables , where represents the bin into which the th ball falls. Clearly is function of .

We than observe that changing the value of any can change the value of by at most 1, because one ball can affect the emptiness of at most one bin. Thus as a function of independent random variables , satisfies the Lipschitz condition. Apply the method of bounded differences, it holds that

Thus, for sufficiently large and , the number of empty bins is tightly concentrated around

Pattern Matching

Let be a sequence of characters chosen independently and uniformly at random from an alphabet , where . Let be an arbitrarily fixed string of characters from , called a pattern. Let be the number of occurrences of the pattern as a substring of the random string .

By the linearity of expectation, it is obvious that

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

For a fixed pattern , the random variable is a function of the independent random variables . Any character participates in no more than matches, thus changing the value of any can affect the value of by at most . satisfies the Lipschitz condition with constant . Apply the method of bounded differences,

Combining unit vectors

Let be unit vectors from some normed space. That is, for any , where denote the vector norm (e.g. ) of the space.

Let be independently chosen and .

Let

and

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

is a function of independent random variables . By the triangle inequality for norms, it is easy to verify that changing the sign of a unit vector can only change the value of for at most 2, thus satisfies the Lipschitz condition with constant 2. The concentration result follows by applying the method of bounded differences: