高级算法 (Fall 2018)/Fingerprinting and 高级算法 (Fall 2018)/Concentration of measure: Difference between pages

From TCS Wiki
(Difference between pages)
Jump to navigation Jump to search
VisualWikitext
imported>Etone
 
imported>Etone
(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...")
 
Line 1: Line 1:
=Polynomial Identity Testing (PIT) =
= Conditional Expectations =
The '''Polynomial Identity Testing (PIT)''' is such a problem: given as input two polynomials, determine whether they are identical. It plays a fundamental role in ''Identity Testing'' problems.
The '''conditional expectation''' of a random variable <math>Y</math> with respect to an event <math>\mathcal{E}</math> is defined by
 
:<math>
First, let's consider the univariate ("one variable") case:
\mathbf{E}[Y\mid \mathcal{E}]=\sum_{y}y\Pr[Y=y\mid\mathcal{E}].
* '''Input:''' two polynomials <math>f, g\in\mathbb{F}[x]</math> of degree <math>d</math>.
</math>
* Determine whether <math>f\equiv g</math> (<math>f</math> and <math>g</math> are identical).
In particular, if the event <math>\mathcal{E}</math> is <math>X=a</math>, the conditional expectation
Here the <math>\mathbb{F}[x]</math> denotes the [http://en.wikipedia.org/wiki/Polynomial_ring ring of univariate polynomials] on a field <math>\mathbb{F}</math>. More precisely, a polynomial <math>f\in\mathbb{F}[x]</math> is
:<math>
:<math>f(x)=\sum_{i=0}^\infty a_ix^i</math>,
\mathbf{E}[Y\mid X=a]
where the coefficients <math>a_i</math> are taken from the field <math>\mathbb{F}</math>, and the addition and multiplication are also defined over the field <math>\mathbb{F}</math>.
</math>
And:
defines a function
* the '''degree''' of <math>f</math> is the highest <math>i</math> with non-zero <math>a_i</math>;
:<math>
* a polynomial <math>f</math> is a '''zero-polynomial''', denoted as <math>f\equiv 0</math>, if all coefficients <math>a_i=0</math>.
f(a)=\mathbf{E}[Y\mid X=a].
</math>
Thus, <math>\mathbf{E}[Y\mid X]</math> can be regarded as a random variable <math>f(X)</math>.


Alternatively, we can consider the following equivalent problem by comparing the polynomial <math>f-g</math> (whose degree is at most <math>d</math>) with the zero-polynomial:
;Example
* '''Input:''' a polynomial <math>f\in\mathbb{F}[x]</math> of degree <math>d</math>.
: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:
* Determine whether <math>f\equiv 0</math> (<math>f</math> is the 0 polynomial).
:* 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.
:* 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 probalem is trivial if the input polynomial <math>f</math> is given explicitly: one can trivially solve the problem by checking whether all <math>d+1</math> coefficients are <math>0</math>. To make the problem nontrivial, we assume that the input polynomial is given implicitly as a ''black box'' (also called an ''oracle''): the only way the algorithm can access to <math>f</math> is to evaluate <math>f(x)</math> over some <math>x</math> from the field <math>\mathbb{F}</math>, <math>x</math> chosen by the algorithm.
The following proposition states some fundamental facts about conditional expectation.


A straightforward deterministic algorithm is to evaluate <math>f(x_1),f(x_2),\ldots,f(x_{d+1})</math> over <math>d+1</math> ''distinct'' elements <math>x_1,x_2,\ldots,x_{d+1}</math> from the field <math>\mathbb{F}</math> and check whether they are all zero. By the [https://en.wikipedia.org/wiki/Fundamental_theorem_of_algebra fundamental theorem of algebra], also known as polynomial interpolations, this guarantees to verify whether a degree-<math>d</math> univariate polynomial <math>f\equiv 0</math>.
{{Theorem
{{Theorem|Fundamental Theorem of Algebra|
|Proposition (fundamental facts about conditional expectation)|
:Any non-zero univariate polynomial of degree <math>d</math> has at most <math>d</math> roots.
: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
:# <math>\mathbf{E}[X]=\mathbf{E}[\mathbf{E}[X\mid Y]]</math>.
:# <math>\mathbf{E}[X\mid Z]=\mathbf{E}[\mathbf{E}[X\mid Y,Z]\mid Z]</math>.
:# <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>.
}}
}}
The reason for this fundamental theorem holding generally over any field <math>\mathbb{F}</math> is that any univariate polynomial of degree <math>d</math> factors uniquely into at most <math>d</math> irreducible polynomials, each of which has at most one root.
The proposition can be formally verified by computing these expectations. Although these equations look formal, the intuitive interpretations to them are very clear.


The following simple randomized algorithm is natural:
The first equation:
{{Theorem|Algorithm for PIT|
:<math>\mathbf{E}[X]=\mathbf{E}[\mathbf{E}[X\mid Y]]</math>
*suppose we have a finite subset <math>S\subseteq\mathbb{F}</math> (to be specified later);
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.
*pick <math>r\in S</math> ''uniformly'' at random;
*if <math>f(r) = 0</math> then return “yes” else return “no”;
}}


This algorithm evaluates <math>f</math> at one point chosen uniformly at random from a finite subset <math>S\subseteq\mathbb{F}</math>. It is easy to see the followings:
The second equation:
* If <math>f\equiv 0</math>, the algorithm always returns "yes", so it is always correct.
:<math>\mathbf{E}[X\mid Z]=\mathbf{E}[\mathbf{E}[X\mid Y,Z]\mid Z]</math>
* If <math>f\not\equiv 0</math>, the algorithm may wrongly return "yes" (a '''false positive'''). But this happens only when the random <math>r</math> is a root of <math>f</math>. By the fundamental theorem of algebra, <math>f</math> has at most <math>d</math> roots, so the probability that the algorithm is wrong is bounded as
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.
::<math>\Pr[f(r)=0]\le\frac{d}{|S|}.</math>


By fixing <math>S\subseteq\mathbb{F}</math> to be an arbitrary subset of size <math>|S|=2d</math>, this probability of false positive is at most <math>1/2</math>. We can reduce it to an arbitrarily small constant <math>\delta</math> by repeat the above testing ''independently'' for <math>\log_2 \frac{1}{\delta}</math> times, since the error probability decays geometrically as we repeat the algorithm independently.
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>
\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].
</math>


== Communication Complexity of Equality ==
The proposition holds in more general cases when <math>X, Y</math> and <math>Z</math> are a sequence of random variables.
The [http://en.wikipedia.org/wiki/Communication_complexity communication complexity] is introduced by Andrew Chi-Chih Yao as a model of computation with more than one entities, each with partial information about the input.


Assume that there are two entities, say Alice and Bob. Alice has a private input <math>a</math> and Bob has a private input <math>b</math>. Together they want to compute a function <math>f(a,b)</math> by communicating with each other. The communication follows a predefined '''communication protocol''' (the "algorithm" in this model). The complexity of a communication protocol is measured by the number of bits communicated between Alice and Bob in the worst case.
= 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
The problem of checking identity is formally defined by the function EQ as follows: <math>\mathrm{EQ}:\{0,1\}^n\times\{0,1\}^n\rightarrow\{0,1\}</math> and for any <math>a,b\in\{0,1\}^n</math>,
:<math>
:<math>
\mathrm{EQ}(a,b)=
2^n-\sum_{i=1}^{n}2^{i-1}=1,
\begin{cases}
</math>
1& \mbox{if } a=b,\\
which is a positive number.
0& \mbox{otherwise.}
\end{cases}</math>


A trivial way to solve EQ is to let Bob send his entire input string <math>b</math> to Alice and let Alice check whether <math>a=b</math>. This costs <math>n</math> bits of communications.
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.


It is known that for deterministic communication protocols, this is the best we can get for computing EQ.
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|Theorem (Yao 1979)|
{{Theorem
:Any deterministic communication protocol computing EQ on two <math>n</math>-bit strings costs <math>n</math> bits of communication in the worst-case.
|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>
}}
}}


This theorem is much more nontrivial to prove than it looks, because Alice and Bob are allowed to interact with each other in arbitrary ways. The proof of this theorem is in Yao's [http://math.ucla.edu/~znorwood/290d.2.14s/papers/yao.pdf  celebrated paper in 1979 with a humble title]. It pioneered the field of communication complexity.
==Examples ==
;coin flips
:A fair coin is flipped for a number of times. Let <math>Z_j\in\{-1,1\}</math> denote the outcome of the <math>j</math>th flip. Let
::<math>X_0=0\quad \mbox{ and } \quad X_i=\sum_{j\le i}Z_j</math>.  
:The random variables <math>X_0,X_1,\ldots</math> defines a martingale.
;Proof
:We first observe that <math>\mathbf{E}[X_i\mid X_0,\ldots,X_{i-1}] = \mathbf{E}[X_i\mid X_{i-1}]</math>, 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.
::<math>
\begin{align}
\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{align}
</math>
 
;Polya's urn scheme
: Consider an urn (just a container) that initially contains <math>b</math> balck balls and <math>w</math> white balls. At each step, we uniformly select a ball from the urn, and replace the ball with <math>c</math> balls of the same color. Let <math>X_0=b/(b+w)</math>, and <math>X_i</math> be the fraction of black balls in the urn after the <math>i</math>th step. The sequence <math>X_0,X_1,\ldots</math> is a martingale.


If we allow randomness in protocols, and also tolerate a small probabilistic error, the problem can be solved with significantly less communications. To present this randomized protocol, we need a few preparations:
;edge exposure in a random graph
* We represent the inputs  <math>a,b \in\{0,1\}^{n}</math> of Alice and Bob as two univariate polynomials of degree at most <math>n-1</math>, respectively
:Consider a '''random graph''' <math>G</math> generated as follows. Let <math>[n]</math> be the set of vertices, and let <math>[m]={[n]\choose 2}</math> be the set of all possible edges. For convenience, we enumerate these potential edges by <math>e_1,\ldots, e_m</math>. For each potential edge <math>e_j</math>, we independently flip a fair coin to decide whether the edge <math>e_j</math> appears in <math>G</math>. Let <math>I_j</math> be the random variable that indicates whether <math>e_j\in G</math>. We are interested in some graph-theoretical parameter, say [http://mathworld.wolfram.com/ChromaticNumber.html chromatic number], of the random graph <math>G</math>. Let <math>\chi(G)</math> be the chromatic number of <math>G</math>. Let <math>X_0=\mathbf{E}[\chi(G)]</math>, and for each <math>i\ge 1</math>, let <math>X_i=\mathbf{E}[\chi(G)\mid I_1,\ldots,I_{i}]</math>, namely, the expected chromatic number of the random graph after fixing the first <math>i</math> edges. This process is called edges exposure of a random graph, as we "exposing" the edges one by one in a random graph.
::<math>f(x)=\sum_{i=0}^{n-1}a_ix^{i}</math> and <math>g(x)=\sum_{i=0}^{n-1}b_ix^{i}</math>.
* The two polynomials <math>f</math> and <math>g</math> are defined over finite field <math>\mathbb{Z}_p=\{0,1,\ldots,p-1\}</math> for some suitable prime <math>p</math> (to be specified later), which means the additions and multiplications are modulo <math>p</math>.
The randomized communication protocol is then as follows:
{{Theorem|A randomized protocol for EQ|
'''Bob does''':
:* pick <math>r\in\mathbb{Z}_p</math> uniformly at random;
:* send <math>r</math> and <math>g(r)</math> to Alice;
'''Upon receiving''' <math>r</math> and <math>g(r)</math> '''Alice does''':
:* compute <math>f(r)</math>;
:* If <math>f(r)= g(r)</math> return "'''yes'''"; else return "'''no'''".
}}
The communication complexity of the protocol is given by the number of bits used to represent the values of <math>r</math> and <math>g(r)</math>.
Since the polynomials are defined over finite field <math>\mathbb{Z}_p</math> and the random number <math>f</math> is also chosen from <math>\mathbb{Z}_p</math>, this is bounded by <math>O(\log p)</math>.  


On the other hand the protocol makes mistakes only when <math>a\neq b</math> but wrongly answers "yes". This happens only when <math>f\not\equiv g</math> but <math>f(r)=g(r)</math>. The degrees of <math>f, g</math> are at most <math>n-1</math>, and <math>r</math> is chosen among <math>p</math> distinct values, we have
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.
:<math>\Pr[f(r)=g(r)]\le \frac{n-1}{p}</math>.


By choosing <math>p</math> to be a prime in the interval <math>[n^2, 2n^2]</math> (by [https://en.wikipedia.org/wiki/Bertrand%27s_postulate Chebyshev's theorem], such prime <math>p</math> always exists), the above randomized communication protocol solves the Equality function EQ with an error probability of false positive at most <math>O(1/n)</math>, with communication complexity <math>O(\log n)</math>, an EXPONENTIAL improvement to ANY deterministic communication protocol!
== Generalizations ==
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.


== Schwartz-Zippel Theorem ==
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.
Now let's see the the true form of '''Polynomial Identity Testing (PIT)''', for multivariate polynomials:
* '''Input:''' two <math>n</math>-variate polynomials <math>f, g\in\mathbb{F}[x_1,x_2,\ldots,x_n]</math> of degree <math>d</math>.
* Determine whether <math>f\equiv g</math>.
The <math>\mathbb{F}[x_1,x_2,\ldots,x_n]</math> is the [http://en.wikipedia.org/wiki/Polynomial_ring#The_polynomial_ring_in_several_variables ring of multivariate polynomials] over field <math>\mathbb{F}</math>. An <math>n</math>-variate polynomial of degree <math>d</math>, written as a sum of monomials, is:
:<math>f(x_1,x_2,\ldots,x_n)=\sum_{i_1,i_2,\ldots,i_n\ge 0\atop i_1+i_2+\cdots+i_n\le d}a_{i_1,i_2,\ldots,i_n}x_{1}^{i_1}x_2^{i_2}\cdots x_{n}^{i_n}</math>.
The '''degree''' or '''total degree''' of a monomial <math>a_{i_1,i_2,\ldots,i_n}x_{1}^{i_1}x_2^{i_2}\cdots x_{n}^{i_n}</math> is given by <math>i_1+i_2+\cdots+i_n</math> and the degree of a polynomial <math>f</math> is the maximum degree of monomials of nonzero coefficients.


As before, we also consider the following equivalent problem:
=Azuma's Inequality=
* '''Input:''' a polynomial <math>f\in\mathbb{F}[x_1,x_2,\ldots,x_n]</math> of degree <math>d</math>.
* Determine whether <math>f\equiv 0</math>.


If <math>f</math> is written explicitly as a sum of monomials, then the problem can be solved by checking whether all coefficients, and there at most <math>{n+d\choose d}\le (n+d)^{d}</math> coefficients in an <math>n</math>-variate polynomial of degree at most <math>d</math>.  
We introduce a martingale tail inequality, called Azuma's inequality.


A multivariate polynomial <math>f</math> can also be presented in its '''product form''', for example:
{{Theorem
{{Theorem|Example|
|Azuma's Inequality|
The [http://en.wikipedia.org/wiki/Vandermonde_matrix Vandermonde matrix] <math>M=M(x_1,x_2,\ldots,x_n)</math> is defined as that <math>M_{ij}=x_i^{j-1}</math>, that is
:Let <math>X_0,X_1,\ldots</math> be a martingale such that, for all <math>k\ge 1</math>,
:<math>M=\begin{bmatrix}
::<math>
1 & x_1 & x_1^2 & \dots & x_1^{n-1}\\
|X_{k}-X_{k-1}|\le c_k,
1 & x_2 & x_2^2 & \dots & x_2^{n-1}\\
1 & x_3 & x_3^2 & \dots & x_3^{n-1}\\
\vdots & \vdots & \vdots & \ddots &\vdots \\
1 & x_n & x_n^2 & \dots & x_n^{n-1}
\end{bmatrix}</math>.
Let <math>f</math> be the polynomial defined as
:<math>
f(x_1,\ldots,x_n)=\det(M)=\prod_{j<i}(x_i-x_j).
</math>
</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>
}}
}}
For polynomials in product form, it is quite efficient to '''evaluate''' the polynomial at any specific point from the field over which the polynomial is defined, however, '''expanding''' the polynomial to a sum of monomials can be very expensive.
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.


The following is a simple randomized algorithm for testing identity of multivariate polynomials:
Second, the condition that
{{Theorem|Randomized algorithm for multivariate PIT|
:<math>
*suppose we have a finite subset <math>S\subseteq\mathbb{F}</math> (to be specified later);
|X_{k}-X_{k-1}|\le c_k
* pick <math>r_1,r_2,\ldots,r_n\in S</math> ''uniformly'' and ''independently'' at random;
</math>
* if <math>f(\vec{r})=f(r_1,r_2,\ldots,r_n) = 0</math> then return “yes” else return “no”;
is central to the proof. This condition is sometimes called the '''bounded difference condition'''. If we think of the martingale <math>X_0,X_1,\ldots</math> as a process evolving through time, where <math>X_i</math> gives some measurement at time <math>i</math>, 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.
}}


This algorithm evaluates <math>f</math> at one point chosen uniformly from an <math>n</math>-dimensional cube <math>S^n</math>, where <math>S\subseteq\mathbb{F}</math> is a finite subset. And:
A special case is when the differences are bounded by a constant. The following corollary is directly implied by the Azuma's inequality.  
* If <math>f\equiv 0</math>, the algorithm always returns "yes", so it is always correct.
* If <math>f\not\equiv 0</math>, the algorithm may wrongly return "yes" (a '''false positive'''). But this happens only when the random <math>\vec{r}=(r_1,r_2,\ldots,r_n)</math> is a root of <math>f</math>. The probability of this bad event is upper bounded by the following famous result due to [https://pdfs.semanticscholar.org/b913/cf330852035f49b4ec5fe2db86c47d8a98fd.pdf Schwartz (1980)] and [http://www.cecm.sfu.ca/~monaganm/teaching/TopicsinCA15/zippel79.pdf Zippel (1979)].  


{{Theorem|Schwartz-Zippel Theorem|
{{Theorem
: Let <math>f\in\mathbb{F}[x_1,x_2,\ldots,x_n]</math> be a multivariate polynomial of degree <math>d</math> over a field <math>\mathbb{F}</math>. If <math>f\not\equiv 0</math>, then for any finite set <math>S\subset\mathbb{F}</math>, and <math>r_1,r_2\ldots,r_n\in S</math> chosen uniformly and independently at random,
|Corollary|
::<math>\Pr[f(r_1,r_2,\ldots,r_n)=0]\le\frac{d}{|S|}.</math>
: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>
}}
}}
The Schwartz-Zippel Theorem states that for any nonzero <math>n</math>-variate polynomial of degree at most <math>d</math>, the number of roots in any cube <math>S^n</math> is at most <math>d\cdot |S|^{n-1}</math>.


Dana Moshkovitz gave a surprisingly simply and elegant [http://eccc.hpi-web.de/report/2010/096/ proof] of Schwartz-Zippel Theorem, using some advanced ideas. Now we introduce the standard proof by induction.
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>.


{{Proof|
=== Generalization ===
The theorem is proved by induction on <math>n</math>.


;Induction basis''':'''
Azuma's inequality can be generalized to a martingale with respect another sequence.
For <math>n=1</math>, this is the univariate case. Assume that <math>f\not\equiv 0</math>. Due to the fundamental theorem of algebra, any polynomial <math>f(x)</math> of degree at most <math>d</math> must have at most <math>d</math> roots, thus
{{Theorem
:<math>\Pr[f(r)=0]\le\frac{d}{|S|}.
|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>
</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>
}}


;Induction hypothesis''':'''  
=== The Proof of Azuma's Inueqality===
Assume the theorem holds for any <math>m</math>-variate polynomials for all <math>m<n</math>.
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>.  


;Induction step''':'''
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.
For any <math>n</math>-variate polynomial <math>f(x_1,x_2,\ldots,x_n)</math>  of degree at most <math>d</math>, we write <math>f</math> as
:<math>f(x_1,x_2,\ldots,x_n)=\sum_{i=0}^kx_n^{i}f_i(x_1,x_2,\ldots,x_{n-1})</math>,
where <math>k</math> is the highest degree of <math>x_n</math>, which means the degree of <math>f_k</math> is at most <math>d-k</math> and <math>f_k\not\equiv 0</math>.


In particular, we write <math>f</math> as a sum of two parts:
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>.
:<math>f(x_1,x_2,\ldots,x_n)=x_n^k f_k(x_1,x_2,\ldots,x_{n-1})+\bar{f}(x_1,x_2,\ldots,x_n)</math>,
where both <math>f_k</math> and <math>\bar{f}</math> are polynomials, such that
* <math>f_k\not\equiv 0</math> is as above, whose degree is  at most <math>d-k</math>;
* <math>\bar{f}(x_1,x_2,\ldots,x_n)=\sum_{i=0}^{k-1}x_n^i f_i(x_1,x_2,\ldots,x_{n-1})</math>, thus <math>\bar{f}(x_1,x_2,\ldots,x_n)</math> has no <math>x_n^{k}</math> factor in any term.


By the law of total probability, we have
==== 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>
:<math>
\begin{align}
\begin{align}
&\Pr[f(r_1,r_2,\ldots,r_n)=0]\\
\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}]\\
&\Pr[f(\vec{r})=0\mid f_k(r_1,r_2,\ldots,r_{n-1})=0]\cdot\Pr[f_k(r_1,r_2,\ldots,r_{n-1})=0]\\
&=\mathbf{E}[X_i\mid X_0,\ldots,X_{i-1}]-\mathbf{E}[X_{i-1}\mid X_0,\ldots,X_{i-1}]\\
&+\Pr[f(\vec{r})=0\mid f_k(r_1,r_2,\ldots,r_{n-1})\neq0]\cdot\Pr[f_k(r_1,r_2,\ldots,r_{n-1})\neq0].
&=X_{i-1}-X_{i-1}\\
&=0.
\end{align}
\end{align}
</math>
</math>
Note that <math>f_k(r_1,r_2,\ldots,r_{n-1})</math> is a polynomial on <math>n-1</math> variables of degree <math>d-k</math> such that <math>f_k\not\equiv 0</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.
By the induction hypothesis, we have
 
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>
:<math>
\begin{align}
\begin{align}
(*)
X_n-X_0
&\qquad
&=(X_1-X_{0})+(X_2-X_1)+\cdots+(X_n-X_{n-1})\\
&\Pr[f_k(r_1,r_2,\ldots,r_{n-1})=0]\le\frac{d-k}{|S|}.
&=\sum_{i=1}^n Y_i\\
&=Z_n.
\end{align}
\end{align}
</math>
</math>


Now we look at the case conditioning on <math>f_k(r_1,r_2,\ldots,r_{n-1})\neq0</math>. Recall that <math>\bar{f}(x_1,\ldots,x_n)</math> has no <math>x_n^k</math> factor in any term, thus the condition <math>f_k(r_1,r_2,\ldots,r_{n-1})\neq0</math> guarantees that  
We then only need to upper bound the probability of the event <math>Z_n\ge t</math>.
:<math>f(r_1,\ldots,r_{n-1},x_n)=x_n^k f_k(r_1,r_2,\ldots,r_{n-1})+\bar{f}(r_1,r_2,\ldots,r_{n-1},x_n)=g_{r_1,\ldots,r_{n-1}}(x_n)</math>
 
is a nonzero univariate polynomial of <math>x_n</math> such that the degree of <math>g_{r_1,\ldots,r_{n-1}}(x_n)</math> is <math>k</math> and <math>g_{r_1,\ldots,r_{n-1}}\not\equiv 0</math>, for which we already known that the probability <math>g_{r_1,\ldots,r_{n-1}}(r_n)=0</math> is at most <math>\frac{k}{|S|}</math>.
==== Apply Markov's inequality to the moment generating function ====
Therefore,
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>
:<math>
\begin{align}
\begin{align}
(**)
\Pr\left[Z_n\ge t\right]
&\qquad
&=\Pr\left[e^{\lambda Z_n}\ge e^{\lambda t}\right]\\
&\Pr[f(\vec{r})=0\mid f_k(r_1,r_2,\ldots,r_{n-1})\neq0]=\Pr[g_{r_1,\ldots,r_{n-1}}(r_n)=0\mid f_k(r_1,r_2,\ldots,r_{n-1})\neq0]\le\frac{k}{|S|}
&\le \frac{\mathbf{E}\left[e^{\lambda Z_n}\right]}{e^{\lambda t}}.
\end{align}
\end{align}
</math>.
</math>
Substituting both <math>(*)</math> and <math>(**)</math> back in the total probability, 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 <math>\mathbf{E}\left[e^{\lambda Z_n}\right]</math>.
 
==== Bound the moment generating functions ====
The moment generating function
:<math>
:<math>
\Pr[f(r_1,r_2,\ldots,r_n)=0]
\begin{align}
\le\frac{d-k}{|S|}+\frac{k}{|S|}=\frac{d}{|S|},
\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>
</math>
which proves the theorem.
}}
}}
{{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>


= Fingerprinting =
Since <math>\mathbf{E}[X]=0</math>, we have
The polynomial identity testing algorithm in the Schwartz-Zippel theorem can be abstracted as the following framework:
:<math>
Suppose we want to compare two objects <math>X</math> and <math>Y</math>. Instead of comparing them directly, we compute random '''fingerprints''' <math>\mathrm{FING}(X)</math> and <math>\mathrm{FING}(Y)</math> of them and compare the fingerprints.
\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>


The fingerprints has the following properties:
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>.
* <math>\mathrm{FING}(\cdot)</math> is a function, meaning that if <math>X= Y</math> then <math>\mathrm{FING}(X)=\mathrm{FING}(Y)</math>.
}}
* It is much easier to compute and compare the fingerprints.
* Ideally, the domain of fingerprints is much smaller than the domain of original objects, so storing and comparing fingerprints are easy. This means the fingerprint function <math>\mathrm{FING}(\cdot)</math> cannot be an injection (one-to-one mapping), so it's possible that different <math>X</math> and <math>Y</math> are mapped to the same fingerprint. We resolve this by making fingerprint function ''randomized'', and for <math>X\neq Y</math>, we want the probability <math>\Pr[\mathrm{FING}(X)=\mathrm{FING}(Y)]</math> to be small.


In Schwartz-Zippel theorem, the objects to compare are polynomials from <math>\mathbb{F}[x_1,\ldots,x_n]</math>. Given a polynomial <math>f\in \mathbb{F}[x_1,\ldots,x_n]</math>, its fingerprint is computed as <math>\mathrm{FING}(f)=f(r_1,\ldots,r_n)</math> for <math>r_i</math> chosen independently and uniformly at random from some fixed set <math>S\subseteq\mathbb{F}</math>.
Apply the above lemma to the random variable
:<math>
(Y_n \mid X_0,\ldots,X_{n-1})
</math>


With this generic framework, for various identity testing problems, we may design different fingerprints <math>\mathrm{FING}(\cdot)</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>


== Communication protocols for Equality by fingerprinting==
Back to our analysis of the expectation <math>\mathbf{E}\left[e^{\lambda Z_n}\right]</math>, we have
Now consider again the communication model where the two players Alice with a private input <math>x\in\{0,1\}^n</math> and Bob with a private input <math>y\in\{0,1\}^n</math> together compute a function <math>f(x,y)</math> by running a communication protocol.
:<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>


We still consider the communication protocols for the equality function EQ
Apply the same analysis to <math>\mathbf{E}\left[e^{\lambda Z_{n-1}}\right]</math>, we can solve the above recursion by
:<math>
:<math>
\mathrm{EQ}(x,y)=
\begin{align}
\begin{cases}
\mathbf{E}\left[e^{\lambda Z_n}\right]
1& \mbox{if } x=y,\\
&\le \prod_{k=1}^n e^{\lambda^2c_k^2/2}\\
0& \mbox{otherwise.}
&= \exp\left(\lambda^2\sum_{k=1}^n c_k^2/2\right).
\end{cases}</math>
\end{align}
</math>


With the language of fingerprinting, this communication problem can be solved by the following generic scheme:
Go back to the Markov's inequality,
{{Theorem|Communication protocol for EQ by fingerprinting|
:<math>
'''Bob does''':
\begin{align}
:* choose a random fingerprint function <math>\mathrm{FING}(\cdot)</math> and compute the fingerprint of her input <math>\mathrm{FING}(y)</math>;
\Pr\left[Z_n\ge t\right]
:* sends both the description of <math>\mathrm{FING}(\cdot)</math> and the value of <math>\mathrm{FING}(y)</math> to Alice;
&\le \frac{\mathbf{E}\left[e^{\lambda Z_n}\right]}{e^{\lambda t}}\\
'''Upon receiving''' the description of <math>\mathrm{FING}(\cdot)</math> and the value of <math>\mathrm{FING}(y)</math>, '''Alice does''':
&\le \exp\left(\lambda^2\sum_{k=1}^n c_k^2/2-\lambda t\right).
:* computes <math>\mathrm{FING}(x)</math> and check whether <math>\mathrm{FING}(x)=\mathrm{FING}(y)</math>.
\end{align}
}}
</math>
In this way we have a randomized communication protocol for the equality function EQ with false positive. The communication cost as well as the error probability are reduced to the question of how to design this random fingerprint function <math>\mathrm{FING}(\cdot)</math> to guarantee:
# A random fingerprint function <math>\mathrm{FING}(\cdot)</math> can be described succinctly.
# The range of <math>\mathrm{FING}(\cdot)</math> is small, so the fingerprints are succinct.
# If <math>x\neq y</math>, the probability <math>\Pr[\mathrm{FING}(x)=\mathrm{FING}(y)]</math> is small.


=== Fingerprinting by PIT===
We then only need to choose a proper <math>\lambda>0</math>.
As before, we can define the fingerprint function as: for any bit-string <math>x\in\{0,1\}^n</math>,  its random fingerprint is <math>\mathrm{FING}(x)=\sum_{i=1}^n x_i r^{i}</math>, where the additions and multiplications are defined over a finite field <math>\mathbb{Z}_p</math>, and <math>r</math> is chosen uniformly at random from <math>\mathbb{Z}_p</math>, where <math>p</math> is some suitable prime which can be represented in <math>\Theta(\log n)</math> bits. More specifically, we can choose <math>p</math> to be any prime from the interval <math>[n^2, 2n^2]</math>. Due to Chebyshev's theorem, such prime must exist.  


As we have shown before, it takes <math>O(\log p)=O(\log n)</math> bits to represent <math>\mathrm{FING}(y)</math> and to describe the random function <math>\mathrm{FING}(\cdot)</math> (since it a random function <math>\mathrm{FING}(\cdot)</math> from this family is uniquely identified by a random <math>r\in\mathbb{Z}_p</math>, which can be represented within <math>\log p=O(\log n)</math> bits). And it follows easily from the fundamental theorem of algebra that for any distinct <math>x, y\in\{0,1\}^n</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>
:<math>
\Pr[\mathrm{FING}(x)=\mathrm{FING}(y)] \le \frac{n-1}{p}\le \frac{1}{n}.
\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>
</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.


=== Fingerprinting by randomized checksum===
=The Doob martingales =
Now we consider a new fingerprint function: We treat each input string <math>x\in\{0,1\}^n</math> as the binary representation of a number, and let <math>\mathrm{FING}(x)=x\bmod p</math> for some random prime <math>p</math> chosen from <math>[k]=\{0,1,\ldots,k-1\}</math>, for some <math>k</math> to be specified later.  
The following definition describes a very general approach for constructing an important type of martingales.


Now a random fingerprint function <math>\mathrm{FING}(\cdot)</math> can be uniquely identified by this random prime <math>p</math>. The new communication protocol for EQ with this fingerprint is as follows:
{{Theorem
{{Theorem|Communication protocol for EQ by random checksum|
|Definition (The Doob sequence)|
'''Bob does''':
: 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
:for some parameter <math>k</math> (to be specified),  
::<math>
:* choose a prime <math>p\in[k]</math> uniformly at random;
Y_i=\mathbf{E}[f(X_1,\ldots,X_n)\mid X_1,\ldots,X_{i}], \quad 0\le i\le n.
:* send <math>p</math> and <math>x\bmod p</math> to Alice;
</math>
'''Upon receiving''' <math>p</math> and <math>x\bmod p</math>, '''Alice does''':
: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>.
:* check whether <math>x\bmod p=y\bmod p</math>.
}}
}}
The number of bits to be communicated is obviously <math>O(\log k)</math>. When <math>x\neq y</math>, we want to upper bound the error probability <math>\Pr[x\bmod p=y\bmod p]</math>.


Suppose without loss of generality <math>x>y</math>. Let <math>z=x-y</math>. Then <math>z<2^n</math> since <math>x,y\in[2^n]</math>, and
The Doob sequence of a function defines a martingale. That is
<math>z\neq 0</math> for <math>x\neq y</math>. It holds that <math>x\equiv y\pmod p</math> if and only if <math>p\mid z</math>. Therefore, we only need to upper bound the probability
::<math>
:<math>\Pr[z\bmod p=0]</math>
\mathbf{E}[Y_i\mid X_1,\ldots,X_{i-1}]=Y_{i-1},  
for an arbitrarily fixed <math>0<z<2^n</math>, and a uniform random prime <math>p\in[k]</math>.
</math>
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>
\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 probability <math>\Pr[z\bmod p=0]</math> is computed directly as
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>.
:<math>\Pr[z\bmod p=0]\le\frac{\mbox{the number of prime divisors of }z}{\mbox{the number of primes in }[k]}</math>.


For the numerator, any positive <math>z<2^n</math> has at most <math>n</math> prime factors. To see this, by contradiction assume that <math>z</math> has more than <math>n</math> prime factors. Note that any prime number is at least 2. Then <math>z</math> must be greater than <math>2^n</math>, contradicting the fact that <math>z<2^n</math>.
The following two Doob martingales arise in evaluating the parameters of random graphs.  


For the denominator, we need to lower bound the number of primes in <math>[k]</math>. This is given by the celebrated [http://en.wikipedia.org/wiki/Prime_number_theorem '''Prime Number Theorem (PNT)'''].
;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>
: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'''.


{{Theorem|Prime Number Theorem|
;vertex exposure martingale
:Let <math>\pi(k)</math> denote the number of primes less than <math>k</math>. Then <math>\pi(k)\sim\frac{k}{\ln k}</math> as <math>k\rightarrow\infty</math>.
: 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.
}}
: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>.
:The sequence <math>Y_0,Y_1,\ldots,Y_n</math> gives a Doob martingale that is commonly called the '''vertex exposure martingale'''.


Therefore, by choosing <math>k=2n^2\ln n</math>, we have that for a <math>0<z<2^n</math>, and a random prime <math>p\in[k]</math>,
===Chromatic number===
:<math>\Pr[z\bmod p=0]\le\frac{n}{\pi(k)}\sim\frac{1}{n}</math>,
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.
which means the for any inputs <math>x,y\in\{0,1\}^n</math>, if <math>x\neq y</math>, then the false positive is bounded as
:<math>\Pr[\mathrm{FING}(x)=\mathrm{FING}(y)]\le\Pr[|x-y|\bmod p=0]\le \frac{1}{n}</math>.
Moreover, by this choice of parameter <math>k=2n^2\ln n</math>, the communication complexity of the protocol is bounded by <math>O(\log k)=O(\log n)</math>.


= Checking distinctness =
{{Theorem
Consider the following problem of '''checking distinctness''':
|Theorem [Shamir and Spencer (1987)]|
*Given a sequence <math>x_1,x_2,\ldots,x_n\in\{1,2,\ldots,n\}</math>, check whether every element of <math>\{1,2,\ldots,n\}</math> appears '''exactly''' once.
:Let <math>G\sim G(n,p)</math>. Let <math>\chi(G)</math> be the chromatic number of <math>G</math>. Then
::<math>\begin{align}
\Pr\left[|\chi(G)-\mathbf{E}[\chi(G)]|\ge t\sqrt{n}\right]\le 2e^{-t^2/2}.
\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>.
}}


Obviously this problem can be solved in linear time and linear space (in addition to the space for storing the input) by maintaining a <math>n</math>-bit vector that indicates which numbers among <math>\{1,2,\ldots,n\}</math> have appeared.
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.  


When this <math>n</math> is enormously large, <math>\Omega(n)</math> space cost is too expensive. We wonder whether we could solve this problem with a space cost (in addition to the space for storing the input) much less than <math>O(n)</math>. This can be done by fingerprinting if we tolerate a certain degree of inaccuracy.
=== 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.
{{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>.


== Fingerprinting multisets ==
:<math>
We consider the following more generalized problem, '''checking identity of multisets''':
\begin{align}
* '''Input:''' two multisets <math>A=\{a_1,a_2,\ldots, a_n\}</math> and <math>B=\{b_1,b_2,\ldots, b_n\}</math> where <math>a_1,a_2,\ldots,b_1,b_2,\ldots,b_n\in \{1,2,\ldots,n\}</math>.
|Y_i-Y_{i-1}|
* Determine whether <math>A=B</math> (multiset equivalence).
&=
\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.
}}


Here for a '''multiset''' <math>A=\{a_1,a_2,\ldots, a_n\}</math>, its elements <math>a_i</math> are not necessarily distinct. The '''multiplicity''' of an element <math>a_i</math> in a multiset <math>A</math> is the number of times <math>a_i</math> appears in <math>A</math>. Two multisets <math>A</math> and <math>B</math> are equivalent if they contain the same set of elements and the multiplicities of every element in <math>A</math> and <math>B</math> are equal.  
=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.


Obviously the above problem of checking distinctness can be treated as a special case of checking identity of multisets: by checking the identity of the multiset <math>A</math> and set <math>\{1,2,\ldots, n\}</math>.
== 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).


The following fingerprinting function for multisets was introduced by Lipton for solving multiset identity testing.
{{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>
: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>.
}}


{{Theorem|Fingerprint for multiset|
== For independent random variables ==
:Let <math>p</math> be a uniform random prime chosen from the interval <math>[(n\log n)^2,2(n\log n)^2]</math>. By Chebyshev's theorem, such prime must exist. And consider the the finite field <math>\mathbb{Z}_p=[p]</math>.
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.


:Given a multiset <math>A=\{a_1,a_2,\ldots,a_n\}</math>, we define a univariate polynomial <math>f_A\in\mathbb{Z}_p[x]</math> over the finite field <math>\mathbb{Z}_p</math> as follows:
{{Theorem
::<math>f_A(x)=\prod_{i=1}^n(x-a_i)</math>,
|Definition (Lipschitz condition)|
:where <math>+</math> and <math>\cdot</math> are defined over the finite field <math>\mathbb{Z}_p</math>.
: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.  


:We then define the random fingerprinting function as:
The diference of 1 can be replaced by arbitrary constants, which gives a generalized version of Lipschitz condition.
::<math>\mathrm{FING}(A)=f_A(r)=\prod_{i=1}^n(r-a_i)</math>,
{{Theorem
:where <math>r</math> is chosen uniformly at random from <math>\mathbb{Z}_p</math>.
|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>
}}
}}


Since all computations of <math>\mathrm{FING}(A)=\prod_{i=1}^n(r-a_i)</math> are over the finite field <math>\mathbb{Z}_p</math>, the space cost for computing the fingerprint <math>\mathrm{FING}(A)</math> is only <math>O(\log p)=O(\log n)</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>
}}


Moreover, the fingerprinting function <math>\mathrm{FING}(A)</math> is invariant under permutation of elements of the multiset <math>A=\{a_1,a_2,\ldots,a_n\}</math>, thus it is indeed a function of multisets (meaning every multiset has only one fingerprint). Therefore, if <math>A=B</math> then <math>\mathrm{FING}(A)=\mathrm{FING}(B)</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>.


For two distinct multisets <math>A\neq B</math>, it is possible that <math>\mathrm{FING}(A)=\mathrm{FING}(B)</math>, but the following theorem due to Lipton bounds this error probability of false positive.
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.


{{Theorem|Theorem (Lipton 1989)|
For any <math>a</math>, by the law of total expectation,
:Let <math>A=\{a_1,a_2,\ldots,a_n\}</math> and <math>B=\{b_1,b_2,\ldots,b_n\}</math> be two multisets whose elements are from <math>\{1,2,\ldots,n\}</math>. If <math>A\neq B</math>, then
:<math>
::<math>\Pr[\mathrm{FING}(A)= \mathrm{FING}(B)]=O\left(\frac{1}{n}\right)</math>.
\begin{align}
}}
&\quad\, \mathbf{E}\left[f(\boldsymbol{X})\mid \boldsymbol{X}_{[1,i-1]},X_i=a\right]\\
{{Proof|
&=\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]\\
Let <math>\tilde{f}_A(x)=\prod_{i=1}^n(x-a_i)</math> and <math>\tilde{f}_B(x)=\prod_{i=1}^n(x-b_i)</math> be two univariate polynomials defined over reals <math>\mathbb{R}</math>. Note that in contrast to <math>f_A(x)</math> and <math>f_B(x)</math>, the <math>+</math> and <math>\cdot</math> in <math>\tilde{f}_A(x), \tilde{f}_B(x)</math> do not modulo <math>p</math>. It is easy to verify that the polynomials <math>\tilde{f}_A(x), \tilde{f}_B(x)</math> have the following properties:
&=\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})\\
*<math>\tilde{f}_A\equiv \tilde{f}_B</math> if and only if <math>A=B</math>. Here <math>A=B</math> means the multiset equivalence.
&= \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].
*By the properties of finite field, for any value <math>r\in\mathbb{Z}_p</math>, it holds that <math>f_A(r)=\tilde{f}_A(r)\bmod p</math> and <math>f_B(r)=\tilde{f}_B(r)\bmod p</math>.
\end{align}
</math>


Therefore, assuming that <math>A\neq B</math>, we must have <math>\tilde{f}_A(x)\not\equiv \tilde{f}_B(x)</math>. Then by the law of total probability:
Let <math>a=a_i</math> and <math>b_i</math>, and take the diference. Then
:<math>
:<math>
\begin{align}
\begin{align}
\Pr[\mathrm{FING}(A)= \mathrm{FING}(B)]
&\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|\\
\Pr\left[f_A(r)=f_B(r)\mid f_A\not\equiv f_B\right]\Pr[f_A\not\equiv f_B]\\
&\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]\\
&\quad\,\,+\Pr\left[f_A(r)=f_B(r)\mid f_A\equiv f_B\right]\Pr[f_A\equiv f_B]\\
&\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})\\
&\le \Pr\left[f_A(r)=f_B(r)\mid f_A\not\equiv f_B\right]+\Pr[f_A\equiv f_B].
&=c_i.
\end{align}
\end{align}
</math>
</math>
Note that the degrees of <math>f_A,f_B</math> are at most <math>n</math> and <math>r</math> is chosen uniformly from <math>[p]</math>. By the Schwartz-Zippel theorem for univariate polynomials, the first probability
 
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>
:<math>
\Pr\left[f_A(r)=f_B(r)\mid f_A\not\equiv f_B\right]\le \frac{n}{p}=o\left(\frac{1}{n}\right),
\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>
</math>
since <math>p</math> is chosen from the interval <math>[(n\log n)^2,2(n\log n)^2]</math>.


