Chris Piech PSet #2

CS109 October 5, 2018

Problem Set #2
Due: 1:00pm on Monday, Oct 15th
For each problem, briefly explain/justify how you obtained your answer in order to obtain full
credit. Your explanations will help us determine your understanding of the problem, whether or
not you got the correct answer. Moreover, in the event of an incorrect answer, we can still try to
give you partial credit based on the explanation you provide. It is fine for your answers to include
summations, products, factorials, exponentials, or combinations, unless you are specifically asked
for a single numeric answer. The website has both datasets and file reading code. For coding
problems, explain how you came to your answer, but don’t submit source code.

Warmup
1. Say in Silicon Valley, 36% of engineers program in Java and 24% of the engineers who
program in Java also program in C++. Furthermore, 33% 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 he/she programs in C++?

2. 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 first card chosen is the Ace
of Spades. Compute: P(E | F).

3. 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 3 servers are still working after one year?
c. What is the probability that at least 3 servers are still working after one year?

4. 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 in 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.3. Assume all tests are independent.
a. If a robot visits the website, what is the probability they get flagged?
b. If a visitor is human, what is the probability they get flagged?
c. The fraction of visitors on the site that are robots is 1/10. Suppose a visitor gets flagged.
What is the probability that visitor is a robot?

5. Recall the game set-up in the “St. Petersburg’s paradox” discussed in class: there is a fair coin
which comes up "heads" with probability p = 0.5. The coin is flipped repeatedly until the first
"tails" appears. Let N = number of coin flips before the first "tails" appears (i.e., N = the
number of consecutive "heads" that appear). Given that no one really has infinite money to
offer as payoff for the game, consider a variant of the game where you win MIN($2N, X),
 –2–

where X is the maximum amount that the game provider will pay you after playing. Compute
the expected payoff of the game for the following values of X. Show your work.
a. X = $5.
b. X = $500.
c. X = $4096.

6. A bit string of length n is generated randomly such that each bit is generated independently
with probability p that the bit is a 1 (and 0 otherwise). How large does n need to be (in terms
of p) so that the probability that there is at least one 1 in the string is at least 0.7?

7. The probability that a Netflix user likes a movie Mi from the “Tearjerker” genre, given that
they like the Tearjerker genre, is pi. The probability that a user likes Mi given that they do not
like the Tearjerker genre, is qi. Of all Netflix users, 60% like the Tearjerker genre. Assume
that, conditioned on knowing a user’s preference for the genre (either liking the genre or not
liking it), liking movie M1 , M2 and M3 are independent events. Express all your answers in
terms of qs and ps. What is the probability:
a. That a user likes all three movies M1, M2 and M3 given that they like the Tearjerker genre?
b. That they like at least one movie M1, M2 or M3 given that they like the Tearjerker genre?
c. That they like the Tearjerker genre given that they like M1, M2 and M3?

Program Analysis
8. Suppose we want to write an algorithm fairRandom for randomly generating a 0 or a 1 with
equal probability (= 0.5). Unfortunately, all we have available to us is a function:
int unknownRandom();
that randomly generates bits, where on each call a 1 is returned with some unknown probability
p that need not be equal to 0.5 (and a 0 is returned with probability 1 – p). Consider the
following algorithm for fairRandom:
def fairRandom():
while True:
r1 = unknownRandom()
r2 = unknownRandom()
if (r1 != r2): break
return r2;

a. Show mathematically that fairRandom does indeed return a 0 or a 1 with equal probability.

b. Say we want to simplify the function, so we write the simpleRandom function below.
Would the simpleRandom function also generate 0’s and 1’s with equal probability?
Explain why or why not. Determine P(simpleRandom returns 1) in terms of p.

