Problem Set#2 Solution

1. Let E and F be events defined on the same sample space S. Prove that:

P(EF)    P(E) + P(F)    1

(This formula is known as Bonferroni’s Inequality.)




    2. Say in Silicon Valley, 35% of engineers program in Java and 28% of the engineers who program in Java also program in C++. Furthermore, 40% of engineers program in C++.

        a. What is the probability that a randomly selected engineer programs in Java and C++?

        b. What is the conditional probability that a randomly selected engineer programs in Java given that they program in C++?



    a) This probability can easily calculated since we know that P (J) and P (CjJ). We can simply use the general definition of conditional probability. Thus, we get:


    a) We are trying to find P (JjC), which we can obtain using Bayes’ Theorem, since we know P (CjJ), P (C) and P (J) (and our answer from part a):


    3. A website wants to detect if a visitor is a robot. They give the visitor three CAPTCHA tests that are hard for robots but easy for humans. If the visitor fails one of the tests, they are flagged as a robot. The probability that a human succeeds at a single test is 0.95, while a robot only succeeds with probability 0.15. Assume all tests are independent.

        a. If a visitor is actually a robot, what is the probability they get flagged (the probability they fail at least one test)?
        b. If a visitor is human, what is the probability they get flagged?

        c. The percentage of visitors on the site that are robots is 5%. Suppose a visitor gets flagged. Using your answers from part (a), what is the probability that the visitor is a robot?



c) Since visitors can only be robot or human and one cannot be both a robot and human (mutually exclusive), the probability of visitors on the site that are humans is 0:95 (i.e. 1 0:05). Let us redefine our events:

F = event of being flagged

H = visitor is human

R = visitor is robot




    4. Say all computers either run operating system W or X. A computer running operating system W is twice as likely to get infected with a virus as a computer running operating system X. If 70% of all computers are running operating system W, what percentage of computers infected with a virus are running operating system W?


    5. Two cards are randomly chosen without replacement from an ordinary deck of 52 cards. Let E be the event that both cards are Aces. Let F be the event that the Ace of Spades is one of the chosen cards, and let G be the event that at least one Ace is chosen. Compute:

P (E j F )

        a. P (E j G)


    6. Two emails are received at a mail server. Suppose that each email is spam with probability 0.8 and that whether each email message is spam is an independent event from the other.

        a. Suppose that you are told that at least one of the two emails is spam. Compute the conditional probability that both emails are spam.

        b. Suppose now that one of the emails is randomly (accidentally) forwarded from the server to your account, and you see that this email is spam. What is the probability that both emails originally received by the server are spam in this case? Explain your answer.



    7. After a long night of programming, you have built a powerful, but slightly buggy, email spam filter. When you don’t encounter the bug, the filter works very well, always marking a spam email as SPAM and always marking a non-spam email as GOOD. Unfortunately, your code contains a bug that is encountered 10% of the time when the filter is run on an email. When the bug is encountered, the filter always marks the email as GOOD. As a result, emails that are actually spam will be erroneously marked as GOOD when the bug is encountered. Let p denote the probability that an email is actually non-spam, and let q denote the conditional probability that an email is non-spam given that it is marked as GOOD by the filter.

        a. Determine q in terms of p.

        b. Using your answer from part (a), explain mathematically whether q or p is greater. Also, provide an intuitive justification for your answer.




    8. Consider a hash table with 15 buckets, of which 9 are empty (have no strings hashed to them) and the other 6 buckets are non-empty (have at least one string hashed to each of them already). Now, 2 new strings are independently hashed into the table, where each string is equally likely to be hashed into any bucket. Later, another 2 strings are hashed into the table (again, independently and equally likely to get hashed to any bucket). What is the probability that both of the final 2 strings are each hashed to empty buckets in the table?


9. Five servers are located in a computer cluster. After one year, each server independently is still working with probability p, and otherwise fails (with probability 1 p).

    a. What is the probability that at least 1 server is still working after one year?

    b. What is the probability that exactly 2 servers are still working after one year?

    c. What is the probability that at least 2 servers are still working after one year?




    10. The Superbowl institutes a new way to determine which team receives the kickoff first. The referee chooses with equal probability one of three coins. Although the coins look identical, they have probability of heads 0.1, 0.5 and 0.9, respectively. Then the referee tosses the chosen coin 3 times. If more than half the tosses come up heads, one team will kick off; otherwise, the other team will kick off. If the tosses resulted in the sequence H, T, H, what is the probability that the fair coin was actually used?



    11. A robot, which only has a camera as a sensor, can either be in one of two locations: L1 (which does not have a window) or L2 (which has a window). The robot doesn’t know exactly where it is and it represents this uncertainty by keeping track of two probabilities: P (L1) and P (L2). Based on all past observations, the robot thinks that there is a 0.7 probability it is in L1 and a 0.3 probability that it is in L2.

The robot then observes a window through its camera, and although there is only a window in L2, it can’t conclude with certainty that it is in fact in L2, since its image recognition algorithm is not perfect. The probability of observing a window given there is no window at its location is 0.2, and the probability of observing a window given there is a window is 0.9. After incorporating the observation of a window, what are the robot’s new probabilities for being in L1 and L2, respectively?


    12. The color of a person’s eyes is determined by a pair of eye-color genes, as follows:

        ◦ if both of the eye-color genes are blue-eyed genes, then the person will have blue eyes

        ◦ if one or more of the genes is a brown-eyed gene, then the person will have brown eyes

A newborn child independently receives one eye-color gene from each of its parents, and the gene it receives from a parent is equally likely to be either of the two eye-color genes of that parent. Suppose William and both of his parents have brown eyes, but William’s sister (Claire) has blue eyes. (We assume that blue and brown are the only eye-color genes.)

    a. What is the probability that William possesses a blue-eyed gene?

    b. Suppose that William’s wife has blue eyes. What is the probability that their first child will have blue eyes?



    b) As mentioned in part a), there are three possible combinations of genes for William given he has brown eyes. Thus, we can find the total possible combinations given these three combinations and William’s wife’s genes (b; b). Then we would also find the number of favorable outcomes: those that produce (b; b).

    13. Your colleagues in a comp-bio lab have sequenced DNA from a large population in order to understand how a gene (G) influences two particular traits (T1 and T2). They find that P (G) = 0:6, P (T1kG) = 0:7, and P (T2kG) = 0:9. They also observe that if a subject does not have the gene G, they express neither T1 nor T2. The probability of a patient having both T1 and T2 given that they have the gene G is 0.63.

        a. Are T1 and T2 conditionally independent given G?
        b. Are T1 and T2 conditionally independent given GC?
        c. What is P (T1)?
        d. What is P (T2)?
        e. Are T1 and T2 independent?



    14. See Problem Set #2 for a full write-up of this problem. You will submit parts a and b as code in Gradescope and write up answers to c and d (and optionally e) in this document.