View source for 高级算法 (Fall 2017)/Problem Set 1

 每道题目的解答都要有<font color="red" >完整的解题过程</font>。中英文不限。

== Problem 1==
Recall that in class we show by the probabilistic method how to deduce a <math>\frac{n(n-1)}{2}</math> upper bound on the number of distinct min-cuts in any multigraph <math>G</math> with <math>n</math> vertices from the <math>\frac{2}{n(n-1)}</math> lower bound for success probability of Karger's min-cut algorithm. 

Also recall that the <math>FastCut</math> algorithm taught in class guarantees to return a min-cut with probability at least <math>\Omega(1/\log n)</math>. Does this imply a much tighter <math>O(\log n)</math> upper bound on the number of distinct min-cuts in any multigraph <math>G</math> with <math>n</math> vertices? Prove your improved upper bound if your answer is "yes", and give a satisfactory explanation if your answer is "no".

== Problem 2 ==
Two ''rooted'' trees <math>T_1</math> and <math>T_2</math> are said to be '''isomorphic''' if there exists a bijection <math>\phi</math> that maps vertices of <math>T_1</math> to those of <math>T_2</math> satisfying the following condition: for each ''internal'' vertex <math>v</math> of <math>T_1</math> with children <math>u_1,u_2,\ldots, u_k</math>, the set of children of vertex <math>\phi(v)</math> in <math>T_2</math> is precisely <math>\{\phi(u_1), \phi(u_2),\ldots,\phi(u_k)\}</math>, no ordering among children assumed.

Give an efficient randomized algorithm with bounded one-sided error (false positive), for testing isomorphism between rooted trees with <math>n</math> vertices. Analyze your algorithm.

== Problem 3 ==
Suppose <math>x_1,x_2,\ldots,x_n</math> is an unsorted list of <math>n</math> distinct numbers. We sample (with replacement) <math>t</math> items uniformly at random from the list, and denote them as <math>Y_1,Y_2,\ldots,Y_t</math>. Obviously <math>\{Y_1,Y_2,\ldots,Y_t\}\subseteq \{x_1,x_2,\ldots,x_n\}</math>.

Describe a strategy of choosing an <math>x</math> from the sampled set <math>\{Y_1,Y_2,\ldots,Y_t\}</math> such that <math>\mathrm{rank}(x)</math> is approximately <math>k</math>. Here <math>\mathrm{rank}(x)</math> denotes the rank of <math>x</math> in the original list <math>\{x_1,x_2,\ldots,x_n\}</math>: The rank of the largest number among <math>x_1,x_2,\ldots,x_n</math> is 1; the rank of the second largest number among <math>x_1,x_2,\ldots,x_n</math> is 2, and so on. Choose your <math>t</math> as small as possible (in big-O notation) so that with probability at least <math>1-\delta</math>, your strategy returns an <math>x</math> such that <math>(1-\epsilon)k\le \mathrm{rank}(x)\le (1+\epsilon)k</math>.

== Problem 4 ==
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>. 
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'''''. 

Here are the questions:
*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>).

*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 5==
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>.

*'''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.

==Problem 6==
A '''boolean code''' is a mapping <math>C:\{0,1\}^k\rightarrow\{0,1\}^n</math>. Each <math>x\in\{0,1\}^k</math> is called a '''message''' and <math>y=C(x)</math> is called a '''codeword'''. The '''code rate''' <math>r</math> of a code <math>C</math> is <math>r=\frac{k}{n}</math>. A boolean code <math>C:\{0,1\}^k\rightarrow\{0,1\}^n</math> is a '''linear code''' if it is a linear transformation, i.e. there is a matrix <math>A\in\{0,1\}^{n\times k}</math> such that <math>C(x)=Ax</math> for any <math>x\in\{0,1\}^k</math>, where the additions and multiplications are defined over the finite field of order two, <math>(\{0,1\},+_{\bmod 2},\times_{\bmod 2})</math>.

The '''distance''' between two codeword <math>y_1</math> and <math>y_2</math>, denoted by <math>d(y_1,y_2)</math>, is defined as the Hamming distance between them. Formally, <math>d(y_1,y_2)=\|y_1-y_2\|_1=\sum_{i=1}^n|y_1(i)-y_2(i)|</math>. The distance of a code <math>C</math> is the minimum distance between any two codewords. Formally, <math>d=\min_{x_1,x_2\in \{0,1\}^k\atop x_1\neq x_2}d(C(x_1),C(x_2))</math>.

Usually we want to make both the code rate <math>r</math> and the code distance <math>d</math> as large as possible, because a larger rate means that the amount of actual message per transmitted bit is high, and a larger distance allows for more error correction and detection.

* Use the probabilistic method to prove that there exists a boolean code <math>C:\{0,1\}^k\rightarrow\{0,1\}^n</math> of code rate <math>r</math> and distance <math>\left(\frac{1}{2}-\Theta\left(\sqrt{r}\right)\right)n</math>. Try to optimize the constant in <math>\Theta(\cdot)</math>.
* Prove a similar result for linear boolean codes.

== Bonus problem ==
Let <math>X</math> be a ''centralized'' random variable (<math>\mathbb{E}[X]=0</math>) with finite <math>\mathbb{E}\left[\mathrm{e}^{\lambda |X|}\right]</math> for <math>\lambda>0</math>. We have the following two kinds of tail inequalities.
;Chernoff bound<nowiki>:</nowiki>
:<math>\Pr[|X|\ge t]\le\inf_{\lambda\ge 0}\frac{\mathbb{E}\left[\mathrm{e}^{\lambda |X|}\right]}{\mathrm{e}^{\lambda t}}</math>.
;<math>k</math>-th moment bound<nowiki>:</nowiki>
:<math>\Pr[|X|\ge t]\le \frac{\mathbb{E}\left[|X|^k\right]}{t^k}</math>.
* Use the probabilistic method to show that for any <math>t>0</math>, there exists a choice of <math>k</math> such that the <math>k</math>-th moment bound is ''strictly'' stronger than the Chernoff bound.
* Why would we still prefer the Chernoff bound to the seemingly stronger <math>k</math>-th moment method?