概率论 (Summer 2013)/Problem Set 2: Difference between revisions
imported>Zhangchihao No edit summary |
imported>Etone |
||
Line 32: | Line 32: | ||
\Pr[X-\mu_X\ge t\sigma_X]\le\frac{1}{1+t^2}, | \Pr[X-\mu_X\ge t\sigma_X]\le\frac{1}{1+t^2}, | ||
</math> | </math> | ||
This version of the Chebyshev inequality is sometimes referred to as the <b>Chebyshev-Cantelli bound</b>. | :This version of the Chebyshev inequality is sometimes referred to as the <b>Chebyshev-Cantelli bound</b>. | ||
# Prove that | # Prove that | ||
Line 38: | Line 38: | ||
\Pr[|X-\mu_X|\ge t\sigma_X]\le\frac{2}{1+t^2}. | \Pr[|X-\mu_X|\ge t\sigma_X]\le\frac{2}{1+t^2}. | ||
</math> | </math> | ||
Under what circumstances does this give a better bound than the Chebyshev inequality? | :Under what circumstances does this give a better bound than the Chebyshev inequality? | ||
== Problem 5 (Bonus Problem) == | == Problem 5 (Bonus Problem) == | ||
Consider the following experiment, which proceeds in a sequence of <i>rounds</i>. For the first round, we have <math>n</math> balls, which are thrown independently and uniformly at random into <math>n</math> bins. After round <math>i</math>, for <math>i\ge 1</math>, we discard every ball that fell into a bin by itself in round <math>i</math> (i.e., we discard a ball if and only if there is no other balls that fell into the same bin). The remaining balls are retained for round <math>i+1</math>, in which they are thrown independently and uniformly at random into the <math>n</math> bins. Show that there is a constant <math>c</math> such that with probability <math>1-o(1)</math>, the number of rounds is at most <math>c\ln\ln n</math>. | Consider the following experiment, which proceeds in a sequence of <i>rounds</i>. For the first round, we have <math>n</math> balls, which are thrown independently and uniformly at random into <math>n</math> bins. After round <math>i</math>, for <math>i\ge 1</math>, we discard every ball that fell into a bin by itself in round <math>i</math> (i.e., we discard a ball if and only if there is no other balls that fell into the same bin). The remaining balls are retained for round <math>i+1</math>, in which they are thrown independently and uniformly at random into the <math>n</math> bins. Show that there is a constant <math>c</math> such that with probability <math>1-o(1)</math>, the number of rounds is at most <math>c\ln\ln n</math>. |
Revision as of 11:25, 11 July 2013
Problem 1
We play the following game:
Start with [math]\displaystyle{ 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.
- 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
In Balls-and-Bins model, we throw [math]\displaystyle{ n }[/math] balls independently and uniformly at random into [math]\displaystyle{ n }[/math] bins, then the maximum load is [math]\displaystyle{ \Theta(\frac{\ln n}{\ln\ln n}) }[/math] with high probability.
The two-choice paradigm is another way to throw [math]\displaystyle{ n }[/math] balls into [math]\displaystyle{ 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]\displaystyle{ \Theta(\ln\ln n) }[/math] with high probability, which is exponentially less than the previous one. This phenomenon is called the power of two choices.
Now consider the following three paradigms:
- The first [math]\displaystyle{ n/2 }[/math] balls are thrown into bins independently and uniformly at random. The remaining [math]\displaystyle{ n/2 }[/math] balls are thrown into bins using two-choice paradigm.
- The first [math]\displaystyle{ n/2 }[/math] balls are thrown into bins using two-choice paradigm. The remaining [math]\displaystyle{ n/2 }[/math] balls are thrown into bins independently and uniformly at random.
- Assume all [math]\displaystyle{ n }[/math] balls are in a sequence. For every [math]\displaystyle{ 1\le i\le n }[/math], if [math]\displaystyle{ i }[/math] is odd, we throw [math]\displaystyle{ 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]\displaystyle{ \Theta(\cdot) }[/math]).
Problem 3
Consider a sequence of [math]\displaystyle{ n }[/math] flips of an unbiased coin. Let [math]\displaystyle{ 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]\displaystyle{ i }[/math] flips. Define [math]\displaystyle{ H=\max_i H_i }[/math]. Show that [math]\displaystyle{ \mathbf{E}[H_i]=\Theta(\sqrt{i}) }[/math], and that [math]\displaystyle{ \mathbf{E}[H]=\Theta(\sqrt{n}) }[/math].
Problem 4
Let [math]\displaystyle{ X }[/math] be a random variable with expectation [math]\displaystyle{ \mu_X }[/math] and standard deviation [math]\displaystyle{ \sigma_X }[/math].
- Show that for any [math]\displaystyle{ t\in\mathbb{R}^+ }[/math],
- [math]\displaystyle{ \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 Chebyshev-Cantelli bound.
- Prove that
- [math]\displaystyle{ \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?
Problem 5 (Bonus Problem)
Consider the following experiment, which proceeds in a sequence of rounds. For the first round, we have [math]\displaystyle{ n }[/math] balls, which are thrown independently and uniformly at random into [math]\displaystyle{ n }[/math] bins. After round [math]\displaystyle{ i }[/math], for [math]\displaystyle{ i\ge 1 }[/math], we discard every ball that fell into a bin by itself in round [math]\displaystyle{ i }[/math] (i.e., we discard a ball if and only if there is no other balls that fell into the same bin). The remaining balls are retained for round [math]\displaystyle{ i+1 }[/math], in which they are thrown independently and uniformly at random into the [math]\displaystyle{ n }[/math] bins. Show that there is a constant [math]\displaystyle{ c }[/math] such that with probability [math]\displaystyle{ 1-o(1) }[/math], the number of rounds is at most [math]\displaystyle{ c\ln\ln n }[/math].