Discrete Mathematics and Probability Theory Solutions Part 1

Section1: Straightforwardquestions(30points) You get one drop: do 5 out of the following 6 questions. Bonus for getting all six perfectly. No partial credit will be given. 3. Prove It Prove by induction that 5n − 1 is divisible by 4 for all integers n ≥ 1. Solution: Base case: P(1) : 51 − 1 = 4, which is clearly divisible by 4. Inductive Hypothesis: Suppose P(k) : 5k − 1 is divisible by 4 for some integer k > 1. Inductive Step: We want to show that P(k) ⇒ P(k + 1). By the Inductive Hypothesis, since 5k − 1 is divisible by 4, 5k − 1 = 4l for some integer l . 5k+1 − 1 = 5 · 5k − 1 = 5(5k − 1)+4 = 5(4l)+4 = 4(5l + 1), which means 5k+1 − 1 is also divisible by 4. By the Principle of Induction, the original statement must hold. Q.E.D. 4. Equate It Use a combinatorial argument to prove that the following combinatorial identity is true (i.e., provide a story for why the identity should hold). Solution: n2n−1 =   n n +2 + · · · +(n − 1) 2 1   n n +n n−1 n We want to count the number of ways that we can select a team with a single leader out of n people. We don’t allow an empty team because we insist on having a single leader. Left-hand side: From n people, pick one team leader and then some (possibly empty) subset of other people on his team. Right-hand side: First pick k people on the team, then pick the leader among them. For example, when k is  n members choose our from. 2, we firstto choose team of 2 people2 inways, then pick a leader in 2 ways because there are only 2 Since the left-hand side and the right-hand side count the same thing, they are equal. Q.E.D. 5. Bound It A random variable X is always strictly larger than -100. You know that E [X]=−60. Give the best upper bound you can on P (X ≥ −20). Solution: Notice that we do not have the variance of X, so Chebyshev’s bound is not applicable here. There is no upper bound on X, so Hoeffding’s inequality cannot be used. We know nothing else about it’s distribution so we cannot evaluate E[esX ] and so Chernoff bounds are not available. Since X is also not a sum of other random variables, other bounds or approximations are not available. This leaves us with just Markov’s Inequality. But Markov Bound only applies on a nonnegative random variable, whereas X can take on negative values. This suggests that we want to “shift” X somehow, so that we can apply Markov’s Inequality on it. Define a random variable Y = X + 100, which means Y is strictly larger than 0, since X is always strictly larger than −100. Then, E[Y ]=E[X + 100]=E[X]+100 = −60 + 100 = 40. Finally, the upper bound on X that we want can be calculated via Y , and we can now apply Markov’s Inequality on Y since Y is strictly positive. P (X ≥ −20)=P (Y ≥ 80) ≤ Hence, the best upper bound on P (X ≥ −20) 2is. 1 E[Y ] 80 = 40 1 = 80 2 6. Match It We have n i.i.d. Bernoulli-p random variables. Let A be the average of these random variables. The following plots are on log-scale and show various bounds and approximations for the probability of the average being more than 1.1 times the mean of A as a function of n (depicted in linear scale). The scatter points represent the actual probability of the deviation. (a) In this set of plots, p = 0.4. Label which one corresponds to Markov’s Inequality, to Chebyshev’s Inequality, and to a Chernoff Bound. Solution: From left to right, Chebyshev’s Inequality, Chernoff Bound, Markov’s Inequality. The dead give-away for Markov is that it doesn’t get better with increasing n. The dead give-away for Chernoff is that it is a straight line of constant negative slope on such a plot with the horizontal axis in linear scale and the vertical axis in logarithmic scale. This leaves the first one as being Chebyshev’s inequality. We can also see that Chebyshev’s inequality can be larger than 1 while the other two will never be so when evaluating the probability of something being bigger than its mean. (b) In the next set of plots, p = 0.6. Label which one corresponds to Chebyshev’s Inequality, to Hoeffding’s Inequality, and to the Central Limit Theorem. Solution: From left to right, Central Limit Theorem, Chebyshev’s Inequality, Hoeffding’s Inequality. The dead give-away for Hoeffding is that it is a straight line of constant negative slope on such a plot with the horizontal axis in linear scale and the vertical axis in logarithmic scale. The dead give-away for the CLT is that it is an approximation and not a bound – so the points are on both sides of the CLT curve. This leave the middle one as being Chebyshev’s inequality. We can also see that Chebyshev’s inequality can be larger than 1 while the other two will never be so when evaluating the probability of something being bigger than its mean. 7. Expect It We call a couple a soulmate couple if both of them have each other as the first person on their preference lists. If there are n men and n women, and all of their preference lists are independently uniformly generated over all permutations, what is the expected number of soulmate couples? Solution: This is similar to the homeworks example in Note 15. Let ( 1 0ifotherwise man i is part of a soulmate couple Xi = 1 There is a probability of n that the woman at the top of man i’s list also has man i at the top of her list, therefore, P(Xi = 1)= 1 , n 1 1 n−1 E(Xi )=1 · +0· n = n n The number of soulmate couples is equivalent to the number of men who belong to them, so the expected number of soulmate couples is ∑ E ni=1 n ! ∑ E(Xi ) (By Linearity of Expectation) i=1 Xi = = n · E(Xi ) 1 = n· n =1 ✷ 8. Provoke It In a demonstration/protest march, there are 2 kinds of people: civilians and undercover police. You know that 99% of the civilians are peaceful, and 1% advocate violence. You also know that 50% of the undercover police are agent provocateurs (who advocate violence) and 50% of them are peaceful. 2% of the protestors are undercover police. Given that you see a person in the demonstration advocating violence, what is the probability that this person is undercover police? (It is fine to leave the answer as a simplified fraction.) Solution: We are given that people in the protest are either civilians or undercover police with the following probabilities. P(Person is a civilian)=P(C)=0.98 and P(Person is an undercover police)=P(U P)=0.02 We are also given that P(Violent|C)=0.01, P(Peaceful|C)=0.99, P(Violent|U P)=0.5, P(Peaceful|UP)= 0.5. You spot a person advocating violence in the crowd. We want to find the probability that this person is an undercover police officer i.e., P(UP|Violent). Using Bayes’ Rule we have P(UP|Violent)= P(UP ∩ Violent) P(Violent) = P(Violent|U P) × P(UP) P(Violent) (1) By the total probability rule we get, P(Violent)=P(Violent|U P) × P(U P) + P(Violent|C) × P(C)=0.5 × 0.02 + 0.01 × 0.98 = 0.0198 (2) Plugging Eq (2) and other given values to Eq (1), we get P(UP|Violent)= 0.5 × 0.02 0.0198 = 50 99 Section2: Additionalstraightforwardquestions(27points) You get one drop: do 3 out of the following 4 questions. Bonus for getting all of them perfectly. Very little partial credit will be given. 9. Sections An EECS class with 3n students has three discussion sections, and each student attends exactly one of them by choosing one uniformly at random, independently of the others. Use Stirling’s approximation to estimate an n so that the probability of all three sections having exactly the same number of students is about 1.6%. It is fine to leave the answer as a simplified formula for n. √ √ (Numerical hints for those who prefer actual numbers: 2π ≈ 6.28, 2π ≈ 2.51, 3 ≈ 1.73.) Solution: The number of ways that all three sections can have exactly the same number of students is the number of ways each section has 3n/3 = n students, (3n)!    n!n!n! = (n!)3 3n (3n)! 2n n = n n n 3n √ 3n ≈ 2π · 3n e n 3  √ n 2πn e n  √ √ 3n = 2πn · 3 · 33n  ne 3n √ √ 2π n3n· (2π n) · e 3·3 = 2πn (Stirling’s Approximation) The number of ways 3n students can choose sections is 33n , therefore, √ 3 · 33n 2πn P(All 3 sections have the same number of students) ≈33n √ 3 0.016 = 2πn √ 3 n= 2π · 0.016 1.73 n≈ ≈ 17.22 6.28 · 0.016 But since the number n has to be a positive integer, we take the floor and get 17. ✷ 10. Two Face Suppose you have two coins, one that has heads on both sides and another that has tails on both sides. (a) You pick one of the two coins uniformly at random and you flip that coin 400 times. Approximate the probability of getting more than 220 heads. Your answer should be a number that approximates this probability, accurate to 2 digits after the decimal point. Solution: There are two equally likely outcomes of this experiment. Either you pick the doubleheaded coin, in which case you get 400 heads, or you pick the double-tailed coin, in which case you get 0 heads. Thus, the probability of getting more than 220 heads is 0.5. (b) You pick one of the two coins uniformly at random and flip it. You repeat this process 400 times, each time picking one of the two coins uniformly at random and then flipping it, for a total of 400 flips. Approximate the probability of getting more than 220 heads. Your answer should be a number that approximates this probability, accurate to 2 digits after the decimal point. 1 Solution: Let X be the number of heads. In each flip, you have probability 2 of picking the double1 headed coin and getting heads and probability of picking the double-tailed coin and not getting 2 1 = 200 and Var(X)= heads. The flips are independent, so X ∼ Bin(400 ,1 2 ). Since E(X)=400 · 2 400 ·21· 21 = 100. This gives a standard deviation of 10. So we are asking what is the probability of being two standard deviations or more away from the mean in the positive direction. In other words, we can approximate X as a normal Y ∼ N(400, 100). Then   Y − 200 Pr[X > 220] ≈ Pr[Y > 220]=Pr > 2 = Pr[Z > 2]=1 − Pr[Z ≤ 2], 10 where Z is the standard normal. Thus, Pr[X ≥ 220] ≈ 1 − 0.9772 = 0.0228. (c) Now you pick one of the two coins uniformly at random and flip it four times. You repeat this process 100 times, each time picking one of the two coins uniformly at random and then flipping it four times, for a total of 400 flips. Approximate the probability of getting more than 220 heads. Your answer should be a number that approximates this probability, accurate to 2 digits after the decimal point. Solution: Let S be the number of times you pick the double-headed coin. Each time, you have 1 probability 21 of picking the double-headed coin and probability 2 of picking the double-tailed coin, ), and where the choice of coin is independent each time. Thus, S ∼ Bin(2100 , 1 E(S)=100 · 12 = 50 and Var(S)=100 · 1 2 · 21 = 25. So the standard deviation of S is 5. This means that the standard deviation for the number of heads 4S is 20. The event we are interested in what is the chance that 4S is more than 1 standard deviation away from the mean in the positive direction. In other words, we can approximate S as a normal U ∼ N(100, 25). Let T be the total number of heads. Then T = 4S, so   U − 50 > 1 = Pr[Z > 1]=1 − Pr[Z ≤ 1], Pr[T > 220]=Pr[S > 55] ≈ Pr[U > 55]=Pr 5 where Z is the standard normal. Thus, Pr[T ≥ 220] ≈ 1 − 0.8413 = 0.1587. On this question as well as the previous part, the indications to use the CLT were pretty clear. We want to approximate the probability, not bound it. 11. Estimating π One can estimate π by playing darts with a special dartboard shown in figure 1. Assume every time you throw a dart, the dart will always be inside the square. The probability that your dart lands inside the circle Xi πbe the random variable is equal to the ratio of the area of the circle to the area of the square, 4 . Leti.e., denoting whether your dart is within the circle after your i-th throw. How can you estimate π using this experiment? How many times should you throw to ensure your estimation error is within 0.01 with probability at least 95%? (You can just leave the numerical expression of the number of times but not compute the exact value.) Figure 1: Dartboard. n = 4 Solution: Suppose we throw the dart n times in order to estimate π. We can estimate π byn ∑Mi=1 n Xi . Then we want P(|Mn − π| ≥ 0.01) ≤ 0.05. π Xi is a bernolli random variable with P(Xi = 1)= 4 . The expectation of Mn is E[Mn ]=E[ n 4 n ∑ Xi ]= i=1 4 n n ∑ E[Xi ]= i=1 π 4 · n · = π. n 4 By Chebyshev’s inequality: The variance of Mn is Var(Mn )=Var( n 4 n ∑ Xi )= i=1 42 n2 n ∑ Var(Xi )= i=1 π π 16 · n · (1 − )= π (4 − π ) n2 4 n 4 . So P(|Mn − π| ≥ 0.01) ≤ Let π (4−π ) 0.012 n Var(Mn ) 0.012 = π(4 − π) . 0.012 n π(4−π) = 539353.2. We have to throw at least 539354 times. 2 ·0.05 ≤ 0.05, we get n ≥ 0.01 One may assume the exact value of π is unknown. Then we can use the inequality π(4 − π)=−(π − 2)2 + π) 4 4 = 800000. ≤ 0.01 4 ≤ 4. Let π0(4− 2 n ≤ 0.05, and we can get n ≥ 0.012 ·0.05 .012 n [Extra page. If you want the work on this page to be graded, make sure you tell us on the problem’s main page.] By Hoeffding’s inequality: P(|Mn − π| ≥ 0.01)=P(| Let 2e −n 2·0.0025 (1−0)2 2 Mn 4 − 2 ≤ 0.05, we get n ≥ ln π −n 2·0.002 | ≥ 0.0025) ≤ 2e (1−0)2 . 4 2 0.05· − (1−0) 2 2·0.0025 2 = 295110.36. We have to throw at least 295111 times. 12. Independent Shares Consider a secret-sharing scheme over GF(5) that divides a secret among 4 people. Assume the secret is uniformly chosen from 0,1,2,3,4. We use the standard polynomial-based secret-sharing scheme so that any 2 people can recover the secret. The linear coefficient in the polynomial is chosen uniformly from 0,1,2,3,4 and independently of the secret. Show that the shares (i.e. values obtained by evaluating the polynomial at their point) given to person 1 and person 2 are independent. Solution: Let the secret be X0 and the linear coefficient be X1 . These are chosen independently, so the sample space is the product-space of pairs (X0 , X1 ). Let the shares of person 1 and 2 be Y1 and Y2 , respectively. f These are random variables, each a function of (X0 , X1 ). The secret-sharing scheme maps (X 0, X 7→ (Y11) ,Y2 ) through some function f (ie, by evaluating the polynomial determined by X0 , X1 ). Notice that f is a bijection, since it maps between two unique representations of a degree-1 polynomial (the coefficient representation and the evaluation representation). Therefore, for given shares y1 , y2 , the event {(Y1 ,Y2 )=(y1 , y2 )} is exactly the event { f −1 (Y1 ,Y2 )= f −1 (y1 , y2 )} = {(X0 , X1 )= f −1 (y1 , y2 )}. Letting (x0 , x1 )= f −1 (y1 , y2 ), we find the distribution factors: Pr[(Y1 ,Y2 )=(y1 , y2 )]=Pr[(X0 , X1 )=(x0 , x1 )]=Pr[X0 = x0 ] Pr[X1 = x1 ]=1/25 Where the second-to-last equality follows by the stipulated independence of the coefficients X0 and X1 . Therefore, the joint distribution of (Y1 ,Y2 ) is uniform on a square, so Y1 and Y2 are independent. Remarks: The main idea here is that the two coefficients and two shares are equivalent ways of describing the same underlying “random degree-1 polynomial.” Any way of making this formal was acceptable (including more “brute-force” ways than the above.) It was insufficient to simply say “because one person’s share is hidden from another” or “because secret sharing works”, etc. The point of this problem was to prove exactly this. Section3: True/False(30points) You get one drop: do 3 out of the following 4 questions. Bonus for getting all four correct. For each question in this section, determine whether the given statement is TRUE or FALSE. If TRUE, prove the statement. If FALSE, provide a counterexample or otherwise disprove it. 13. Conditional If P(A) > P(B), and P(C|A) > P(C|B), then P(A|C) > P(B|C). Mark one: TRUE or FALSE. Solution: The probability of any event lies in the range [0, 1]. Thus we have P(A) > P(B) ≥ 0 (3) P(C|A) > P(C|B) ≥ 0 (4) Thus if we multiply the two inequalities Eq (3) and Eq (4), the sign of the inequality is preserved and we get, P(A) × P(C|A) > P(B) × P(C|B) P(A ∩C) > P(B ∩C) P(C) × P(A|C) > P(C) × P(B|C) Since P(A) > P(B) ≥ 0 and so P(C) ≥ P(C ∩ A)=P(A)P(C|A) > 0, we can divide through by P(C) from both sides of the inequality which preserving the sign to get P(A|C) > P(B|C). 14. Epsilon n1 Xi be the average of n Consider i.i.d. random variables {Xi } with mean µ and variance σ 2 . Let Ann ∑ =i=1 such random variables. Let g(ε, δ ) be the minimum n so that An is within ±ε of µ with probability at least ε (1 − δ ). Then for δ = 0.1, we can be certain that g( , δ ) ≤ 2g(ε, δ ). 2 Mark one: TRUE or FALSE . Solution: The conceptually easiest solution here makes a direct appeal to continuous random variables. (And this was accepted if done correctly.) Consider the case when the An s are exactly Gaussian/Normal random variables. For example, let Xi ∼ N(0, 1), so µ = 0, σ 2 = 1. Then An ∼ N(0, 1/n). Let ε be such that Φ(ε ) − Φ(−ε )=1 − δ . That is, the probability of a standard normal being within ±ε is 1 − δ . Therefore, g(ε, δ )=1. In order for An to be within ±ε/2 of its mean with probability 1 − δ , the standard deviation of An must be 1/2. Notice the standard deviation of A√nnis, so1 g(2ε, δ )=4. A much more elementary counterexample: Let each Xi be Bernoulli(1/2). So µ = 1/2. Let ε = 1/2. Then g(ε, δ )=1, trivially. But notice that g(ε/2, δ ) > 2: The distribution of A2 is: 0 w.p. 1/4; 1/2 w.p. 1/2; 1 w.p. 1/4. So Pr[|A2 − µ| ≥ ε/2]=Pr[|A2 − 1/2| ≥ 1/4]=1/2 < 1 − δ . How could you have come up with the above counterexample? Just try fair coins as your default first example. 1 Remarks: Many students appealed to the √ scaling of the standard deviation, but argued using Chebyshev’s n 2 inequality: Pr[|An − µ| ≥ ε] ≤ nεσ 2 . Although this scaling turns out to be correct, Chebyshev can only give an n that is sufficiently high (not necessarily high), since it is a bound. We gave significant partial credit for such solutions, though they were not rigorous counterexamples. In principle, it should be possible to give a generic counterexample to this by appealing to the Berry-Esseen inequality form of the CLT. But nobody seems to have done that.