For the second probability <math>\Pr[f_A\equiv f_B]</math>, recall that <math>\tilde{f}_A\not\equiv \tilde{f}_B</math>, therefore there is at least a non-zero coefficient <math>c\le n^n</math> in <math>\tilde{f}_A-\tilde{f}_B</math>. The event <math>f_A\equiv f_B</math> occurs only if <math>c\bmod p=0</math>, which means
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>
:<math>
\begin{align}
\begin{align}
\Pr[f_A\equiv f_B]
&\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|\\
&\le \Pr[c\bmod p=0]\\
&=\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| \\
&=\frac{\text{number of prime factors of }c}{\text{number of primes in }[(n\log n)^2,2(n\log n)^2]}\\
&\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 \frac{n\log_2n}{\pi(2(n\log n)^2)-\pi((n\log n)^2)}.
&\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}
\end{align}
</math>
</math>
By the prime number theorem, <math>\pi(N)\rightarrow \frac{N}{\ln N}</math> as <math>N\to\infty</math>. Therefore,
 
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>
:<math>
\Pr[f_A\equiv f_B]=O\left(\frac{n\log n}{n^2\log n}\right)=O\left(\frac{1}{n}\right).
\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>
</math>
Combining everything together, we have
<math>\Pr[\mathrm{FING}(A)= \mathrm{FING}(B)]=O\left(\frac{1}{n}\right)</math>.
}}

