Solutions to Problem Set 3 - University of California ...

1 UC Berkeley, CS 174: Combinatorics and Discrete Probability (Fall 2010) Solutions to Problem Set 31.(MU )Suppose that we roll a standard fair die 100 times. LetXbe the sum of the numbersthat appear over the 100 rolls. Use Chebyshev s inequality to boundP[|X 350| 50].LetXibe the number on the face of the die for rolli. LetXbe the sum of the dice rolls. ThereforeX= 100i=1Xi. By linearity of expectation, we writeE[X] = 100i=1E[Xi]. We can computeE[Xi] =6 j=1jP[Xi=j] =6 j=1j(1/6) = (1/6)6(7)2= 7/2,where we use the fact that nj=1j=n(n+1)2. Then we haveE[X] = 100(7/2) = use Chebyshev s inequality, the only remaining value we need to compute is the variance ofX.

2 By the independence of the dice rolls we haveVar(X) = Var( iXi)=100 i=1 Var(Xi)To compute the variance of a single dice roll , we use Var(Xi) =E[X2i] +E[X]2E[X2i] =6 j=1j2P[Xi=j]=6 j=1j2(1/6)=16 6(7)(13)6= 91/6where we use the fact that nj=1j2=n(n+1)(2n+1)6. Now we can finish computing the variance ofXiasVar(Xi) =E[X2i] E[X]2= 91/6 (7/2)2= 35 the variance ofXis Var(X) = 100(231/4). Finally, we can by Chebyshev s inequality wehaveP[|X 350| 50] 100(35/12)502= 7 (MU )Given any two random variablesXandY, by the linearity of expectations we haveE[X Y] =E[X] E[Y]. Prove that, whenXandYare independent, Var[X Y] = Var[X] +Var[Y].

3 1 From the definition of variance, we writeVar[X Y] =E[(X Y)2] E[X Y]2=E[X2 2XY+Y2] (E[X] E[Y])2=E[X2] 2E[XY] +E[Y2] (E[X]2 2E[X]E[Y] +E[Y]2)=E[X2] E[X]2+E[Y2] E[Y]2,since by independenceE[XY] =E[X]E[Y]. Finally, we see thatVar[X Y] = Var[X] + Var[Y].3.(MU )For a coin that comes up heads independently with probabilitypon each flip, whatis the variance in the number of flips until thekth head appears?The number of coin flips until a head is a geometric random variable,Xi, with parameterp. LetXbe the number of coin flips untilkheads. ThenX= ki= [X] = Var[k i=1Xi]=k i=1 Var[Xi]=k i=1(1 p)/p2=k(1 p)/p24.

4 (MU )LetYbe a non-negative integer-valued random variable with positive [Y]2E[Y2] P[Y6= 0] E[Y].First, we consider the upper bound. By Markov s inequality, we haveP[Y6= 0] =P[Y 1] E[Y].Now, for the lower bound. Notice that one might think of usingP[Y6= 0] = 1 P[Y= 0],and upper boundingP[Y= 0] by Chebyshev s inequality. However, this will not work, becauseJensen s inequality, for convertingE[X]2toE[X2], cannot provide a bound in the proper direction.(Note that the first solution provided to this Problem was incorrect in attempting to use proceedvia Chebyshev s and Jensen s inequalities.)A much more useful approach is to use conditional expectation to obtain an inequality thatcontainsP[Y6= 0] as one of the coefficients.

5 Recall that Jensen s inequality tells us thatE[X]2 E[X2]2 LetXbe a random variable derived fromYwhereXhas sample space ={ \{z |Y(z) =0}}where is the sample space forY, and where the random variableXsatisfiesX(z) =Y(z) z . So, we have definedXsuch thatX= (Y|Y6= 0). Then, the above Jensen sinequality tell us thatE[Y|Y6= 0]2 E[Y2|Y6= 0].Now we compute each side of the above inequality. For the left-hand, side we haveE[Y|Y6= 0] =( i=0iP[Y=i|Y6= 0])2=( i=0iP[Y=i, Y6= 0]P[Y6= 0])2=( i=1iP[Y=i]P[Y6= 0])2=E[Y]2P[Y6= 0] the right-hand side, we haveE[Y2|Y6= 0] = i=0i2P[Y=i|Y6= 0]= i=1i2P[Y=i]P[Y6= 0]=E[Y2]P[Y6= 0].

