概率论 (Summer 2013)/Problem Set 2: Difference between revisions
imported>Zhangchihao (Created page with "== 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 hand…") |
imported>Zhangchihao No edit summary |
||
| Line 7: | Line 7: | ||
== 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 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>). | |||
Revision as of 07:41, 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 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]).