CS 70 Discrete Mathematics for CSSpring 2008 David Wagner HW 13Due Thursday, March 8thImportant: Show your work on all problems on this homework.1. (6 pts.) The myth of fingerprints, cont.A crime has been committed. The police discover that the criminal has left DNA behind, and they comparethe DNA fingerprint against a police database containing DNA fingerprints for 20 million people. Assumethat the probability that two DNA fingerprints (falsely) match by chance is 1 in 10 million. Assume that,if the crime was committed by someone whose DNA fingerprint is on file in the police database, then it’scertain that this will turn up as a match when the police compare the crime-scene evidence to their database;the only question is whether there will be any false matches.Let D denote the event that the criminal’s DNA is in the database; ¬D denotes the event that the criminal’sDNA is not in the database. Assume that it is well-documented that half of all such crimes are committedby criminals in the database, i.e., assume that Pr[D] = Pr[¬D] = 1/2. Let the random variable X denote thenumber of matches that are found when the police run the crime-scene sample against the DNA database.In the following, compute all probabilities to at least two digits of precision.(a) Calculate Pr[X = 1|D].(b) Calculate Pr[X = 1|¬D].(c) Calculate Pr[¬D|X = 1].(d) Suppose that the police find exactly one match, and promptly prosecute the corresponding individual.Suppose you are appointed a member of the jury, and the DNA match is the only evidence that thepolice present. Do you think the defendant should be convicted? Why or why not?2. (6 pts.) Chebyshev inequalityA friend tells you about a course called “Laziness in Modern Society” that requires almost no work. Youhope to take this course so that you can devote all of your time to CS70. At the first lecture, the professorannounces that grades will depend only a midterm and a final. The midterm will consist of three questions,each worth 10 points, and the final will consist of four questions, also each worth 10 points. He will give anA to any student who gets at least 60 of the possible 70 points.However, speaking with the professor in office hours you hear some very disturbing news. He tells you thatto save time he will be grading as follows. For each students midterm, he’ll choose a real number randomlyfrom a distribution with meanµ= 5 and varianceσ2= 1. He’ll mark each of the three questions with thatscore. To grade the final, he’ll again choose a random number from the same distribution, independent ofthe first number, and he’ll mark all four questions with that score.If you take the class, what will the mean and variance of your total class score be? Can you conclude thatyou have less than a 5% chance of getting an A? Why?CS 70, Spring 2008, HW 13 13. (6 pts.) Normal distributionSuppose the overall scores of the students in a Discrete Math class are approximately normally distributedwith a mean of 83 and a standard deviation of 6. Compute:(a) the lowest passing score, if the bottom 5% of these students fail;(b) the highest B, if the top 10% of the students are given A’s.Note: You may assume that if X is normal with mean 0 and variance 1, then Pr[X ≤ 1.3] ≈ 0.9 and Pr[X ≤1.65] ≈ 0.95.4. (9 pts.) z-scoresLet Z be a random variable that has a normal distribution with mean 0 and variance 1. Given a real numberz, there are tables that allow us to compute Pr[Z ≤ z] as a function of z. The value z is sometimes called az-score. The tables allow us to compute one (or both) of the following quantities:• The “left tail”: The left tail represents the values of Z that are less than or equal to z, and Pr[Z ≤ z] isthe area under the normal curve and where x ≤ z. For instance, Pr[Z ≤ −1] ≈ 0.1587, Pr[Z ≤ 0] = 0.5,and Pr[Z ≤ 1] ≈ 0.8413.• The “right tail”: The right tail represents the values greater than or equal to z. For instance, Pr[Z ≥1] ≈ 0.1587, and Pr[Z ≥ 2] ≈ 0.0228.You can find resources for calculating these values—e.g., normal tables, normal calculators—at http://www.cs.berkeley.edu/˜daw/teaching/cs70-s08/tables.html. These typically allowyou to go back and forth between a z-score z and the probability Pr[Z ≤ z] (i.e., the area under the “left tail”),or between z and Pr[Z ≥ z] (i.e., the area under the “right tail”).(a) Let the r.v. Z be normally distributed with mean 0 and variance 1. Use a table or calculator mentionedabove to find the approximate value of Pr[Z ≤ 1.5].z-scores have many applications. For instance, if the random variable X is normally distributed with meanµand varianceσ2, then the random variable X can be normalized to get a random variable Xnormdefined byXnorm= (X −µ)/σ. A useful fact is that, with these assumptions, Xnormwill be normally distributed withmean 0 and variance 1. Note that the value of Xnormcan be viewed as a z-score.(b) Suppose X is normally distributed with mean 100 and standard deviation 10. Calculate Pr[X ≥ 125].You may wish to use the resources listed above.Here is another application of z-scores. Let B be the number of Heads after flipping n coins, with Headsprobability p, i.e., B ∼ Binomial(n, p). We have shown that E[B] = np and Var(B) = np(1− p). It turns outthat, for large n, the binomial distribution B approximates the normal distribution with the same mean andvariance. Let’s normalize B, to get a random variable Bnormdefined as follows:Bnorm=B− nppnp(1− p).Given the assumption that B is approximately normally distributed with mean np and variance np(1− p),then Bnormis approximately normally distributed with mean 0 and variance 1. Thus, the value of Bnormcanbe viewed as a z-score.(c) Find a value k for which, when you flip a fair coin 10,000 times, the probability of k or more heads isapproximately 0.20.CS 70, Spring 2008, HW 13 25. (8 pts.) Statistical significanceA college soccer team won its conference championship 11 times in the first 20 years of existence. Then, forthe next 20 years it won only 3 times. Prof. Argyle argues that the soccer team has gotten worse; but Prof.Plaid insists that this difference is just due to bad luck. Let’s figure out whether this difference is statisticallysignificant or whether it can be plausibly attributed to random chance.To model this, let’s suppose the probability of winning the championship was p in each of the first 20 years,and q in the each of the second 20
View Full Document
Unlocking...