CS 70 Spring 2019
PRINT Your Name:
SIGN Your Name:
PRINT Your Student ID:
PRINT Your Exam Room:
Name of the person sitting to your left:
Discrete Mathematics and Probability Theory Ayazifar and Rao
,
Final Exam
(last)
(first)
Name of the person sitting to your right:
• After the exam starts, please write your student ID (or name) on every odd page (we will remove the staple when scanning your exam).
• We will not grade anything outside of the space provided for a problem.
• The questions vary in difficulty, so if you get stuck on any question, it might help to leave it and try another one.
• If there is a box provided, put your answer in it. If not, use the space provided for your proof or argument.
• You may consult only three sides of notes. Apart from that, you may not look at books, notes, etc. Calculators, phones, computers, and other electronic devices are NOT permitted.
• There are 21 single sided pages including the cover sheet on the exam. Notify a proctor immediately if a page is missing.
• You may, without proof, use theorems and lemmas that were proven in the notes and/or in lecture.
• You have 170 minutes: there are 12 questions (with 66 parts) on this exam worth a total of 222 points.
• Graphs are simple and undirected unless we say otherwise.
Do not turn this page until your instructor tells you to do so.
CS 70, Spring 2019, Final Exam 1
SID:
1. TRUE or FALSE? 2 points each part, 26 total.
For each of the questions below, answer TRUE or FALSE. No need to justify answer.
Please fill in the appropriate bubble!
1. (P =⇒ (R∧¬R)) =⇒ ¬P
2. Let Z be the integers, and P(i) be a predicate on integers, (P(0)∧((∃i ∈ Z) P(i)∧P(i+1)) =⇒ (∀i ∈ Z) ((i ≥ 0) =⇒ P(i)))
3. LetRbetherealnumbers,(∀x,y∈R)((x
5. Given independent X,Y ∼ Bin(n, p), what is Pr[X +Y = i]?
6. Consider a random variable X where E[X4] = 5, give as good upper bound on Pr[X ≥ 5] as you can.
9
SID:
6. Concepts through balls in bins. 3 points each part, 18 points total.
Consider throwing n balls into n bins uniformly at random. Let X be the number of balls in the first bin.
1. What is the expected value of X?
2. Use Markov’s inequality to give an upper bound on Pr[X ≥ k].
3. What is the variance of X?
4. Use Chebyshev’s inequality to give an upper bound on Pr[X ≥ k].
5. Now let Y be the number of balls in the second bin. What the joint distribution of X,Y, i.e., what is Pr[X = i,Y = j]?
6. What is Pr[X = i|Y = j]?
10
SID:
7. Lots of chicken nuggets. 5 points each part, 15 points total.
We will model the number of customers going into Emaan’s and Jonathan’s favorite McDonalds within an hour as a random Poisson variable, i.e., X ∼ Poisson(λ ).
1. Giventhatλ=5,whatistheprobabilitythat5peoplecomeinduringthehourthatEmaanandJonathan are eating chicken nuggets?
2. If λ is unknown but is definitely at most 10, how many hours do Emaan and Jonathan need to be at McDonalds to be able to construct a 95% confidence interval for λ that is of width 2. (You should use Chebyshev’s inequality here. Recall for X ∼ Poisson(λ ) that Var(X ) = λ )
3. Solve the previous problem but now assume you can use the Central Limit Theorem. (Hint: You may want to use the table in the back of the exam).
11
SID:
8. Not so dense density functions. 5 points each (sub)part, 15 points total.
1. Consider a continuous random variable whose probability density function is cx−3 for x ≥ 1, and 0 outside this range. What is c?
2. Consider random variables X , Y with joint density function f (x, y) = cxy for x, y ∈ [0, 1], and 0 outside that range.
(a) What is c?
(b) What is Pr[|X −Y| ≤ 1/2]?
12
SID:
9. This is Absolutely Not Normal! 6 points each part, 12 points total.
Consider a standard Gaussian random variable Z whose PDF is
1 −z2/2
Define another random variable X such that X = |Z|.
(a) Determine a reasonably simple expression for fX(x), the PDF of X. It may be helpful to draw a plot.
Place your final expression in the box below.
∀z∈R, fZ(z)= √ e 2π
.
(b) Determine a reasonably simple expression for E(X), the mean of X. Place your final answer in the box below.
13
SID:
10. Joint Distributions with Kyle and Lara. 6 points each part, 18 points total.
Kyle and Lara arrive in Saint Petersburg randomly and independently, on any one of the first five (5) days of May 2019. Let K be the day that Kyle arrives, and let L be the day that Lara arrives. (Note that K and L will both be in {1,2,3,4,5}).
Whoever arrives first must wait for the other to arrive before going on any kind of excursion in the city.
(a) DetermineE[|K−L|],theexpectedwaittimeindays.
14
SID:
(b) Given that Kyle arrives at least a day later than Lara:
(i) Determine the conditional probability mass function for Kyle’s arrival day, pK(K>L)(k)
(ii) Provide a well-labeled plot of pK(K>L)(k).
15
SID:
11. Markov Chains 3 points for each part, 18 points total.
Consider the two Markov Chains represented by the following state transition diagrams.
Markov Chain I
0
Markov Chain II
0
pp p p 1−p1−p
1−p 1−p
1−p 1−p1−p
31
21
p
pp
2
(a) For Markov Chain I:
(i) Do the n-step transition probabilities—defined by ri j (n) = Pr Xn = jX0 = i —converge as n →
∞?
hConverges
hDoes not converge (ii) If so, determine the corresponding limit to which each transition probability converges, and ex- plain whether and why the limit depends on the initial state (i.e., the state at which the walker was stationed initially). If you assert that the transitional probabilities do not converge, explain why
no limit exists.
16
SID:
Markov Chain I
Markov Chain II
0
0
pp p p 1−p1−p
1−p 1−p
1−p 1−p1−p
31
21
p
pp
2
(b) For Markov Chain II:
(i) Do the n-step transition probabilities—defined by ri j (n) = Pr Xn = jX0 = i —converge as n →
∞?
hConverges
hDoes not converge (ii) If so, determine the corresponding limit to which each transition probability converges, and ex- plain whether and why the limit depends on the initial state (i.e., the state at which the walker was stationed initially). If you assert that the transitional probabilities do not converge, explain why
no limit exists.
17
SID:
(c) ( Points) Consider Markov Chain I above. Determine t0∗, the mean recurrence time for State 0.
The mean recurrence time for a state s is the expected number of steps up to the first return to state s, starting from state s. In other words,
In particular,
ts∗ =Emin(n≥1suchthatXn =s)|X0 =s. ts∗ =1+∑psiti,
i
where ti, which denotes the mean first passage time from State i to State s, is given by
ti =Emin(n≥0suchthatXn =s)|X0 =i.
(i) Write the system of equations that you would solve in the box below. Use t0∗, t1, t2, and p.
(ii) Set p to 1/2 and write your final answer for the value of t0∗ in the box below.
18
SID:
12. Derive Magic from a Uniform PDF. 5 points per part. 15 points.
A random-number generator produces sample values of a continuous random variable U that is uniformly distributed between 0 and 1.
In this problem you’ll explore a method that uses the generated values of U to produce another random variable X that follows a desired probability law distinct from the uniform.
(a) Let g : R → [0, 1] be a function that satisfies all the properties of a CDF. Furthermore, assume that g is invertible, i.e. for every y ∈ (0, 1) there exists a unique x ∈ R such that g(x) = y.
Let random variable X be given by X = g−1(U), where g−1 denotes the inverse of g. Prove that the CDF of X is FX(x) = g(x).
19
SID:
(b) A random variable X follows a double-exponential PDF given by ∀x∈R, fX(x)= λ e−λ|x|,
2
where λ > 0 is a fixed parameter.
Using the random-number generator described above (which samples U ), we want to generate sample
values of X . Derive the explicit function that expresses X in terms of U . In other words, determine the expression on the right-hand side of
X = g−1(U).
To do this, you must first determine the function g. From part (a) you know that g(x) = FX (x), so you must first determine FX (x). It might help you to sketch the PDF of X first. Place your expression for g−1 in the box below.
20
SID:
Introduction to Probability, 2nd Ed, by D. Bertsekas and J. Tsitsiklis, Athena Scientific, 2008
21