Latest revision as of 02:23, 19 September 2018

Conditional Expectations

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

[math]\displaystyle{ \mathbf{E}[Y\mid \mathcal{E}]=\sum_{y}y\Pr[Y=y\mid\mathcal{E}]. }[/math]

In particular, if the event [math]\displaystyle{ \mathcal{E} }[/math] is [math]\displaystyle{ X=a }[/math], the conditional expectation

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

defines a function

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

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

Example
Suppose that we uniformly sample a human from all human beings. Let [math]\displaystyle{ Y }[/math] be his/her height, and let [math]\displaystyle{ X }[/math] be the country where he/she is from. For any country [math]\displaystyle{ a }[/math], [math]\displaystyle{ \mathbf{E}[Y\mid X=a] }[/math] gives the average height of that country. And [math]\displaystyle{ \mathbf{E}[Y\mid X] }[/math] is the random variable which can be defined in either ways:
  • We choose a human uniformly at random from all human beings, and [math]\displaystyle{ \mathbf{E}[Y\mid X] }[/math] 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 [math]\displaystyle{ \mathbf{E}[Y\mid X] }[/math] 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 [math]\displaystyle{ X,Y }[/math] and [math]\displaystyle{ Z }[/math] be arbitrary random variables. Let [math]\displaystyle{ f }[/math] and [math]\displaystyle{ g }[/math] be arbitrary functions. Then
  1. [math]\displaystyle{ \mathbf{E}[X]=\mathbf{E}[\mathbf{E}[X\mid Y]] }[/math].
  2. [math]\displaystyle{ \mathbf{E}[X\mid Z]=\mathbf{E}[\mathbf{E}[X\mid Y,Z]\mid Z] }[/math].
  3. [math]\displaystyle{ \mathbf{E}[\mathbf{E}[f(X)g(X,Y)\mid X]]=\mathbf{E}[f(X)\cdot \mathbf{E}[g(X,Y)\mid X]] }[/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:

[math]\displaystyle{ \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]\displaystyle{ X }[/math] is the height of a uniform random human and [math]\displaystyle{ 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:

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

is the same as the first one, restricted to a particular subspace. As the previous example, inaddition to the height [math]\displaystyle{ X }[/math] and the country [math]\displaystyle{ Y }[/math], let [math]\displaystyle{ Z }[/math] be the gender of the individual. Thus, [math]\displaystyle{ \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.

The third equation:

[math]\displaystyle{ \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]\displaystyle{ X }[/math] and [math]\displaystyle{ Y }[/math] are not necessarily independent. Nevertheless, the equation follows the simple fact that conditioning on any [math]\displaystyle{ X=a }[/math], the function value [math]\displaystyle{ 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]\displaystyle{ X=a }[/math],

[math]\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]. }[/math]

The proposition holds in more general cases when [math]\displaystyle{ X, Y }[/math] and [math]\displaystyle{ Z }[/math] 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 [math]\displaystyle{ n }[/math] losses, if the [math]\displaystyle{ (n+1) }[/math]th bet wins, then it gives a net profit of

[math]\displaystyle{ 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]\displaystyle{ X_0,X_1,\ldots, }[/math], where [math]\displaystyle{ X_0 }[/math] is his initial capital, and [math]\displaystyle{ X_i }[/math] represents his capital after the [math]\displaystyle{ i }[/math]th betting. Up to different betting strategies, [math]\displaystyle{ X_i }[/math] can be arbitrarily dependent on [math]\displaystyle{ 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]\displaystyle{ X_0,\ldots,X_{i-1} }[/math], we will expect no change in the value of the present variable [math]\displaystyle{ X_{i} }[/math] on average. Random variables satisfying this property is called a martingale sequence.

Definition (martingale)
A sequence of random variables [math]\displaystyle{ X_0,X_1,\ldots }[/math] is a martingale if for all [math]\displaystyle{ i\gt 0 }[/math],
[math]\displaystyle{ \begin{align} \mathbf{E}[X_{i}\mid X_0,\ldots,X_{i-1}]=X_{i-1}. \end{align} }[/math]

Examples

coin flips
A fair coin is flipped for a number of times. Let [math]\displaystyle{ Z_j\in\{-1,1\} }[/math] denote the outcome of the [math]\displaystyle{ j }[/math]th flip. Let
[math]\displaystyle{ X_0=0\quad \mbox{ and } \quad X_i=\sum_{j\le i}Z_j }[/math].
The random variables [math]\displaystyle{ X_0,X_1,\ldots }[/math] defines a martingale.
Proof
We first observe that [math]\displaystyle{ \mathbf{E}[X_i\mid X_0,\ldots,X_{i-1}] = \mathbf{E}[X_i\mid X_{i-1}] }[/math], 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.
[math]\displaystyle{ \begin{align} \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{align} }[/math]
Polya's urn scheme
Consider an urn (just a container) that initially contains [math]\displaystyle{ b }[/math] balck balls and [math]\displaystyle{ w }[/math] white balls. At each step, we uniformly select a ball from the urn, and replace the ball with [math]\displaystyle{ c }[/math] balls of the same color. Let [math]\displaystyle{ X_0=b/(b+w) }[/math], and [math]\displaystyle{ X_i }[/math] be the fraction of black balls in the urn after the [math]\displaystyle{ i }[/math]th step. The sequence [math]\displaystyle{ X_0,X_1,\ldots }[/math] is a martingale.
edge exposure in a random graph
Consider a random graph [math]\displaystyle{ G }[/math] generated as follows. Let [math]\displaystyle{ [n] }[/math] be the set of vertices, and let [math]\displaystyle{ [m]={[n]\choose 2} }[/math] be the set of all possible edges. For convenience, we enumerate these potential edges by [math]\displaystyle{ e_1,\ldots, e_m }[/math]. For each potential edge [math]\displaystyle{ e_j }[/math], we independently flip a fair coin to decide whether the edge [math]\displaystyle{ e_j }[/math] appears in [math]\displaystyle{ G }[/math]. Let [math]\displaystyle{ I_j }[/math] be the random variable that indicates whether [math]\displaystyle{ e_j\in G }[/math]. We are interested in some graph-theoretical parameter, say chromatic number, of the random graph [math]\displaystyle{ G }[/math]. Let [math]\displaystyle{ \chi(G) }[/math] be the chromatic number of [math]\displaystyle{ G }[/math]. Let [math]\displaystyle{ X_0=\mathbf{E}[\chi(G)] }[/math], and for each [math]\displaystyle{ i\ge 1 }[/math], let [math]\displaystyle{ X_i=\mathbf{E}[\chi(G)\mid I_1,\ldots,I_{i}] }[/math], namely, the expected chromatic number of the random graph after fixing the first [math]\displaystyle{ i }[/math] 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 [math]\displaystyle{ Y_0,Y_1,\ldots }[/math] is a martingale with respect to the sequence [math]\displaystyle{ X_0,X_1,\ldots }[/math] if, for all [math]\displaystyle{ i\ge 0 }[/math], the following conditions hold:
  • [math]\displaystyle{ Y_i }[/math] is a function of [math]\displaystyle{ X_0,X_1,\ldots,X_i }[/math];
  • [math]\displaystyle{ \begin{align} \mathbf{E}[Y_{i+1}\mid X_0,\ldots,X_{i}]=Y_{i}. \end{align} }[/math]

Therefore, a sequence [math]\displaystyle{ 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

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

Azuma's Inequality
Let [math]\displaystyle{ X_0,X_1,\ldots }[/math] be a martingale such that, for all [math]\displaystyle{ k\ge 1 }[/math],
[math]\displaystyle{ |X_{k}-X_{k-1}|\le c_k, }[/math]
Then
[math]\displaystyle{ \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]

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

[math]\displaystyle{ |X_{k}-X_{k-1}|\le c_k }[/math]

is central to the proof. This condition is sometimes called the bounded difference condition. If we think of the martingale [math]\displaystyle{ X_0,X_1,\ldots }[/math] as a process evolving through time, where [math]\displaystyle{ X_i }[/math] gives some measurement at time [math]\displaystyle{ i }[/math], 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 [math]\displaystyle{ X_0,X_1,\ldots }[/math] be a martingale such that, for all [math]\displaystyle{ k\ge 1 }[/math],
[math]\displaystyle{ |X_{k}-X_{k-1}|\le c, }[/math]
Then
[math]\displaystyle{ \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]\displaystyle{ \omega(\sqrt{n}) }[/math] far away from the starting point after [math]\displaystyle{ n }[/math] steps is bounded by [math]\displaystyle{ o(1) }[/math].

Generalization

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

Azuma's Inequality (general version)
Let [math]\displaystyle{ Y_0,Y_1,\ldots }[/math] be a martingale with respect to the sequence [math]\displaystyle{ X_0,X_1,\ldots }[/math] such that, for all [math]\displaystyle{ k\ge 1 }[/math],
[math]\displaystyle{ |Y_{k}-Y_{k-1}|\le c_k, }[/math]
Then
[math]\displaystyle{ \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]\displaystyle{ Y_i }[/math] conditioning on sequence [math]\displaystyle{ 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]\displaystyle{ |X_n-X_0|\ge t }[/math], we first bound the upper tail [math]\displaystyle{ \Pr[X_n-X_0\ge t] }[/math]. The bound of the lower tail can be symmetrically proved with the [math]\displaystyle{ X_i }[/math] replaced by [math]\displaystyle{ -X_i }[/math].

Represent the deviation as the sum of differences

We define the martingale difference sequence: for [math]\displaystyle{ i\ge 1 }[/math], let

[math]\displaystyle{ Y_i=X_i-X_{i-1}. }[/math]

It holds that

[math]\displaystyle{ \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]\displaystyle{ X_0,X_1,\ldots }[/math] is a martingale and the definition of conditional expectation.

Let [math]\displaystyle{ Z_n }[/math] be the accumulated differences

[math]\displaystyle{ Z_n=\sum_{i=1}^n Y_i. }[/math]

The deviation [math]\displaystyle{ (X_n-X_0) }[/math] can be computed by the accumulated differences:

[math]\displaystyle{ \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]\displaystyle{ Z_n\ge t }[/math].

Apply Markov's inequality to the moment generating function

The event [math]\displaystyle{ Z_n\ge t }[/math] is equivalent to that [math]\displaystyle{ e^{\lambda Z_n}\ge e^{\lambda t} }[/math] for [math]\displaystyle{ \lambda\gt 0 }[/math]. Apply Markov's inequality, we have

[math]\displaystyle{ \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]\displaystyle{ \mathbf{E}\left[e^{\lambda Z_n}\right] }[/math].

Bound the moment generating functions

The moment generating function

[math]\displaystyle{ \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]\displaystyle{ \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]\displaystyle{ e^{\lambda Y_n} }[/math].

Lemma
Let [math]\displaystyle{ X }[/math] be a random variable such that [math]\displaystyle{ \mathbf{E}[X]=0 }[/math] and [math]\displaystyle{ |X|\le c }[/math]. Then for [math]\displaystyle{ \lambda\gt 0 }[/math],
[math]\displaystyle{ \mathbf{E}[e^{\lambda X}]\le e^{\lambda^2c^2/2}. }[/math]
Proof.
Observe that for [math]\displaystyle{ \lambda\gt 0 }[/math], the function [math]\displaystyle{ e^{\lambda X} }[/math] of the variable [math]\displaystyle{ X }[/math] is convex in the interval [math]\displaystyle{ [-c,c] }[/math]. We draw a line between the two endpoints points [math]\displaystyle{ (-c, e^{-\lambda c}) }[/math] and [math]\displaystyle{ (c, e^{\lambda c}) }[/math]. The curve of [math]\displaystyle{ e^{\lambda X} }[/math] lies entirely below this line. Thus,
[math]\displaystyle{ \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]\displaystyle{ \mathbf{E}[X]=0 }[/math], we have

[math]\displaystyle{ \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]

By expanding both sides as Taylor's series, it can be verified that [math]\displaystyle{ \frac{e^{\lambda c}+e^{-\lambda c}}{2}\le e^{\lambda^2c^2/2} }[/math].

[math]\displaystyle{ \square }[/math]

Apply the above lemma to the random variable

[math]\displaystyle{ (Y_n \mid X_0,\ldots,X_{n-1}) }[/math]

We have already shown that its expectation [math]\displaystyle{ \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]\displaystyle{ |Y_n|=|(X_n-X_{n-1})|\le c_n. }[/math] Thus, due to the above lemma, it holds that

[math]\displaystyle{ \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]\displaystyle{ \mathbf{E}\left[e^{\lambda Z_n}\right] }[/math], we have

[math]\displaystyle{ \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]\displaystyle{ \mathbf{E}\left[e^{\lambda Z_{n-1}}\right] }[/math], we can solve the above recursion by

[math]\displaystyle{ \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]\displaystyle{ \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]\displaystyle{ \lambda\gt 0 }[/math].

Optimization

By choosing [math]\displaystyle{ \lambda=\frac{t}{\sum_{k=1}^n c_k^2} }[/math], we have that

[math]\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). }[/math]