6 Putting everything together, we haveE[Y]2P[Y6= 0]2 E[Y2]P[Y6= 0]E[Y]2E[Y2] P[Y6= 0],which concludes the (MU )(a) Chebyshev s inequality uses the variance of a random variable to bound its deviation fromits expectation. We can also use higher moments. Suppose that we have a random variableXand an even integerkfor whichE[(X E[X])k] is finite. Show thatP[|X E[X]|> tk E[(X E[X])k]] (X E[X])k. By Markov s inequality we haveP[Y tkE[Y]] E[Y]tkE[Y]=1tk. Now,we haveP[Y tkE[Y]]=P[k Y tk E[Y]]=P[|X E[X]| tk E[(X E[X])k]]where the first step is true since we take thekth root of both sides of the inequality, and thesecond step is true since thekth root of a number , wherekis even, is the absolute this together with the Markov s inequality, we haveP[|X E[X]| tk E[(X E[X])k]] 1tk.

7 (b) Why is it difficult to derive a similar inequality whenkis odd? SinceXis any randomvariable, the value (X E[X])kmay be negative for odd valuesk. Therefore Markov sinequality would not (MU )A fixed point of a permutation : [1, n] [1, n] is a value for which (x) =x. Findthe variance in the number of fixed points of a permutation chosen uniformly at random from an indicator random variable for the event that (i) =i, makingia fixed point, 1 wheniis a fixed point, andXi= 0 otherwise. We can easily compute theE[X]. LetX= ni=1be the number of fixed , we notice that Var[X] =E[X2] E[X]2. Next, we compute the expectation of the numberof fixed points.

8 Since theE[Xi] =P[Xi] = 1/n, we haveE[X] =E[n i=1Xi]=n i=1E[Xi] =n i=1(1/n) = , we compute the first term in the variance,E[X2] =E (n i=1Xi)2 =(n i=1E[X2i])+ n i=1 j6=iE[XiXj] =(n i=1E[Xi])+ n i=1 j6=iE[XiXj] = 1 + n i=1 j6=iP[Xi= 1]E[XiXj|Xi= 1] = 1 + n i=1 j6=i1n1(n 1) = 1 + 1= 24 The third line follows since for indicator variablesX2i=Xi. The forth line is obtained by usingconditional expectation, conditioning on the eventXi= 1. The fifth line comes from knowingthatP[Xi= 1] = 1/n, and conditioning onXi= 1, there aren 1 choices for mapping elementj, yielding 1/(n 1) as the conditional probability ofjbeing a fixed everything together we haveVar[X] = 2 1 = (Balls and Bins)This Problem involves aballs and bins experimentin whichmballs are tossedindependently intonbins with each ball equally likely to land in any bin.

9 (a) Using a Chernoff bound, estimate the probability that if 3nlnnballs are tossed intonbins,the maximum number of balls in any bin is less than or equal to 2 Problem was not graded due to issues with the Problem statement.(b) Write a simple program that simulates the balls and bins experiment for given values ofmandnup to one million. You will need a random number generator; the standard C libraryfunction drand48() is recommended. Consult the man page for most straight forward way to do the simulation is to use an array of dimension onemillion to record the number of balls that have landed in each bin.

10 It is wasteful of space touse one million integers to store the bin loads. Since you are very unlikely ever to see a loadgreater than 15, you can in fact use a single byte ( , a character) to store each bin is an alternate way to do the simulation using an integer array which records, inpositioni, the number of bins that have received exactlyiballs. This eliminates the needfor an array of size one million. If you see the trick, explain how to do the simulation thisway. Using one of the above two methods, perform at least 20 (preferably 100) simulationswithm=n= 106, and make a table of the distribution of the maximum , consider the following alternative scheme: balls are again thrown sequentially, butinstead of simply choosing a single bin at random, each ball now choosestwobins at random,inspects their current loads, and goes to the less full of the two (breaking ties arbitrarily).