imported>TCSseminar |
imported>Etone |
| Line 1: |
Line 1: |
| *作业电子版于2019/11/5 23:59 之前提交到邮箱 <font color=blue>njuadvalg@163.com</font>
| | == Problem 1 == |
| *每道题目的解答都要有<font color="red" size=5>完整的解题过程</font>。中英文不限。
| | (Matching vs. Star) |
|
| |
|
| == Problem 1==
| | 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>. |
| Let <math>X</math> be a real-valued random variable with finite <math>\mathbb{E}[X]</math> and finite <math>\mathbb{E}\left[\mathrm{e}^{\lambda X}\right]</math> for all <math>\lambda\ge 0</math>. We define the '''log-moment-generating function''' as
| |
| :<math>\Psi_X(\lambda):=\ln\mathbb{E}[\mathrm{e}^{\lambda X}] \quad\text{ for all }\lambda\ge 0</math>,
| |
| and its ''dual function'':
| |
| :<math>\Psi_X^*(t):=\sup_{\lambda\ge 0}(\lambda t-\Psi_X(\lambda))</math>.
| |
| Assume that <math>X</math> is NOT almost surely constant. Then due to the convexity of <math>\mathrm{e}^{\lambda X}</math> with respect to <math>\lambda</math>, the function <math>\Psi_X(\lambda)</math> is ''strictly'' convex over <math>\lambda\ge 0</math>.
| |
| *Prove the following Chernoff bound:
| |
| ::<math>\Pr[X\ge t]\le\exp(-\Psi_X^*(t))</math>.
| |
| :In particular if <math>\Psi_X(\lambda)</math> is continuously differentiable, prove that the supreme in <math>\Psi_X^*(t)</math> is achieved at the unique <math>\lambda\ge 0</math> satisfying
| |
| ::<math>\Psi_X'(\lambda)=t</math>
| |
| :where <math>\Psi_X'(\lambda)</math> denotes the derivative of <math>\Psi_X(\lambda)</math> with respect to <math>\lambda</math>.
| |
|
| |
|
| *'''Normal random variables.''' Let <math>X\sim \mathrm{N}(\mu,\sigma)</math> be a Gaussian random variable with mean <math>\mu</math> and standard deviation <math>\sigma</math>. What are the <math>\Psi_X(\lambda)</math> and <math>\Psi_X^*(t)</math>? And give a tail inequality to upper bound the probability <math>\Pr[X\ge t]</math>.
| | 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>. |
| | |
| *'''Poisson random variables.''' Let <math>X\sim \mathrm{Pois}(\nu)</math> be a Poisson random variable with parameter <math>\nu</math>, that is, <math>\Pr[X=k]=\mathrm{e}^{-\nu}\nu^k/k!</math> for all <math>k=0,1,2,\ldots</math>. What are the <math>\Psi_X(\lambda)</math> and <math>\Psi_X^*(t)</math>? And give a tail inequality to upper bound the probability <math>\Pr[X\ge t]</math>.
| |
| | |
| *'''Bernoulli random variables.''' Let <math>X\in\{0,1\}</math> be a single Bernoulli trial with probability of success <math>p</math>, that is, <math>\Pr[X=1]=1-\Pr[X=0]=p</math>. Show that for any <math>t\in(p,1)</math>, we have <math>\Psi_X^*(t)=D(Y \| X)</math> where <math>Y\in\{0,1\}</math> is a Bernoulli random variable with parameter <math>t</math> and <math>D(Y \| X)=(1-t)\ln\frac{1-t}{1-p}+t\ln\frac{t}{p}</math> is the [https://en.wikipedia.org/wiki/Kullback–Leibler_divergence '''Kullback-Leibler divergence'''] between <math>Y</math> and <math>X</math>.
| |
| | |
| *'''Sum of independent random variables.''' Let <math>X=\sum_{i=1}^nX_i</math> be the sum of <math>n</math> independently and identically distributed random variables <math>X_1,X_2,\ldots, X_n</math>. Show that <math>\Psi_X(\lambda)=\sum_{i=1}^n\Psi_{X_i}(\lambda)</math> and <math>\Psi_X^*(t)=n\Psi^*_{X_i}(\frac{t}{n})</math>. Also for binomial random variable <math>X\sim \mathrm{Bin}(n,p)</math>, give an upper bound to the tail inequality <math>\Pr[X\ge t]</math> in terms of KL-divergence.
| |
| | |
| :Give an upper bound to <math>\Pr[X\ge t]</math> when every <math>X_i</math> follows the geometric distribution with a probability <math>p</math> of success.
| |
|
| |
|
| | (Hint: Learn from the proof of Erdos-Rado's sunflower lemma.) |
|
| |
|
| == Problem 2 == | | == Problem 2 == |
| An <math>n</math>-dimensional hypercube <math>Q_n</math> is a graph with <math>2^n</math> vertices, where each vertex is represented by an <math>n</math>-bit vector, and there is an edge between two vertices if and only if their bit-vectors differ in exactly one bit.
| | (Frankl 1986) |
| | |
| Given an <math>n</math>-dimensional hypercube with some non-empty subset of vertices <math>S</math>, which is called marked black. Let <math>f(u)</math> denote the shortest distance from vertex <math>u</math> to any black vertex. Formally,
| |
| | |
| <math>f(u) = \min_{v \in S}\mathrm{dist}_{Q_n}(u,v),</math>
| |
| | |
| where <math>\mathrm{dist}_{Q_n}(u,v)</math> denotes the length of the shortest path between <math>u</math> and <math>v</math> in graph <math>Q_n</math> .
| |
| | |
| Prove that if we choose <math>u</math> from all <math>2^n</math> vertices uniformly at random, then, with high probability, <math>f(u)</math> can not deviate from its expectation too much:
| |
| | |
| <math>\mathrm{Pr}[|f(u) - \mathbb{E}[f(u)]| \geq t\sqrt{n \log n}] \leq n^{-c}.</math>
| |
| | |
| Give the relation between <math>c</math> and <math>t</math>.
| |
| | |
| == Problem 3 ==
| |
| Let <math>Y_1,Y_2,Y_3,\ldots,Y_n</math> be a set of <math>n</math> random variables where each <math>Y_i \in \{0,1\}</math>. All variables <math>Y_i</math> follow some joint distribution over <math>\{0,1\}^n</math> and they may NOT be mutually independent. Assume the following property holds for <math>(Y_i)_{1\leq i \leq n}</math>. For any <math>1\leq i \leq n</math> and it holds that
| |
| | |
| <math>\forall c_1\in \{0,1\},c_2\in \{0,1\},\ldots,c_{i-1}\in \{0,1\} , \quad \Pr[Y_i = 1 \mid \forall 1\leq j<i, Y_j = c_j ] \leq p.</math>
| |
| | |
| Let <math>X_1,X_2,X_3,\ldots,X_n</math> be a set of <math>n</math> mutually independent random variables where each <math>X_i \in \{0,1\}</math>. Assume
| |
| | |
| <math>\forall 1\leq i \leq n:\quad \Pr[X_i = 1] = p.</math>
| |
| | |
| Prove that for any <math>a \geq 0</math>, it holds that
| |
| | |
| <math>\Pr\left[\sum_{i= 1}^n Y_i \geq a\right] \leq \Pr\left[\sum_{i= 1}^n X_i \geq a\right].</math>
| |
| | |
| Prove that for any <math>t \geq 0</math>, it holds that
| |
| | |
| <math>\Pr\left[\sum_{i= 1}^n Y_i \geq np + t\right] \leq \exp\left( -\frac{2t^2}{n}\right).</math>
| |
| | |
| | |
| <strong>Hint</strong>: Although random variables <math>Y_1,Y_2,Y_3,\ldots,Y_n</math> may not be mutually independent, we can still bound the tail probability for <math>\sum_{i=1}^nY_i</math>. This tool is called the stochastic dominance.
| |
| | |
| To prove the first inequality, you only need to construct a coupling <math>\mathcal{C}</math> between <math>(X_i)_{1\leq i \leq n}</math> and <math> (Y_i)_{ 1\leq i\leq n }</math> such that
| |
| | |
| <math> \Pr_{\mathcal{C}}[\,\forall 1\leq i \leq n, Y_i \leq X_i\,] = 1.</math>
| |
| | |
| This implies the random sequence <math>(Y_i)_{1\leq i \leq n}</math> is stochastically dominated by the random sequence <math>(X_i)_{1\leq i \leq n}</math>.
| |
| | |
| == Problem 4 ==
| |
| Let <math>U</math> be a universal set.
| |
| We use <math>2^U</math> to denote the collection of all subsets of <math>U</math>.
| |
| Let <math>\mathcal{F}</math> be a family of hash functions, in which each hash function <math>h:2^U \rightarrow \{0,1\}^m</math> maps subsets of <math>U</math> to 0-1 vectors of length <math>m</math>.
| |
| A locality sensitive hashing scheme is a distribution on a family <math>\mathcal{F}</math> of hash functions operating on <math>2^U</math>, such that for two subsets <math>A,B \in 2^U</math>,
| |
| | |
| <math>(1) \qquad \Pr_{h\in\mathcal{F}}[h(A)=h(B)]=sim(A,B).</math>
| |
| | |
| Here <math>sim:2^U \times 2^U \rightarrow [0,1] </math> is called the similarity function. Given a hash function family <math> \mathcal{F} </math> that satisfies Equation (1), we will say that <math>\mathcal{F}</math> is a locality sensitive hash function family corresponding to similarity function <math>sim(\cdot,\cdot)</math>.
| |
| | |
| *For any similarity function <math> sim(A,B)</math> that admits a locality sensitive hash function family as defined in Equation (1), prove that the distance function <math> d(A,B) \triangleq 1-sim(A,B)</math> satisfies triangle inequality, formally,
| |
| | |
| <math> \forall A,B,C \in 2^U :\quad d(A,B) + d(B,C) \geq d(A,C).</math>
| |
| | |
| *Show that there is no locality sensitive hash function family corresponding to Dice's and the Overlap coefficient. Dice's coefficient is defined as:
| |
| | |
| <math>sim_{Dice}(A,B)=\frac{2|A\cap B|}{|A| + |B|}.</math>
| |
| | |
| Overlap coefficient is defined as:
| |
|
| |
|
| <math>sim_{Ovl}(A,B) = \frac{|A\cap B|}{\min(|A|, |B|)}.</math> | | 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>. |
|
| |
|
| <font color = "blue">Hint: use the triangle inequality result. </font> | | ==Problem 3 == |
| | 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>. |
|
| |
|
| * Construct a collection of hash function <math>\mathcal{B}</math> where <math>f : \{0,1\}^m \rightarrow \{0,1\}</math> for each <math>f \in \mathcal{B}</math>, together with a probability distribution on <math>\mathcal{B}</math> such that
| | 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. |
|
| |
| <math>\forall x, y \in \{0,1\}^m:\quad | |
| \Pr_{f \in \mathcal{B}}[f(x) = f(y)] = \begin{cases}
| |
| 1 &\text{ if } x= y;\\
| |
| \frac{1}{2} &\text{ if } x \neq y.
| |
| \end{cases}
| |
| </math> | |
|
| |
|
| Then use the hash function family <math>\mathcal{B}</math> to prove the following result.
| | ==Problem 4== |
| Given a locality sensitive hash function family <math>\mathcal{F}</math> (<math>h:2^U \rightarrow \{0,1\}^m</math> for each <math>h \in \mathcal{F}</math>) corresponding to a similarity function <math>sim(A,B)</math>, we can obtain a locality sensitive hash function <math>\mathcal{F}'</math> (<math>h':2^U \rightarrow \{0,1\}</math> for each <math>h' \in \mathcal{F}'</math>) corresponding to the similarity function <math>\frac{1+sim(A,B)}{2}</math>.
| | 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. |
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.