Thus, the probability

[math]\displaystyle{ \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]\displaystyle{ X_i }[/math] by [math]\displaystyle{ -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.

Definition (The Doob sequence)
The Doob sequence of a function [math]\displaystyle{ f }[/math] with respect to a sequence of random variables [math]\displaystyle{ X_1,\ldots,X_n }[/math] is defined by
[math]\displaystyle{ 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]\displaystyle{ Y_0=\mathbf{E}[f(X_1,\ldots,X_n)] }[/math] and [math]\displaystyle{ Y_n=f(X_1,\ldots,X_n) }[/math].

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

[math]\displaystyle{ \mathbf{E}[Y_i\mid X_1,\ldots,X_{i-1}]=Y_{i-1}, }[/math]

for any [math]\displaystyle{ 0\le i\le n }[/math].

To prove this claim, we recall the definition that [math]\displaystyle{ Y_i=\mathbf{E}[f(X_1,\ldots,X_n)\mid X_1,\ldots,X_{i}] }[/math], thus,

[math]\displaystyle{ \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]\displaystyle{ f(X_1,\ldots,X_n) }[/math] of random variables [math]\displaystyle{ X_1,\ldots,X_n }[/math]. The Doob sequence [math]\displaystyle{ Y_0,Y_1,\ldots,Y_n }[/math] represents a sequence of refined estimates of the value of [math]\displaystyle{ f(X_1,\ldots,X_n) }[/math], gradually using more information on the values of the random variables [math]\displaystyle{ X_1,\ldots,X_n }[/math]. The first element [math]\displaystyle{ Y_0 }[/math] is just the expectation of [math]\displaystyle{ f(X_1,\ldots,X_n) }[/math]. Element [math]\displaystyle{ Y_i }[/math] is the expected value of [math]\displaystyle{ f(X_1,\ldots,X_n) }[/math] when the values of [math]\displaystyle{ X_1,\ldots,X_{i} }[/math] are known, and [math]\displaystyle{ Y_n=f(X_1,\ldots,X_n) }[/math] when [math]\displaystyle{ f(X_1,\ldots,X_n) }[/math] is fully determined by [math]\displaystyle{ X_1,\ldots,X_n }[/math].

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

edge exposure martingale
Let [math]\displaystyle{ G }[/math] be a random graph on [math]\displaystyle{ n }[/math] vertices. Let [math]\displaystyle{ 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]\displaystyle{ m={n\choose 2} }[/math]. Fix an arbitrary numbering of potential edges between the [math]\displaystyle{ n }[/math] vertices, and denote the edges as [math]\displaystyle{ e_1,\ldots,e_m }[/math]. Let
[math]\displaystyle{ X_i=\begin{cases} 1& \mbox{if }e_i\in G,\\ 0& \mbox{otherwise}. \end{cases} }[/math]
Let [math]\displaystyle{ Y_0=\mathbf{E}[f(G)] }[/math] and for [math]\displaystyle{ i=1,\ldots,m }[/math], let [math]\displaystyle{ Y_i=\mathbf{E}[f(G)\mid X_1,\ldots,X_i] }[/math].
The sequence [math]\displaystyle{ Y_0,Y_1,\ldots,Y_n }[/math] 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 [math]\displaystyle{ [n] }[/math]. Let [math]\displaystyle{ X_i }[/math] be the subgraph of [math]\displaystyle{ G }[/math] induced by the vertex set [math]\displaystyle{ [i] }[/math], i.e. the first [math]\displaystyle{ i }[/math] vertices.
Let [math]\displaystyle{ Y_0=\mathbf{E}[f(G)] }[/math] and for [math]\displaystyle{ i=1,\ldots,n }[/math], let [math]\displaystyle{ Y_i=\mathbf{E}[f(G)\mid X_1,\ldots,X_i] }[/math].
The sequence [math]\displaystyle{ Y_0,Y_1,\ldots,Y_n }[/math] gives a Doob martingale that is commonly called the vertex exposure martingale.

Chromatic number

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

Theorem [Shamir and Spencer (1987)]
Let [math]\displaystyle{ G\sim G(n,p) }[/math]. Let [math]\displaystyle{ \chi(G) }[/math] be the chromatic number of [math]\displaystyle{ G }[/math]. Then
[math]\displaystyle{ \begin{align} \Pr\left[|\chi(G)-\mathbf{E}[\chi(G)]|\ge t\sqrt{n}\right]\le 2e^{-t^2/2}. \end{align} }[/math]
Proof.
Consider the vertex exposure martingale
[math]\displaystyle{ Y_i=\mathbf{E}[\chi(G)\mid X_1,\ldots,X_i] }[/math]

where each [math]\displaystyle{ X_k }[/math] exposes the induced subgraph of [math]\displaystyle{ G }[/math] on vertex set [math]\displaystyle{ [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]\displaystyle{ |Y_i-Y_{i-1}|\le 1 }[/math]

is satisfied. Now apply the Azuma's inequality for the martingale [math]\displaystyle{ Y_1,\ldots,Y_n }[/math] with respect to [math]\displaystyle{ X_1,\ldots,X_n }[/math].

[math]\displaystyle{ \square }[/math]

For [math]\displaystyle{ 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.

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 [math]\displaystyle{ X=\sum_{i=1}^nX_i }[/math], where [math]\displaystyle{ X_1,\ldots,X_n }[/math] are independent random variables with [math]\displaystyle{ a_i\le X_i\le b_i }[/math] for each [math]\displaystyle{ 1\le i\le n }[/math]. Let [math]\displaystyle{ \mu=\mathbf{E}[X] }[/math]. Then
[math]\displaystyle{ \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]\displaystyle{ Y_i=\mathbf{E}\left[\sum_{j=1}^n X_j\,\Big|\, X_1,\ldots,X_{i}\right] }[/math]. Obviously [math]\displaystyle{ Y_0=\mu }[/math] and [math]\displaystyle{ Y_n=X }[/math].
[math]\displaystyle{ \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]\displaystyle{ Y_0,\ldots,Y_n }[/math] with respect to [math]\displaystyle{ X_1,\ldots, X_n }[/math], the Hoeffding's inequality is proved.

[math]\displaystyle{ \square }[/math]

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]\displaystyle{ X_1,\ldots,X_n }[/math] and a function [math]\displaystyle{ 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 (Method of averaged bounded differences)
Let [math]\displaystyle{ \boldsymbol{X}=(X_1,\ldots, X_n) }[/math] be arbitrary random variables and let [math]\displaystyle{ f }[/math] be a function of [math]\displaystyle{ X_0,X_1,\ldots, X_n }[/math] satisfying that, for all [math]\displaystyle{ 1\le i\le n }[/math],
[math]\displaystyle{ |\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]
Then
[math]\displaystyle{ \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]\displaystyle{ Y_0,Y_1,\ldots,Y_n }[/math] by setting [math]\displaystyle{ Y_0=\mathbf{E}[f(X_1,\ldots,X_n)] }[/math] and, for [math]\displaystyle{ 1\le i\le n }[/math], [math]\displaystyle{ 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]\displaystyle{ Y_0,Y_1,\ldots,Y_n }[/math].
[math]\displaystyle{ \square }[/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.

Definition (Lipschitz condition)
A function [math]\displaystyle{ f(x_1,\ldots,x_n) }[/math] satisfies the Lipschitz condition, if for any [math]\displaystyle{ x_1,\ldots,x_n }[/math] and any [math]\displaystyle{ y_i }[/math],
[math]\displaystyle{ \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.

Definition (Lipschitz condition, general version)
A function [math]\displaystyle{ f(x_1,\ldots,x_n) }[/math] satisfies the Lipschitz condition with constants [math]\displaystyle{ c_i }[/math], [math]\displaystyle{ 1\le i\le n }[/math], if for any [math]\displaystyle{ x_1,\ldots,x_n }[/math] and any [math]\displaystyle{ y_i }[/math],
[math]\displaystyle{ \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.

Corollary (Method of bounded differences)
Let [math]\displaystyle{ \boldsymbol{X}=(X_1,\ldots, X_n) }[/math] be [math]\displaystyle{ n }[/math] independent random variables and let [math]\displaystyle{ f }[/math] be a function satisfying the Lipschitz condition with constants [math]\displaystyle{ c_i }[/math], [math]\displaystyle{ 1\le i\le n }[/math]. Then
[math]\displaystyle{ \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]\displaystyle{ \boldsymbol{X}_{[i,j]}=(X_i,X_{i+1},\ldots, X_j) }[/math] for any [math]\displaystyle{ 1\le i\le j\le n }[/math].

We first show that the Lipschitz condition with constants [math]\displaystyle{ c_i }[/math], [math]\displaystyle{ 1\le i\le n }[/math], implies another condition called the averaged Lipschitz condition (ALC): for any [math]\displaystyle{ a_i,b_i }[/math], [math]\displaystyle{ 1\le i\le n }[/math],

[math]\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|\le c_i. }[/math]

And this condition implies the averaged bounded difference condition: for all [math]\displaystyle{ 1\le i\le n }[/math],

[math]\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|\le c_i. }[/math]

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

For any [math]\displaystyle{ a }[/math], by the law of total expectation,

[math]\displaystyle{ \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]\displaystyle{ a=a_i }[/math] and [math]\displaystyle{ b_i }[/math], and take the diference. Then

[math]\displaystyle{ \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]\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]}]. }[/math]

