imported>TCSseminar |
imported>TCSseminar |
| Line 2: |
Line 2: |
|
| |
|
| == Problem 1 == | | == Problem 1 == |
| Fix a universe <math>U</math> and two subset <math>A,B \subseteq U</math>, both with size <math>n</math>. we create both Bloom filters <math>F_A</math>(<math>F_B</math>) for <math>A</math> (<math>B</math>), using the same number of bits <math> m</math> and the same <math>k</math> hash functions.
| |
| *Let <math>F_C = F_A \land F_B</math> be the Bloom filter formed by computing the bitwise AND of <math>F_A</math> and <math>F_B</math>. Argue that <math>F_C</math> may not always be the same as the Bloom filter that are created for <math>A\cap B </math>.
| |
| *Bloom filters can be used to estimate set differences. Express the expected number of bits where <math>F_A</math> and <math>F_B</math> differ as a function of <math>m, n, k</math> and <math>|A\cap B|</math>.
| |
|
| |
|
| == Problem 2 == | | == Problem 2 == |
| In Balls-and-Bins model, we throw <math>m</math> balls independently and uniformly at random into <math>n</math> bins. We know that the maximum load is <math>\Theta\left(\frac{\log n}{\log\log n}\right)</math> with high probability when <math>m=\Theta(n)</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). |
| The two-choice paradigm is another way to throw <math>m</math> balls into <math>n</math> bins: each ball is thrown into the least loaded of two bins chosen independently and uniformly at random(it could be the case that the two chosen bins are exactly the same, and then the ball will be thrown into that bin), and breaks the tie arbitrarily. When <math>m=\Theta(n)</math>, the maximum load of two-choice paradigm is known to be <math>\Theta(\log\log n)</math> with high probability, which is exponentially less than the maxim load when there is only one random choice. This phenomenon is called '''''the power of two choices'''''.
| | 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. |
|
| |
|
| Here are the questions:
| | 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. |
| *Consider the following paradigm: we throw <math>n</math> balls into <math>n</math> bins. The first <math>\frac{n}{2}</math> balls are thrown into bins independently and uniformly at random. The remaining <math>\frac{n}{2}</math> balls are thrown into bins using the two-choice paradigm. What is the maximum load with high probability? You need to give an asymptotically tight bound (in the form of <math>\Theta(\cdot)</math>).
| | What's the smallest value of <math>k</math> you can achieve? |
| | |
| *Replace the above paradigm to the following: the first <math>\frac{n}{2}</math> balls are thrown into bins using the two-choice paradigm while the remaining <math>\frac{n}{2}</math> balls are thrown into bins independently and uniformly at random. What is the maximum load with high probability in this case? You need to give an asymptotically tight bound.
| |
| | |
| *Replace the above paradigm to the following: assume all <math>n</math> balls are thrown in a sequence. For every <math>1\le i\le n</math>, if <math>i</math> is odd, we throw <math>i</math>-th ball into bins independently and uniformly at random, otherwise, we throw it into bins using the two-choice paradigm. What is the maximum load with high probability in this case? You need to give an asymptotically tight bound.
| |
|
| |
|
| == Problem 3 == | | == Problem 3 == |
| Suppose we want to estimate the value of <math>Z</math>. Let <math>\mathcal{A}</math> be an algorithm that outputs <math>\widehat{Z}</math> satisfying | | Suppose we have graphs <math>G=(V,E)</math> and <math>H=(V,F)</math> on the same vertex set. |
| <math>\Pr[ (1-\epsilon)Z \leq \widehat{Z} \leq (1+\epsilon )Z] \geq \frac{3}{4} .</math> | | 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> |
| We run <math>\mathcal{A}</math> independently for <math>s</math> times, and obtain the outputs <math>\widehat{Z}_1,\widehat{Z}_2,\ldots,\widehat{Z}_s</math>.
| |
|
| |
|
| Let <math>X</math> be the '''median''' (中位数) of <math>\widehat{Z}_1,\widehat{Z}_2,\ldots,\widehat{Z}_s</math>. Find the number <math>s</math> such that <math>\Pr[ (1-\epsilon)Z \leq X \leq (1+\epsilon )Z] \geq 1 - \delta .</math>
| | * Show that the following SDP is an upperbound on this. |
| | | :::<math> |
| Express <math>s</math> as a function of <math>\delta</math>. Make <math>s</math> as small as possible.
| | \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) \\ |
| | |
| '''Remark''': in this problem, we boost the probability of success from <math>\frac{3}{4}</math> to <math>1-\delta</math>. This method is called the median trick.
| |
| | |
| '''Hint''': Chernoff bound.
| |
| | |
| == Problem 4 ==
| |
| Let <math>X</math> be a random variable with expectation <math>0</math> such that moment generating function <math>\mathbf{E}[\exp(t|X|)]</math> is finite for some <math> t > 0 </math>. We can use the following two kinds of tail inequalities for <math> X </math>.
| |
| | |
| '''''Chernoff Bound'''''
| |
| :<math>
| |
| \begin{align}
| |
| \mathbf{Pr}[|X| \geq \delta] \leq \min_{t \geq 0} \frac{\mathbf{E}[e^{t|X|}]}{e^{t\delta}}
| |
| \end{align} | |
| </math>
| |
| | |
| '''''<math>k</math>th-Moment Bound'''''
| |
| :<math>
| |
| \begin{align} | | \begin{align} |
| \mathbf{Pr}[|X| \geq \delta] \leq \frac{\mathbf{E}[|X|^k]}{\delta^k} | | \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} | | \end{align} |
| </math> | | </math> |
|
| |
| * Show that for each <math>\delta</math>, there exists a choice of <math>k</math> such that the <math>k</math>th-moment bound is stronger than the Chernoff bound.
| |
|
| |
| '''''Hint''''': Consider the Taylor expansion of the moment generating function and apply the probabilistic method.
| |
|
| |
| * Why would we still prefer the Chernoff bound to the (seemingly) stronger <math>k</math>-th moment bound?
| |
|
| |
| == Problem 5 ==
| |
|
| |
| In this problem, we will explore the idea of negative association, show that the classical Chernoff bounds also hold for sum of negatively associated random variables, and see negative association in action by considering occupancy numbers in the balls and bins model.
| |
| Let <math>\boldsymbol{X}=(X_1,\cdots,X_n)</math> be a vector of random variables. We say random variables <math>\boldsymbol{X}</math> are ''negatively associated'' if for all disjoint subsets <math>I,J\subseteq[n]</math>,
| |
|
| |
| :<math>\mathbb{E}[f(X_i,i\in I)g(X_j,j\in J)]\leq \mathbb{E}[f(X_i,i\in I)]\mathbb{E}[g(X_j,j\in J)]</math>
| |
|
| |
| for all non-decreasing function <math>f:\mathbb{R}^{|I|}\rightarrow\mathbb{R}</math> and <math>g:\mathbb{R}^{|J|}\rightarrow\mathbb{R}</math>.
| |
|
| |
| Intuitively, if a set of random variables is negatively related, then if any monotone increasing function <math>f</math> of one subset of variables increases then any other monotone increasing function <math>g</math> of a disjoint set of variables must decrease.
| |
|
| |
| '''(a)''' Let <math>X_1,\cdots,X_n</math> be a set of negatively associated random variables, show that for any non-negative non-decreasing function <math>f_i</math> where <math>i\in[n]</math>,
| |
|
| |
| :<math>\mathbb{E}\left[\prod_{i\in[n]}f_i(X_i)\right]\leq\prod_{i\in[n]}\mathbb{E}[f_i(X_i)]</math>
| |
|
| |
| '''(b)''' Show that the classical Chernoff bounds can be applied as is to <math>X=\sum_{i\in[n]}X_i</math> if the random variables <math>X_1,\cdots,X_n</math> are negatively associated. (Consider both the upper tail and the lower tail.)
| |
|
| |
| To establish the negative association condition, the following two properties are usually very helpful:
| |
|
| |
| *(Closure under products).If <math>\boldsymbol{X}=(X_1,\cdots,X_n)</math> is a set of negatively associated random variables, and <math>\boldsymbol{Y}=(Y_1,\cdots,Y_m)</math> is also a set of negatively associated random variables, but <math>\boldsymbol{X}</math> and <math>\boldsymbol{Y}</math> are mutually independent, then the augmented vector <math>(\boldsymbol{X},\boldsymbol{Y})=(X_1,\cdots,X_n,Y_1,\cdots,Y_m)</math> is a set of negatively associated random variables.
| |
|
| |
| *(Disjoint monotone aggregation). Let <math>\boldsymbol{X}=(X_1,\cdots,X_n)</math> be a set of negatively associated random variables. Let <math>I_1,\cdots,I_k\subseteq[n]</math> be disjoint index sets for some positive integer <math>k</math>. For <math>j\in[k]</math>, let <math>f_j:\mathbb{R}^{|I_j|}\rightarrow\mathbb{R}</math> be functions that are all non–decreasing or all non–increasing, and define <math>Y_j=f_j(X_i,i\in I_j)</math>. Then, <math>\boldsymbol{Y}=(Y_1,\cdots,Y_k)</math> is also a set of negatively associated random variables. (That is, non–decreasing or non–increasing functions of disjoint subsets of negatively associated variables are also negatively associated.)
| |
|
| |
| We now consider the paradigmatic example of negative dependence: ''occupancy numbers'' in the balls and bins model. Again, <math>m</math> balls are thrown independently into <math>n</math> bins. However, this time, the balls and the bins are not necessarily identical: ball <math>k</math> has probability <math>p_{i,k}</math> of landing in bin <math>i</math>, for <math>k\in[m]</math> and <math>i\in[n]</math>, with <math>\sum_{i\in[n]}p_{i,k}=1</math> for each <math>k\in[m]</math>. Define indicator random variable <math>B_{i,k}</math> taking value one if and only if ball <math>k</math> lands in bin <math>i</math>. The occupancy numbers are <math>B_i=\sum_{k\in[m]}B_{i,k}</math>. That is, <math>B_i</math> denote the number of balls that land in bin <math>i</math>.
| |
|
| |
| '''(c)''' Intuitively, <math>B_1,\cdots,B_n</math> are negatively associated: if we know one bin has more balls, then clearly other bins are more likely to have less balls. Now, show that the occupancy numbers <math>B_1,\cdots,B_n</math> are negatively associated, formally.
| |