Solutions to Problem Set 10 (6.042J Mathematics for Computer Science)

Massachusetts Institute of Technology 6.042J/18.062J : Mathematics for Computer Science December 9 revised December 2, 1086 minutes Solutions to Problem Set 10 Problem 1. MIT students sometimes delay laundry for a few days. Assume all random values described below are mutually independent. (a) A busy student must complete 3 problem sets before doing laundry. Each problem set requires 1 day with probability 2/3 and 2 days with probability 1/3. Let B be the number of days a busy student delays laundry. What is E [B]? Example: If the first problem set requires 1 day and the second and third problem sets each require 2 days, then the student delays for B = 5 days. Solution. The expected time to complete a problem set is: 1· 2 1 4 +2· = 3 3 3 Therefore, the expected time to complete all three problem sets is: E [B] = E [pset1] + E [pset2] + E [pset3] 4 4 4 = + + 3 3 3 =4 � (b) A relaxed student rolls a fair, 6­sided die in the morning. If he rolls a 1, then he does his laundry immediately (with zero days of delay). Otherwise, he delays for one day and repeats the experiment the following morning. Let R be the number of days a relaxed student delays laundry. What is E [R]? Example: If the student rolls a 2 the first morning, a 5 the second morning, and a 1 the third morning, then he delays for R = 2 days. 2 Solution. If we regard doing laundry as a failure, then the mean time to failure is 1/(1/6) = 6. However, this counts the day laundry is done, so the number of days delay is 6 − 1 = 5. Alternatively, we could derive the answer as follows: E [R] = ∞ � Pr {R > k} k=0 � �2 � �3 5 5 5 = + + + ... 6 6 6 � � � �2 5 5 5 = · 1+ + + ... 6 6 6 5 1 · 6 1 − 5/6 =5 = � (c) Before doing laundry, an unlucky student must recover from illness for a number of days equal to the product of the numbers rolled on two fair, 6­sided dice. Let U be the expected number of days an unlucky student delays laundry. What is E [U ]? Example: If the rolls are 5 and 3, then the student delays for U = 15 days. Solution. Let D1 and D2 be the two die rolls. Recall that a die roll has expectation 7/2. Thus: E [U ] = E [D1 · D2 ] = E [D1 ] · E [D2 ] 7 7 = · 2 2 49 = 4 � (d) A student is busy with probability 1/2, relaxed with probability 1/3, and unlucky with probability 1/6. Let D be the number of days the student delays laundry. What is E [D]? Solution. E [D] = 1 1 1 E [B] + E [R] + E [U ] 2 3 6 � 3 Problem 2. There are about 250,000,000 people in the United States who might use a phone. Assume that each person is on the phone during each minute mutually indepen­ dently with probability p = 0.01. (To keep the problem simple, we are putting aside the fact that people are on the phone more often at certain times of day and on certain days of the year.) (a) What is the expected number of people on the phone at a given moment? Solution. Let Ii be an indicator for the event that the i­th person is one the phone. The number of people on the phone is then: 250,000,000 � Ii . i=1 The expectation of this sum is 250, 000, 000 · 0.01 = 2, 500, 00 by linearity of expectation. � (b) Suppose that we construct a phone network whose capacity is a mere one percent above the expectation. Upper bound the probability that the network is overloaded in a given minute. (Use the approximation formula given in the notes. You may need to evaluate this expression in a clever way because of the size of numbers involved. For example, you could first evaluate the logarithm of the given expression.) Solution. The network is overloaded if the fraction of people calling is greater than 1.01 · 0.01 = 0.0101. In complementary terms, the network is overloaded if the fraction of people not calling is less than 1 − 0.0101 = 0.9899. Define the following variables: n ::= 250, 000, 000 people in the US p ::= 0.99 prob. not on phone α ::= 0.9899 min. allowable fraction not on phone In these terms, the solution to the problem is Fn,p (αn). We can upper bound this approxi­ mately using the formula from the notes: Fn,p (αn) ≈ 1−α 2nH(α) ·� · pαn (1 − p)(1−α)n . 1 − α/p 2πα(1 − α)n By first evaluating the logarithm of this expression, we find that this is about e−120 . � (c) What is the expected number of minutes (approximately) until the system is over­ loaded for the first time? Solution. Applying the “expected time to failure” formula with probability p = e−120 gives 1/p = e120 . � 4 Problem 3. We are given a set of n distinct positive integers. We then determine the maximum of these numbers by the following procedure: Randomly arrange the numbers in a sequence. Let the “current maximum” initially be the first number in the sequence and the “current element” be the second element of the sequence. If the current element is greater than the current maximum, perform an “update”: that is, change the current maximum to be the current element. Either way, change the current element to be the next element of the sequence. Repeat this process until there is no next element. Prove that the expected number of updates is ∼ ln n. Hint: Let Mi be the indicator variable for the event that the ith element of the sequence is bigger than all the previous elements in the sequence. Solution. Note that the number of times we update the current maximum is precisely M = M1 + . . . + Mn . Since expectation is a linear operator, we can compute E [M ] by finding E(Mi ) for all i and summing them up. Note also that since Mi is an “indicator” variable, we only have to find Pr {Mi = 1}. In a random permutation, this happens with probability 1/i. Why? Because all permutations of the first i numbers in the sequence are equally likely, and the largest among them occurs as the last element of the permutation in 1/i of the cases. Thus � E [M ] = Pr {Mi = 1} i = n � 1/i i=1 = Hn ∼ ln n, where Hn is the nth Harmonic number. � Problem 4. In a certain card game, each card has a point value. • Numbered cards in the range 2 to 9 are worth five points each. • The card numbered 10 and the face cards (jack, queen, king) are worth ten points each. • Aces are worth fifteen points each. (a) Suppose that you thoroughly shuffle a 52­card deck. What is the expected total point value of the three cards on the top of the deck after the shuffle? 5 Solution. Let the random variable, X, be the total point value of the three cards on the top of the deck. Then we can write: X = X1 + X2 + X3 where the random variables X1 , X2 , and X3 are the point values of the first, second, and third cards. By the definition of expectation: � E [Xi ] = r · Pr {Xi = r} r∈Xi (S) = 5· = 8 4 1 + 10 · + 15 · 13 13 13 95 13 Now we can solve the problem by taking the expected value of both sides of our original equation and then using linearity of expectation: E [X] = E [X1 + X2 + X3 ] = E [X1 ] + E [X2 ] + E [X3 ] 95 95 95 = + + 13 13 13 285 = 13 � (b) Suppose that you throw out all the red cards and shuffle the remaining 26­card, all­ black deck. Now what is the expected total point value of the top three cards? (Note that drawing three aces, for example, is now impossible!) Solution. The expected point value is the same as before, since expected point value of a single card is unchanged. Nothing in our solution assumed a 52 card deck. � Problem 5. A true story from World War II: The army needs to identify soldiers with a disease called “klep”. There is a way to test blood to determine whether it came from someone with klep. The straightforward ap­ proach is to test each soldier individually. This requires n tests, where n is the number of soldiers. A better approach is the following: group the soldiers into groups of k. Blend 6 the blood samples of each group and apply the test once to each blended sample. If the group­blend doesn’t have klep, we are done with that group after one test. If the group­ blend fails the test, then someone in the group has klep, and we individually test all the soldiers in the group. Assume each soldier has klep with probability, p, independently of all the other soldiers. (a) What is the expected number of tests as a function of n, p, and k? (Assume for sim­ plicity that n is divisible by k.) Solution. There are n/k groups of size k each. Let Xi be a random variable that denotes the number of tests performed in group i. Xi takes value 1 with probability (1 − p)k and value k + 1 with probability 1 − (1 − p)k . Hence the expected number of tests is ⎡ ⎤ n/k n/k � � n 1 ⎣ ⎦ E Xi = E(Xi ) = ( )((1 − p)k + (k + 1)(1 − (1 − p)k )) = n(1 − (1 − p)k + ). (1) k k i=1 i=1 � (b) How should k be chosen to minimize the expected number of test performed, and what is the resulting expectation? Solution. The k must be chosen so that the derivative w.r.t. k of the answer from part (a) is 0, namely, 1 (1 − p)k ln(1 − p) + 2 = 0. k Assuming that p is much smaller than 1/k, we can approximate (1 − p)k by 1 and ln(1 − p) by −p, giving us � 1 . k≈ p In particular, p ≈ 1/k 2 comes out much smaller than 1/k, so our approximations are √ justified. The resulting expectation is approximately n p. � (c) What fraction of the work does the grouping method expect to save over the straight­ forward approach in a million­strong army where 1% have klep? Solution. Using the approximation from the previous part, the expected fraction of work √ saved is 1− p, so for p = 0.01, we estimate a 90% savings. Using the exact formula (1), we � find that the fraction of work√saved is (1 − p)k − 1/k. So for p = 0.01 and k = 1/p = 10, � the savings is (1 − 0.01)10 − 0.01 = 0.804, that is, more than 80%. 7 Problem 6. The hat­check staff has had a long day, and at the end of the party they decide to return people’s hats at random. Suppose that n people have their hats returned at random. We previously showed that the expected number of people who get their own hat back is 1, irrespective of the total number of people. In this problem we will calculate the variance in the number of people who get their hat back. Let �n Xi = 1 if the ith person gets his or her own hat back and 0 otherwise. Let Sn ::= i=1 Xi , so Sn is the total number of people who get their own hat back. Show that (a) E [Xi2 ] = 1/n. Solution. Xi = 1 with probability 1/n and 0 otherwise. Thus Xi2 = 1 with probability 1/n and 0 otherwise. So E [Xi2 ] = 1/n. � (b) E [Xi Xj ] = 1/n(n − 1) for i �= j. Solution. The probability that Xi and Xj are both 1 is 1/n · 1/(n − 1) = 1/n(n − 1). Thus Xi Xj = 1 with probability 1/n(n − 1), and is zero otherwise. So E [Xi Xj ] = 1/n(n − 1). � (c) E [Sn2 ] = 2. Hint: Use (a) and (b). Solution. � � � �� � � E Sn2 = E Xi2 + E [Xi Xj ] i i = n· j�=i 1 1 + n(n − 1) · n n(n − 1) = 2. � (d) Var [Sn ] = 1. Solution. Var [Sn ] = = = = � � E Sn2 − E2 [Sn ] 2 − (n(1/n))2 2−1 1. � 8 (e) Explain why you cannot use the variance of sums formula to calculate Var [Sn ]. Solution. The indicator random variables, Xi , are not even pairwise independent. This can be seen by comparing the marginal and conditional probability of a particular person, Alice, getting her hat back. The marginal probability, unconditioned on any other events, is 1/n as we’ve computed before. However, if compute this probability conditioned on the event that a second person, Bob, got his hat back, we find that the probability of Alice getting her hat back is 1/(n − 1). � (f) Using Chebyshev’s Inequality, show that Pr {Sn ≥ 11} ≤ .01 for any n ≥ 11. Solution. Pr {Sn ≥ 11} = Pr {Sn − E [Sn ] ≥ 11 − E [Sn ]} = Pr {Sn − E [Sn ] ≥ 10} Var [Sn ] ≤ = .01 102 Note that the Xi ’s are Bernoulli variables but are not independent, so Sn does not have a binomial distribution and the binomial estimates from Lecture Notes do not apply. � Problem 7. Let R1 and R2 be independent random variables, and f1 and f2 be any func­ tions such that domain (fi ) = codomain (Ri ) for i = 1, 2. Prove that f1 (R1 ) and f2 (R2 ) are independent random variables. Solution. The event [fi (Ri ) = a] is the disjoint union of all the events [Ri = r] for r ∈ fi−1 (a), so � Pr {fi (Ri ) = a} = Pr {Ri = r} . r∈fi−1 (a) Also, the event [f1 (R1 ) = a and f2 (R2 ) = b] is the disjoint unon of the events [R1 = 9 r and R2 = t] for (r, t) ∈ f1−1 (a) × f2−1 (b). Hence, Pr {f1 (R1 ) = a and f2 (R2 ) = b} � Pr {R1 = r and R2 = t} = (r,t)∈f1−1 (a)×f2−1 (b) � = Pr {R1 = r} Pr {R2 = t} [because R, R2 independent] (r,t)∈f1−1 (a)×f2−1 (b) = � � t∈f2−1 (b) r∈f1−1 (a) Pr {R1 = r} Pr {R2 = t} ⎞ ⎛ = � Pr {R2 = t} ⎝ t∈f2−1 (b) = � � Pr {R1 = r}⎠ r∈f1−1 (a) Pr {R2 = t} (Pr {f (R) = a}) t∈f2−1 (b) = Pr {f (R) = a} � Pr {R2 = t} t∈f2−1 (b) = Pr {f (R) = a} Pr {f2 (R2 ) = b} � Problem 8. Let A, B, C be events, and let IA , IB , IC be the corresponding indicator vari­ ables. Prove that A, B, C are mutually independent iff the random variables IA , IB , IC are mutually independent. Solution. (−→): Pr {IA = 1 ∧ IB = 0 ∧ IC = 1} = = = = = = = � � Pr A ∩ B ∩ C Pr {A ∩ C} − Pr {A ∩ B ∩ C} Pr {A} · Pr {C} − Pr {A} · Pr {B} · Pr {C} Pr {A} · Pr {C} (1 − Pr {B}) � � Pr {A} · Pr {C} Pr B Pr {IA = 1} · Pr {IC = 1} Pr {IB = 0} Pr {IA = 1} · Pr {IB = 0} · Pr {IC = 1} and similarly for any other three binary values in place of 101. 10 (←−): Pr {A ∩ B ∩ C} = Pr {IA = 1 ∧ IB = 1 ∧ IC = 1} = Pr {IA = 1} · Pr {IB = 1} · Pr {IC = 1} = Pr {A} · Pr {B} · Pr {C} Also, � � Pr {A ∩ B ∩ C} + Pr A ∩ B ∩ C Pr {IA = 1 ∧ IB = 1 ∧ IC = 1} + Pr {IA = 1 ∧ IB = 1 ∧ IC = 0} Pr {IA = 1} · Pr {IB = 1} · Pr {IC = 1} + Pr {IA = 1} · Pr {IB = 1} · Pr {IC = 0} � � Pr {A} · Pr {B} · Pr {C} + Pr {A} · Pr {B} · Pr C � � = Pr {A} · Pr {B} (Pr {C} + Pr C ) = Pr {A} · Pr {B} Pr {A ∩ B} = = = = and similarly for B ∩ C and A ∩ C. �