imported>Zhangchihao |
imported>Zhangchihao |
| Line 1: |
Line 1: |
| == Problem 1 == | | == Problem 1 == |
| We play the following game:
| |
|
| |
|
| Start with <math>n</math> people, each with 2 hands. None of these hands hold each other. At each round, uniformly pick 2 free hands and let these two hands hold together. Repeat this until no free hands left.
| | A set of vertices <math>D\subseteq V</math> of graph <math>G(V,E)</math> is a <i>dominating set</i> if for every <math>v\in V</math>, either <math>v\in D</math> or <math>u\in D</math> where <math>u</math> is a neighbour of <math>v</math>. The problem of computing minimum dominating set is NP-hard. Prove that for every <math>d</math>-regular graph with <math>n</math> vertices, there exists a dominating set with size at most <math>\frac{n(1+\ln(d+1))}{d+1}</math>. |
| | |
| * What is the expected number of cycles made by people holding hands with each other (one person with left hand holding right hand is also counted as a cycle) at the end of the game?
| |
|
| |
|
| == Problem 2 == | | == Problem 2 == |
|
| |
| In <i>Balls-and-Bins</i> model, we throw <math>n</math> balls independently and uniformly at random into <math>n</math> bins, then the maximum load is <math>\Theta(\frac{\ln n}{\ln\ln n})</math> with high probability.
| |
|
| |
| The <i>two-choice paradigm</i> is another way to throw <math>n</math> balls into <math>n</math> bins: each ball is thrown into the least loaded of 2 bins chosen independently and uniformly at random and breaks the tie arbitrarily. The maximum load of two-choice paradigm is <math>\Theta(\ln\ln n)</math> with high probability, which is exponentially less than the previous one. This phenomenon is called the <i>power of two choices</i>.
| |
|
| |
| Now consider the following three paradigms:
| |
|
| |
| # The first <math>n/2</math> balls are thrown into bins independently and uniformly at random. The remaining <math>n/2</math> balls are thrown into bins using two-choice paradigm.
| |
| # The first <math>n/2</math> balls are thrown into bins using two-choice paradigm. The remaining <math>n/2</math> balls are thrown into bins independently and uniformly at random.
| |
| # Assume all <math>n</math> balls are 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 two-choice paradigm.
| |
|
| |
| What is the maximum load with high probability in each of three paradigms. You need to give an asymptotically tight bound (i.e. <math>\Theta(\cdot)</math>).
| |
|
| |
|
| == Problem 3 == | | == Problem 3 == |
|
| |
| Consider a sequence of <math>n</math> flips of an unbiased coin. Let <math>H_i</math> denote the absolute value of the excess of the number of HEADS over the number of TAILS seen in the first <math>i</math> flips. Define <math>H=\max_i H_i</math>. Show that <math>\mathbf{E}[H_i]=\Theta(\sqrt{i})</math>, and that <math>\mathbf{E}[H]=\Theta(\sqrt{n})</math>.
| |
|
| |
|
| == Problem 4 == | | == Problem 4 == |
|
| |
|
| Let <math>X</math> be a random variable with expectation <math>\mu_X</math> and standard deviation <math>\sigma_X</math>.
| | == Problem 5 == |
| | |
| # Show that for any <math>t\in\mathbb{R}^+</math>,
| |
| ::<math>
| |
| \Pr[X-\mu_X\ge t\sigma_X]\le\frac{1}{1+t^2},
| |
| </math>
| |
| This version of the Chebyshev inequality is sometimes referred to as the <b>Chebyshev-Cantelli bound</b>.
| |
| | |
| # Prove that
| |
| ::<math>
| |
| \Pr[|X-\mu_X|\ge t\sigma_X]\le\frac{2}{1+t^2}.
| |
| </math>
| |
| Under what circumstances does this give a better bound than the Chebyshev inequality?
| |