高级算法 (Fall 2019)/Basic tail inequalities and 组合数学 (Fall 2019)/Problem Set 4: Difference between pages

From TCS Wiki
(Difference between pages)
Jump to navigation Jump to search
VisualWikitext
imported>Etone
(Created page with "=Markov's Inequality= One of the most natural information about a random variable is its expectation, which is the first moment of the random variable. Markov's inequality dr...")
 
imported>Etone
No edit summary
 
Line 1: Line 1:
=Markov's Inequality=
== Problem 1 ==
(Matching vs. Star)


One of the most natural information about a random variable is its expectation, which is the first moment of the random variable. Markov's inequality draws a tail bound for a random variable from its expectation.
Given a graph <math>G(V,E)</math>, a ''matching'' is a subset <math>M\subseteq E</math> of edges such that there are no two edges in <math>M</math> sharing a vertex, and a ''star'' is a subset <math>S\subseteq E</math> of edges such that every pair <math>e_1,e_2\in S</math> of distinct edges in <math>S</math> share the same vertex <math>v</math>.
{{Theorem
|Theorem (Markov's Inequality)|
:Let <math>X</math> be a random variable assuming only nonnegative values. Then, for all <math>t>0</math>,
::<math>\begin{align}
\Pr[X\ge t]\le \frac{\mathbf{E}[X]}{t}.
\end{align}</math>
}}
{{Proof| Let <math>Y</math> be the indicator such that
:<math>\begin{align}
Y &=
\begin{cases}
1 & \mbox{if }X\ge t,\\
0 & \mbox{otherwise.}
\end{cases}
\end{align}</math>


It holds that <math>Y\le\frac{X}{t}</math>. Since <math>Y</math> is 0-1 valued, <math>\mathbf{E}[Y]=\Pr[Y=1]=\Pr[X\ge t]</math>. Therefore,
Prove that any graph <math>G</math> containing more than <math>2(k-1)^2</math> edges either contains a matching of size <math>k</math> or a star of size <math>k</math>.
:<math>
\Pr[X\ge t]
=
\mathbf{E}[Y]
\le
\mathbf{E}\left[\frac{X}{t}\right]
=\frac{\mathbf{E}[X]}{t}.
</math>
}}


== Generalization ==
(Hint: Learn from the proof of Erdos-Rado's sunflower lemma.)
For any random variable <math>X</math>, for an arbitrary non-negative real function <math>h</math>, the <math>h(X)</math> is a non-negative random variable. Applying Markov's inequality, we directly have that
:<math>
\Pr[h(X)\ge t]\le\frac{\mathbf{E}[h(X)]}{t}.
</math>


This trivial application of Markov's inequality gives us a powerful tool for proving tail inequalities. With the function <math>h</math> which extracts more information about the random variable, we can prove sharper tail inequalities.
== Problem 2 ==
(Frankl 1986)


=Chebyshev's inequality=
Let <math>\mathcal{F}\subseteq {[n]\choose k}</math> be a <math>k</math>-uniform family, and suppose that it satisfies that <math>A\cap B \not\subset C</math> for any <math>A,B,C\in\mathcal{F}</math>.
* Fix any <math>B\in\mathcal{F}</math>. Show that the family <math>\{A\cap B\mid A\in\mathcal{F}, A\neq B\}</math> is an anti chain.
* Show that <math>|\mathcal{F}|\le 1+{k\choose \lfloor k/2\rfloor}</math>.


== Variance ==
==Problem 3 ==
{{Theorem
An <math>n</math>-player tournament (竞赛图) <math>T([n],E)</math> is said to be '''transitive''', if there exists a permutation <math>\pi</math> of <math>[n]</math> such that <math>\pi_i<\pi_j</math> for every <math>(i,j)\in E</math>.
|Definition (variance)|
:The '''variance''' of a random variable <math>X</math> is defined as
::<math>\begin{align}
\mathbf{Var}[X]=\mathbf{E}\left[(X-\mathbf{E}[X])^2\right]=\mathbf{E}\left[X^2\right]-(\mathbf{E}[X])^2.
\end{align}</math>
:The '''standard deviation''' of random variable <math>X</math> is
::<math>
\delta[X]=\sqrt{\mathbf{Var}[X]}.
</math>
}}


The variance is the diagonal case for '''covariance'''.
Show that for any <math>k\ge 3</math>, there exists a finite <math>N(k)</math> such that every tournament of <math>n\ge N(k)</math> players contains a transitive sub-tournament of <math>k</math> players. Express <math>N(k)</math> in terms of Ramsey number.
{{Theorem
|Definition (covariance)|
:The '''covariance''' of two random variables <math>X</math> and <math>Y</math> is
::<math>\begin{align}
\mathbf{Cov}(X,Y)=\mathbf{E}\left[(X-\mathbf{E}[X])(Y-\mathbf{E}[Y])\right].
\end{align}</math>
}}


We have the following theorem for the variance of sum.
==Problem 4==
 
We color each non-empty subset of <math>[n]=\{1,2,\ldots,n\}</math> with one of the <math>r</math> colors in <math>[r]</math>. Show that for any finite <math>r</math> there is a finite <math>N</math> such that for all <math>n\ge </math>$, for any <math>r</math>-coloring of all non-empty subsets of <math>[n]</math>, there always exist <math>1\le i<j<k\le n</math> such that the intervals <math>[i,j)=\{i,i+1,\ldots, j-1\}</math>, <math>[j,k)=\{j,j+1,\ldots, k-1\}</math> and <math>[i,k)=\{i,i+1,\ldots, k-1\}</math> are all assigned with the same color by the <math>r</math>-coloring.
{{Theorem
|Theorem|
:For any two random variables <math>X</math> and <math>Y</math>,
::<math>\begin{align}
\mathbf{Var}[X+Y]=\mathbf{Var}[X]+\mathbf{Var}[Y]+2\mathbf{Cov}(X,Y).
\end{align}</math>
:Generally, for any random variables <math>X_1,X_2,\ldots,X_n</math>,
::<math>\begin{align}
\mathbf{Var}\left[\sum_{i=1}^n X_i\right]=\sum_{i=1}^n\mathbf{Var}[X_i]+\sum_{i\neq j}\mathbf{Cov}(X_i,X_j).
\end{align}</math>
}}
{{Proof| The equation for two variables is directly due to the definition of variance and covariance. The equation for <math>n</math> variables can be deduced from the equation for two variables.
}}
 
For independent random variables, the expectation of a product equals the product of expectations.
{{Theorem
|Theorem|
:For any two independent random variables <math>X</math> and <math>Y</math>,
::<math>\begin{align}
\mathbf{E}[X\cdot Y]=\mathbf{E}[X]\cdot\mathbf{E}[Y].
\end{align}</math>
}}
{{Proof|
:<math>
\begin{align}
\mathbf{E}[X\cdot Y]
&=
\sum_{x,y}xy\Pr[X=x\wedge Y=y]\\
&=
\sum_{x,y}xy\Pr[X=x]\Pr[Y=y]\\
&=
\sum_{x}x\Pr[X=x]\sum_{y}y\Pr[Y=y]\\
&=
\mathbf{E}[X]\cdot\mathbf{E}[Y].
\end{align}
</math>
}}
 
Consequently, covariance of independent random variables is always zero.
{{Theorem
|Theorem|
:For any two independent random variables <math>X</math> and <math>Y</math>,
::<math>\begin{align}
\mathbf{Cov}(X,Y)=0.
\end{align}</math>
}}
{{Proof|
:<math>\begin{align}
\mathbf{Cov}(X,Y)
&=\mathbf{E}\left[(X-\mathbf{E}[X])(Y-\mathbf{E}[Y])\right]\\
&= \mathbf{E}\left[X-\mathbf{E}[X]\right]\mathbf{E}\left[Y-\mathbf{E}[Y]\right] &\qquad(\mbox{Independence})\\
&=0.
\end{align}</math>
}}
 
The variance of the sum of pairwise independent random variables is equal to the sum of variances.
{{Theorem
|Theorem|
:For '''pairwise''' independent random variables <math>X_1,X_2,\ldots,X_n</math>,
::<math>\begin{align}
\mathbf{Var}\left[\sum_{i=1}^n X_i\right]=\sum_{i=1}^n\mathbf{Var}[X_i].
\end{align}</math>
}}
 
;Remark
:The theorem holds for '''pairwise''' independent random variables, a much weaker independence requirement than the '''mutual''' independence. This makes the second-moment methods very useful for pairwise independent random variables.
 
=== Variance of binomial distribution ===
For a Bernoulli trial with parameter <math>p</math>.
:<math>
X=\begin{cases}
1& \mbox{with probability }p\\
0& \mbox{with probability }1-p
\end{cases}
</math>
The variance is
:<math>
\mathbf{Var}[X]=\mathbf{E}[X^2]-(\mathbf{E}[X])^2=\mathbf{E}[X]-(\mathbf{E}[X])^2=p-p^2=p(1-p).
</math>
 
Let <math>Y</math> be a binomial random variable with parameter <math>n</math> and <math>p</math>, i.e. <math>Y=\sum_{i=1}^nY_i</math>, where <math>Y_i</math>'s are i.i.d. Bernoulli trials with parameter <math>p</math>. The variance is
:<math>
\begin{align}
\mathbf{Var}[Y]
&=
\mathbf{Var}\left[\sum_{i=1}^nY_i\right]\\
&=
\sum_{i=1}^n\mathbf{Var}\left[Y_i\right] &\qquad (\mbox{Independence})\\
&=
\sum_{i=1}^np(1-p) &\qquad (\mbox{Bernoulli})\\
&=
p(1-p)n.
\end{align}
</math>
 
== Chebyshev's inequality ==
{{Theorem
|Theorem (Chebyshev's Inequality)|
:For any <math>t>0</math>,
::<math>\begin{align}
\Pr\left[|X-\mathbf{E}[X]| \ge t\right] \le \frac{\mathbf{Var}[X]}{t^2}.
\end{align}</math>
}}
{{Proof| Observe that
:<math>\Pr[|X-\mathbf{E}[X]| \ge t] = \Pr[(X-\mathbf{E}[X])^2 \ge t^2].</math>
Since <math>(X-\mathbf{E}[X])^2</math> is a nonnegative random variable, we can apply Markov's inequality, such that
:<math>
\Pr[(X-\mathbf{E}[X])^2 \ge t^2] \le
\frac{\mathbf{E}[(X-\mathbf{E}[X])^2]}{t^2}
=\frac{\mathbf{Var}[X]}{t^2}.
</math>
}}

Revision as of 05:38, 11 December 2019

Problem 1

(Matching vs. Star)

Given a graph [math]\displaystyle{ G(V,E) }[/math], a matching is a subset [math]\displaystyle{ M\subseteq E }[/math] of edges such that there are no two edges in [math]\displaystyle{ M }[/math] sharing a vertex, and a star is a subset [math]\displaystyle{ S\subseteq E }[/math] of edges such that every pair [math]\displaystyle{ e_1,e_2\in S }[/math] of distinct edges in [math]\displaystyle{ S }[/math] share the same vertex [math]\displaystyle{ v }[/math].

Prove that any graph [math]\displaystyle{ G }[/math] containing more than [math]\displaystyle{ 2(k-1)^2 }[/math] edges either contains a matching of size [math]\displaystyle{ k }[/math] or a star of size [math]\displaystyle{ k }[/math].

(Hint: Learn from the proof of Erdos-Rado's sunflower lemma.)

Problem 2

(Frankl 1986)

Let [math]\displaystyle{ \mathcal{F}\subseteq {[n]\choose k} }[/math] be a [math]\displaystyle{ k }[/math]-uniform family, and suppose that it satisfies that [math]\displaystyle{ A\cap B \not\subset C }[/math] for any [math]\displaystyle{ A,B,C\in\mathcal{F} }[/math].

  • Fix any [math]\displaystyle{ B\in\mathcal{F} }[/math]. Show that the family [math]\displaystyle{ \{A\cap B\mid A\in\mathcal{F}, A\neq B\} }[/math] is an anti chain.
  • Show that [math]\displaystyle{ |\mathcal{F}|\le 1+{k\choose \lfloor k/2\rfloor} }[/math].

Problem 3

An [math]\displaystyle{ n }[/math]-player tournament (竞赛图) [math]\displaystyle{ T([n],E) }[/math] is said to be transitive, if there exists a permutation [math]\displaystyle{ \pi }[/math] of [math]\displaystyle{ [n] }[/math] such that [math]\displaystyle{ \pi_i\lt \pi_j }[/math] for every [math]\displaystyle{ (i,j)\in E }[/math].

Show that for any [math]\displaystyle{ k\ge 3 }[/math], there exists a finite [math]\displaystyle{ N(k) }[/math] such that every tournament of [math]\displaystyle{ n\ge N(k) }[/math] players contains a transitive sub-tournament of [math]\displaystyle{ k }[/math] players. Express [math]\displaystyle{ N(k) }[/math] in terms of Ramsey number.

Problem 4

We color each non-empty subset of [math]\displaystyle{ [n]=\{1,2,\ldots,n\} }[/math] with one of the [math]\displaystyle{ r }[/math] colors in [math]\displaystyle{ [r] }[/math]. Show that for any finite [math]\displaystyle{ r }[/math] there is a finite [math]\displaystyle{ N }[/math] such that for all [math]\displaystyle{ n\ge }[/math]$, for any [math]\displaystyle{ r }[/math]-coloring of all non-empty subsets of [math]\displaystyle{ [n] }[/math], there always exist [math]\displaystyle{ 1\le i\lt j\lt k\le n }[/math] such that the intervals [math]\displaystyle{ [i,j)=\{i,i+1,\ldots, j-1\} }[/math], [math]\displaystyle{ [j,k)=\{j,j+1,\ldots, k-1\} }[/math] and [math]\displaystyle{ [i,k)=\{i,i+1,\ldots, k-1\} }[/math] are all assigned with the same color by the [math]\displaystyle{ r }[/math]-coloring.

Retrieved from "https://tcs.nju.edu.cn/wiki/index.php?title=高级算法_(Fall_2019)/Basic_tail_inequalities&oldid=9086"