int simpleRandom() {
r1 = unknownRandom()
while True:
r2 = unknownRandom()
if (r1 != r2): break
r1 = r2
return r2
 –3–

Localization
In this multi part problem you are going to solve key components for “Localization” which is the
computer science problem of tracking the location of objects when there is uncertainty.

9. A robot, which only has a camera as a sensor, can either be in one of two locations: L1 or L2.
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.8 probability it is in L1 and a 0.2 probability that it is in L2.

The robot’s vision algorithm detects a window, and although there is only a window in L2, it
can’t conclude that it is in fact in L2: 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 is the robot’s new values for P(L1) and P(L2)?

10. [Coding] Your cell phone is constantly trying to keep track of where you are. At any given
point in time, for all nearby locations, your phone stores a probability that you are in that
location. Right now your phone believes that you are in one of 16 different locations arranged
in a grid with the following probabilities (see the figure on the left):
Prior Belief of Location P(Cell Tower
P(Observe two Distance | Location)
bars of signal | Location)

0.05 0.10 0.05 0.05 0.75 0.95 0.75 0.05

0.05 0.10 0.05 0.05 0.05 0.75 0.95 0.75

0.05 0.05 0.10 0.05 0.01 0.05 0.75 0.95

0.05 0.05 0.10 0.05 0.01 0.01 0.05 0.75

Your phone connects to a known cell tower and records two bars of signal. For each grid
location Li you know the probability of observing two bars from this particular tower, given
that the cell phone is in location Li (see the figure on the right). That value is based on
knowledge of the dynamics of this particular cell tower and stochasticity of signal strength.
Example: the highlighted cell on the left figure means that you believed there was a 0.05
probability that the user was in the bottom right grid cell prior to observing the cell tower
signal. The highlighted cell on the right figure means that you think the probability of observing
two bars, given the user was in the bottom right grid cell, is 0.75.
For each of the 16 location positions, calculate the new probability that the user is in each
location given the cell tower observation. Write a program to calculate the probabilities. The
matrices are provided on the website on the problem set #2 page. Report the probabilities of
all 16 cells and write a short explanation of your program. The grid in the left figure is stored
in a file called “[Link]” the grid in the right figure is stored in a file called “[Link]”
 –4–

DNA
11. 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?
c. Still assuming that William’s wife has blue eyes, if their first child had brown eyes, what
is the probability that their next child will also have brown eyes?

12. 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(T1|G) = 0.8 and P(T2|G) = 0.9. They also observe that if a subject does not have the gene,
they express neither T1 nor T2. The probability of a patient having both T1 and T2 given that
they have the gene is 0.72
a. Are T1 and T2 conditionally independent given G?
b. Are T1 and T2 conditionally independent given GC?
c. What is P(T1)? What is P(T2)?
d. Are T1 and T2 independent?

13. [Coding] After the Ebola outbreak of 2015 there was an urgent need to learn more about the
virus. You have been asked to uncover how a particular group of bat genes impact an important
trait: whether the bat can carry Ebola. Nobody knows the underlying mechanism – it is up to
you to hypothesize what is going on. For 100,000 independently sampled bats you have
collected data of whether or not five genes are expressed, and whether or not the bat can carry
Ebola1. If a gene is expressed it can affect both the probability of other genes being expressed
and the probability of the trait being expressed. You can find the data in a file called “[Link]”.
Each row in the file corresponds to one bat and has 6 Booleans:
• Boolean 1: Whether the 1st gene is expressed in the bat (G1)
• Boolean 2: Whether the 2nd gene is expressed in the bat (G2)
…
• Boolean 5: Whether the 5th gene is expressed in the bat (G5)
• Boolean 6: Whether the trait is expressed in the bat, eg the bat can carry Ebola (T).
Write a program to analyze the data you have collected. Report the following:
a. What is the probability of the trait being expressed P(T)?
b. For each gene i calculate and report P(Gi).

1Humane note: bats can carry Ebola, but it causes them no harm. No fake bats were hurt in the
making of this problem. Why are bats immune to the harmful effects? Open question!
 –5–

c. For each gene i decide whether or not you think that is would be reasonable to assume that
Gi is independent of T. Support your argument with numbers. Remember that our
probabilities are based on 100,000 bats, not infinite bats, and are therefore just estimates
of the true probabilities.
d. For each gene i that is not assumed to be independent of T, calculate P(T | Gi).
e. Give your best interpretation of the results from (a) to (d).
f. For extra credit try and find conditional independence relationships between the genes and
the trait. Incorporate this information to improve your hypothesis of how the five genes
relate to whether or not a bat can carry Ebola.