In this problem we apply concentration inequalities to sums of independent but not iden- tically distributed random variables. If the university has n students, let Xj denote the indicator that student j is on CalCentral. We will (unrealistically) assume the Xj are in- dependent for j = 1, . . . , n, and we would like to get high-probability bounds on the total number of students on CalCentral S = X1 + X2 + + Xn, since if too many students are on the site at once it will crash. Assume we know from historical data that P(Xj = 1) = pj .

2 Concentration of Counts In this problem we apply concentration inequalities to sums of independent but not iden- tically distributed random variables. If the university has n students, let X 3- denote the indicator that student 3' is on CalCentral. We will (unrealistically) assume the X J- are in- dependent for j = 1, . . . , n, and we would like to get high-probability bounds on the total number of students on CalCentral S = X1 + X; + - - + Xm since if too many students are on the site at once it will crash. Assume we know from historical data that P(X_1- = 1) = p5. (a) (2 points) Write p: = ]E[S] and 02 = Va'r(S) in terms ofp1,p2,. . . ,1)\". Data 102 Assignment 4 Due: 11:59pm PT Friday, November 6, 2020 (b) (2 points) Find Markov's bound 0n 1P(S 2 Kg) for K > 1. (c) (3 points) Find Chebyshev's bound on 1P(S 2 Kn) in terms of pi, K and or. (d) (2 points) If all the pj's are equal to p, what is the value of the bound in (c)? How does the dependence on it compare to the bound you got in part (b)? (e) (1 point) Show that the moment generating function of Xi is given by MXj(t) = 1 + pj(e' 1) for all t. (Recall the denition: MXJ. (t) = ]E[e'X3']) (f) (2 points) Show that M3(t) 3 exp (Mei 1)) for all t. Hint: use the fact that S is the sum of independent random variables, and that am 2 1 + a: for all a: 2 0. (g) (3 points) Use Chernoif's method and the bound in (f) to show that Ms; K\") g exp(n(KlogK+lK)) If Pi = p for all 3', how does this bound depend on n? Hint: You may use the fact that KlogK+1K20for allK> 0