We can trivially write [math]\displaystyle{ \mathbf{E}\left[f(\boldsymbol{X})\mid \boldsymbol{X}_{[1,i]}\right] }[/math] as

[math]\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]. }[/math]

Hence, the difference is

[math]\displaystyle{ \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.

[math]\displaystyle{ \square }[/math]

Applications

Occupancy problem

Throwing [math]\displaystyle{ m }[/math] balls uniformly and independently at random to [math]\displaystyle{ 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]\displaystyle{ f:[m]\rightarrow[n] }[/math] be a uniform random function from [math]\displaystyle{ [m]\rightarrow[n] }[/math]. We ask for the number of [math]\displaystyle{ i\in[n] }[/math] that [math]\displaystyle{ f^{-1}(i) }[/math] is empty.

For any [math]\displaystyle{ i\in[n] }[/math], let [math]\displaystyle{ X_i }[/math] indicate the emptiness of bin [math]\displaystyle{ i }[/math]. Let [math]\displaystyle{ X=\sum_{i=1}^nX_i }[/math] be the number of empty bins.

[math]\displaystyle{ \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]\displaystyle{ \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]\displaystyle{ X }[/math] deviates from this expectation. The complication here is that [math]\displaystyle{ X_i }[/math] are not independent. So we alternatively look at a sequence of independent random variables [math]\displaystyle{ Y_1,\ldots, Y_m }[/math], where [math]\displaystyle{ Y_j\in[n] }[/math] represents the bin into which the [math]\displaystyle{ j }[/math]th ball falls. Clearly [math]\displaystyle{ X }[/math] is function of [math]\displaystyle{ Y_1,\ldots, Y_m }[/math].

We than observe that changing the value of any [math]\displaystyle{ Y_i }[/math] can change the value of [math]\displaystyle{ 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]\displaystyle{ Y_1,\ldots, Y_m }[/math], [math]\displaystyle{ X }[/math] satisfies the Lipschitz condition. Apply the method of bounded differences, it holds that

[math]\displaystyle{ \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]\displaystyle{ n }[/math] and [math]\displaystyle{ m }[/math], the number of empty bins is tightly concentrated around [math]\displaystyle{ n\left(1-\frac{1}{n}\right)^m\approx \frac{n}{e^{m/n}} }[/math]

Pattern Matching

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

By the linearity of expectation, it is obvious that

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

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

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

[math]\displaystyle{ \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]\displaystyle{ u_1,\ldots,u_n }[/math] be [math]\displaystyle{ n }[/math] unit vectors from some normed space. That is, [math]\displaystyle{ \|u_i\|=1 }[/math] for any [math]\displaystyle{ 1\le i\le n }[/math], where [math]\displaystyle{ \|\cdot\| }[/math] denote the vector norm (e.g. [math]\displaystyle{ \ell_1,\ell_2,\ell_\infty }[/math]) of the space.

Let [math]\displaystyle{ \epsilon_1,\ldots,\epsilon_n\in\{-1,+1\} }[/math] be independently chosen and [math]\displaystyle{ \Pr[\epsilon_i=-1]=\Pr[\epsilon_i=1]=1/2 }[/math].

Let

[math]\displaystyle{ v=\epsilon_1u_1+\cdots+\epsilon_nu_n, }[/math]

and

[math]\displaystyle{ 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]\displaystyle{ X }[/math] is well concentrated around its mean.

[math]\displaystyle{ X }[/math] is a function of independent random variables [math]\displaystyle{ \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]\displaystyle{ u_i }[/math] can only change the value of [math]\displaystyle{ X }[/math] for at most 2, thus [math]\displaystyle{ X }[/math] satisfies the Lipschitz condition with constant 2. The concentration result follows by applying the method of bounded differences:

[math]\displaystyle{ \Pr[|X-\mathbf{E}[X]|\ge 2t\sqrt{n}]\le 2e^{-t^2/2}. }[/math]
Retrieved from "https://tcs.nju.edu.cn/wiki/index.php?title=高级算法_(Fall_2018)/Fingerprinting&oldid=8308"