高级算法 (Fall 2021)/Basic tail inequalities and 高级算法 (Fall 2021)/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>TCSseminar
 
Line 1: Line 1:
=Markov's Inequality=
*每道题目的解答都要有<font color="red" size=5>完整的解题过程</font>。中英文不限。


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.
== Problem 1 ==
{{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,
== Problem 2 ==
:<math>
A ''<math>k</math>-uniform hypergraph'' is an ordered pair <math>G=(V,E)</math>, where <math>V</math> denotes the set of vertices and <math>E</math> denotes the set of edges. Moreover, each edge in <math>E</math> now contains <math>k</math> distinct vertices, instead of <math>2</math> (so a <math>2</math>-uniform hypergraph is just what we normally call a graph).
\Pr[X\ge t]
A hypergraph is <math>k</math>-regular if all vertices have degree <math>k</math>; that is, each vertex is exactly contained within <math>k</math> hypergraph edges.
=
\mathbf{E}[Y]
\le
\mathbf{E}\left[\frac{X}{t}\right]
=\frac{\mathbf{E}[X]}{t}.
</math>
}}
 
== Generalization ==
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.
 
=Chebyshev's inequality=
 
== Variance ==
{{Theorem
|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'''.
{{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.
 
{{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.
Show that for sufficiently large <math>k</math>, the vertices of a <math>k</math>-uniform, <math>k</math>-regular hypergraph can be <math>2</math>-colored so that no edge is monochromatic.
{{Theorem
What's the smallest value of <math>k</math> you can achieve?
|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
== Problem 3 ==
: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.
Suppose we have graphs <math>G=(V,E)</math> and <math>H=(V,F)</math> on the same vertex set.
We wish to partition <math>V</math> into clusters <math>V_1,V_2,\cdots</math> so as to maximise:
:<math>(\#\text{ of edges in }E\text{ that lie within clusters})+(\#\text{ of edges in }F\text{ that lie between clusters}).</math>


=== Variance of binomial distribution ===
* Show that the following SDP is an upperbound on this.
For a Bernoulli trial with parameter <math>p</math>.
:::<math>
:<math>
\text{maximize} &&& \sum_{(u,v)\in E}\langle x_u,x_v\rangle+\sum_{(u,v)\in F}(1-\langle x_u,x_v\rangle) \\
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}
\begin{align}
\mathbf{Var}[Y]
\text{subject to} && \langle x_u,x_u\rangle & =1, & \forall u & \in V, \\
&=
&& \langle x_u,x_v\rangle & \ge0, & \forall u,v & \in V, \\
\mathbf{Var}\left[\sum_{i=1}^nY_i\right]\\
&& x_u & \in R^n, & \forall u & \in V.
&=
\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}
\end{align}
</math>
</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 08:10, 20 December 2021

  • 每道题目的解答都要有完整的解题过程。中英文不限。

Problem 1

Problem 2

A [math]\displaystyle{ k }[/math]-uniform hypergraph is an ordered pair [math]\displaystyle{ G=(V,E) }[/math], where [math]\displaystyle{ V }[/math] denotes the set of vertices and [math]\displaystyle{ E }[/math] denotes the set of edges. Moreover, each edge in [math]\displaystyle{ E }[/math] now contains [math]\displaystyle{ k }[/math] distinct vertices, instead of [math]\displaystyle{ 2 }[/math] (so a [math]\displaystyle{ 2 }[/math]-uniform hypergraph is just what we normally call a graph). A hypergraph is [math]\displaystyle{ k }[/math]-regular if all vertices have degree [math]\displaystyle{ k }[/math]; that is, each vertex is exactly contained within [math]\displaystyle{ k }[/math] hypergraph edges.

Show that for sufficiently large [math]\displaystyle{ k }[/math], the vertices of a [math]\displaystyle{ k }[/math]-uniform, [math]\displaystyle{ k }[/math]-regular hypergraph can be [math]\displaystyle{ 2 }[/math]-colored so that no edge is monochromatic. What's the smallest value of [math]\displaystyle{ k }[/math] you can achieve?

Problem 3

Suppose we have graphs [math]\displaystyle{ G=(V,E) }[/math] and [math]\displaystyle{ H=(V,F) }[/math] on the same vertex set. We wish to partition [math]\displaystyle{ V }[/math] into clusters [math]\displaystyle{ V_1,V_2,\cdots }[/math] so as to maximise:

[math]\displaystyle{ (\#\text{ of edges in }E\text{ that lie within clusters})+(\#\text{ of edges in }F\text{ that lie between clusters}). }[/math]
  • Show that the following SDP is an upperbound on this.
[math]\displaystyle{ \text{maximize} &&& \sum_{(u,v)\in E}\langle x_u,x_v\rangle+\sum_{(u,v)\in F}(1-\langle x_u,x_v\rangle) \\ \begin{align} \text{subject to} && \langle x_u,x_u\rangle & =1, & \forall u & \in V, \\ && \langle x_u,x_v\rangle & \ge0, & \forall u,v & \in V, \\ && x_u & \in R^n, & \forall u & \in V. \end{align} }[/math]
Retrieved from "https://tcs.nju.edu.cn/wiki/index.php?title=高级算法_(Fall_2021)/Basic_tail_inequalities&oldid=9698"