Quiz 1

CS109 Winter 2021. February 3-5. By Chris Piech, Jerry Cain, Freya, and Doris

Take-Home Quiz information

Each quiz will be a 46.5-hour open-book, open-note exam. We have designed this quiz to approximate about 1-2 hours of active work

You can submit multiple times; we will only grade the last submission you submit before 1:00pm (Pacific time) on Friday, February 5 $^{th}$ . No late submissions can be accepted. When uploading, please assign pages to each question.
You should upload your submission as a PDF to Gradescope. We provide a LaTeX template if you find it useful, but we will accept any legible submission. You may also find the CS109 Probability LaTeX reference useful: https://www.overleaf.com/project/5f650a577489e90001f065be
Course staff assistance will be limited to clarifying questions of the kind that might be allowed on a traditional, in-person exam. If you have questions during the exam, please ask them as private posts via our discussion forum. We will not have any office hours for answering quiz questions during the quiz, and we can't answer any questions about course material while the quiz it out.
For each problem, briefly explain/justify how you obtained your answer at a level such that a future CS109 student would be able to understand how to solve the problem. If it's not fully clear how you arrived at your answer, you will not receive full credit. It is fine for your answers to be a well-defined mathematical expression including summations, products, factorials, exponents, and combinations, unless the question specifically asks for a numeric quantity or closed form. Where numeric answers are required, fractions are fine.

Honor Code Guidelines for Take-Home Quizzes

This exam must be completed individually. It is a violation of the Stanford Honor Code to communicate with any other humans about this exam (other than CS109 course staff), to solicit solutions to this exam, or to share your solutions with others.

The take-home exams are open-book: open lecture notes, handouts, textbooks, course lecture videos, and internet searches for conceptual information (e.g., Wikipedia). Consultation of other humans in any form or medium (e.g., communicating with classmates, asking questions on sites like Chegg or Stack Overflow) is prohibited. All work done with the assistance of any external material in any way (other than provided CS109 course materials) must include citation (e.g., ``Referred to Wikipedia page on $X$ for Question 2.''). Copying solutions is unacceptable, even with citation. If by chance you encounter solutions to the problem, navigate away from that page before you feel tempted to copy.

If you become aware of any Honor Code violations by any student in the class, your commitments under the Stanford Honor Code obligate you to inform course staff. Please remember that there is no reason to violate your conscience to complete a take-home exam in CS109.

Include this sentence in your submission: "I acknowledge and accept the letter and spirit of the Honor Code: <name>." where <name> is your full name.

1. The Freya Checkers Invitational [30 points]

Don't tell Stanford, but Chris and Jerry each have side jobs as professional Checkers players, and they're set to compete against one another and play a total of 9 games in the Freya Checkers Invitational. Each game results in either a win for Chris, a win for Jerry, or a tie. A win is worth 2 points, a tie is worth 1 point, and a loss is worth 0.

(7 points) How many different ways can Chris arrive at 2 wins, 5 draws, and 2 losses if all 9 games are played?
In addition to providing an expression above, please compute an integer answer:
(8 points) What is the probability that Chris gets 10 points when all 9 games are played? Assume that each game results in a win for Chris, a win for Jerry, or a tie with equal likelihood, and that all games are independent.
In addition to providing an expression above, please compute a numeric answer:
(7 points) Because Freya is in a hurry to get Chris home, Chris and arch-nemesis Jerry agree to play a best-of-9 tournament, where play stops when one accumulates 10 points, or they've played all 9 games, whichever comes first. How many different ways can Chris win the tournament by a score of 10 to 8?
In addition to providing an expression above, please compute an integer answer:
(8 points) Eager to get Chris home to Freya even more quickly, Jerry proposes they keep playing until one player's point total exceeds the other's by 3 or more points. Assume that Chris and Jerry each win a single game with probability of 0.25 and 0.15, respectively, and they tie with probability 0.6. What is the probability that Chris eventually wins?
In addition to providing an expression above, please compute a numeric answer:

2. Malware Detection [30 points]

Jerry's nephew, Andrew, just started high school this past September, and because all course instruction is online, his high school provided him with an old laptop so he could Zoom in for class. To better protect its own equipment from malware and viruses, the school installed two browser extensions to scrutinize all web downloads. Each download is either safe (event

S

) or unsafe (event

S^{C}

), and all downloads are examined by both extensions. The first extension marks the download as either safe (event

A

) or unsafe (event

A^{C}

), and the second extension marks the download as safe (event

B

) or unsafe (event

B^{C}

). Assume that 94% of Andrew's web downloads are safe, and that:

the first browser extension accurately marks unsafe downloads as unsafe with probability 0.93, but improperly marks safe downloads as unsafe with probability 0.04.
the second browser extension accurately marks unsafe downloads as unsafe with probability 0.85, but improperly marks safe downloads as unsafe with probability 0.02.

Assume that given a download is safe, the two browser extensions independently mark that download as safe. Similarly, the two browser extensions independently mark unsafe downloads as unsafe.

(6 points) Assuming a downloaded document is safe, what is the probability that at least one of the two extensions marks the download as unsafe?
In addition to providing an expression above, please compute a numeric answer:
(6 points) Assuming a downloaded document is safe, what is the probability that exactly one of the two extensions marks the download as unsafe?
In addition to providing an expression above, please compute a numeric answer:
(10 points) Given that both extensions mark the download as safe, what is the probability that the download is unsafe?
In addition to providing an expression above, please compute a numeric answer:
(8 points) Are the unconditioned events where the two extensions mark a download as safe independent? Why or why not?
In addition to providing an expression above, please compute a numeric answer:

3. Doris and Inventory Audits [30 points]

Jerry's Boston Terrier, Doris, is a San Francisco-based accountant, and much of her work has her auditing retail companies — literally showing up unannounced--to confirm their in-house inventory matches what their inventory software claims. If she finds evidence to suggest there are widespread discrepancies between physical in-store inventory and what's shared with the Internal Revenue Service (that's the U.S. Federal Tax Bureau) via inventory reports, she informs the IRS that a more thorough audit is warranted.

Assume Doris is auditing a company that maintains separate records for 4500 different items, 4400 of which are accurate and 100 of which are inaccurate. Rather than examining all 4500 records, Doris arbitrarily samples 100 of them (without replacement, 25 per paw). Let

X

be the random variable counting the number of inaccurate record found among all 100 samples, assuming all samples are equally likely.

(10 points) Compute $p_{X} (x)$ , which is the probability mass function of $X$ as defined above.
In addition to providing an expression above, please compute a numeric answer:
(6 points) Compute the expected value of X, i.e. E[X]. You should express your answer as a sum of a finite number of terms (which you share as part of your answer), but then write a short Python program (which need not be included) to compute the summation and present a single numeric value.
In addition to providing an expression above, please compute a numeric answer:

To guard against some unlucky sampling, Doris stops if the first sample produces either 0 (she takes that as conclusive) or three or more inaccurate records. If she finds either one or two inaccurate records in her initial sample of 100, she draws a new sample of 100 from the original 4500, just as she did originally, and counts the number of inaccuracies the same exact way.

(7 points) Let $Y$ be the random variable counting the number of inaccuracies counted between the first and, if needed, second audits. What is $P (Y = 2)$ ?
In addition to providing an expression above, please compute a numeric answer:
(7 points) Compute $E [Y]$ in terms of $E [X]$ . Your answer should be framed in terms of $E [X]$ instead of the exact value you computed for part b, just in case your answer to part b was incorrect.
In addition to providing an expression above, please compute a numeric answer: