| Section |
Number |
Point |
Comments |
| 6.6 | 7 |
4 |
|
| Supp | 13 b,d,f | 6 | |
| A |
1,2 - 2 3 - 1 |
A fair die is rolled twice. Let
X denote the sum of the outcomes and Y the first outcome minus the
second. 1) Are X and Y independent? 2) What is Cov(X,Y)? While you can compute this directly by enumerating all outcomes, you can alternatively write X=X_1+X_2 and Y=X_1-X_2. 3) What can you deduce from this? |
|
| B |
6 |
The coupon collector problem. There are N different types of coupons and each time our collector obtains a coupon it is equally likely to be any one of those (independently of anything else). What is the expected number of coupons our collector would own when he finally completes his collection (has at least one of each). Hint: look at our solution to the average waiting time for servicing all the processes in the contention resolution problem. |
|
| C |
4 |
What is the "efficiency" of the contention resolution algorithm: what's the average number of rounds (out of N rounds) that the server is idle? Give upper and lower bounds to this number. | |
| D |
6 |
Let X be a geometric random
variable. Compute E(X) by conditioning on the result of the first
trial: you should get an equation for E(X) which is easily solved. |
|
| E |
4 |
Do the same for E(X^2) and
conclude that V(X)=(1-p)/(p^2) |
|
| F |
6 |
Let S_n be the number of
successes in n Bernoulli trials. We know that for any a>0, Pr( | (S_n-np) / n | >= a ) --> 0 as n -> infinity. What can you (provably) say about the limit of Pr( | (S_n-np) / n^(2/3) | >= a ) (as n -> infinity)? Perspective: remember that a binomial is concentrated in an interval of order C*sqrt(n) about its mean. |