CS 70 Discrete Mathematics and Probability Theory
Spring 2019 Ayazifar and 2 Solutions
PRINT Your Name: Oski Bear SIGN Your Name: OS K I
Do not turn this page until your instructor tells you to do so.
Copyright By PowCoder代写 加微信 powcoder
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!
Answer: Note that the answers provide explanations for your understanding, even though no such justifica- tion was required
1. (P =⇒ (R∧¬R)) =⇒ ¬P
Answer: True. This is the form of a proof by contradiction of ¬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)))
Answer: False. Just because a particular i makes P(i) ∧ P(i + 1) true does not mean P(i) is true for every i. Consider the predicate P such that P(0), P(4) and P(5) are true, and false everywhere else. Then this predicate satisfies the left hand side of the implication but not the right hand side.
3. LetRbetherealnumbers,(∀x,y∈R)((x
Answer: p(1 − p)(i− j−1). One needs a success and (i − j − 1) failures to get from j to i.
5. Given independent X,Y ∼ Bin(n, p), what is Pr[X +Y = i]?
Answer: 2npi(1−p)2n−i. X+Y ∼Bin(2n,p) i
6. Consider a random variable X where E[X4] = 5, give as good upper bound on Pr[X ≥ 5] as you can. Answer: 1 .
20 2 5 4 20
Pr[X ≥5]=Pr[X4 ≥54]≤ E[X4] = 1 . 54 53
The random variable X = 5 with probability 1 125
and 0 demonstrates that this is the best possible bound.
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. 5
1. What is the expected value of X?
Answer: 1. One can use linearity of expectation: X1 +···Xn, where X1 indicates that ball i falls into bin 1 and E[X1] = 1/n.
2. Use Markov’s inequality to give an upper bound on Pr[X ≥ k]. Answer: 1/k. Markov says Pr[X ≥ k] ≤ E[X].
3. What is the variance of X?
Answer: 1 − 1n .
Take X = X1 + . . . + Xn where Xi is an indicator random variable for choosing ball i choosing bin 1.
From the fact that each Xi has variance 1 (1 − 1 ) and the fact that Xi s are independent from each other, 11 nn
wegetn n 1−n =(1−1/n).
4. Use Chebyshev’s inequality to give an upper bound on Pr[X ≥ k].
Answer: n . From Chebyshev’s, we know that
Pr[|X −1| ≥ k−1] ≤ 1−1/n (k−1)2
Furthermore, we know Pr[|X −1| ≥ k−1] = Pr[X ≥ k∪X ≤ 2−k] ≥ 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]?
Answer: nn−i 1 i+ j 1 − 2 n−i− j . There are n ways to choose which balls will go into the first
bin, and n−i ways to pick which balls go into the second bin. After picking, the probability that the i j
balls actually end up in the first bin is 1 , the probability that the j balls end up in the second bin is 1 , ni nj
and the probability that the other n−i− j balls end up in not the first and second bins is 1− 2n−i−j. n
6. What is Pr[X = i|Y = j]?
Answer: n−j 1 in−2n−i−j. We can pretend the second bin doesn’t exist, since it will have j
balls already. Then, there are n − j balls left, thrown into n − 1 bins.
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?
Answer: e−5 55 . 5!
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 ) = λ )
Answer: 200 hours. For the X ∼ Poisson(λ), the variance is λ. If we observe n samples X1,X2,…,Xn,
we can estimate λ as Y := X1+X2+···+Xn . Then we have E[Y] = λ and Var(Y) = λ . nn
ChebyshevsaysPr[|Y−μ|≥t]≤Var(Y). Wewishthisprobabilitytobelessthan 1,andwehave t 20
t = 1. Plugging in, we get 10 ≤ 1 . Or n = 200. n 20
That’s a lot of time to eat chicken nuggets.
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).
2 Y−λ Answer: 40 hours. Or more precisely ⌈10 · 1.96 ⌉ = 39 hours. We assume now that √
normal 0, 1 distribution. From the table in the back of the exam, we see that Y−λ
factthatλ ≤10yields10·1.962.
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?
Answer: 2.1=∞cx−3=−cx−2|∞=c,whichimpliesc=2. 1212
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?
Answer: 4. 11cxydxdy= c =1,soc=4.
Pr −1.96 ≤ λ/n ≤ 1.96 ≈ 0.95
Therefore, the width of the confidence interval is 2 · 1.96 · λ /n. Setting this equal to 2 and using the
(b) What is Pr[|X −Y| ≤ 1/2]?
Answer: 41 . The density function is symmetric around the line y = x, so we will only consider
the part above y = x. Moreover, the integration is a bit easier if one considers the complement or
when |X −Y| ≥ 1/2. This corresponds the 2 1 1/2−y 4xydxdy, where the factor of 2 is where 1/2 0
we use the symmetry. Integrating gives 7 . Taking the complement yields 41 . 48 48
9. This is Absolutely Not Normal! 6 points each part, 12 points total.
Consider a standard Gaussian random variable Z whose PDF is
∀z∈R, fZ(z)= √ e 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.
Answer: We’llsolvethispartintwoways.
MethodI Forx<0,theCDFofX is
For x ≥ 0 the CDF is given by
FX(x)=Pr[X ≤x]=0.
FX (x) = Pr (−x ≤ Z ≤ x) = Φ(x) − Φ(−x)
=Φ(x)−[1−Φ(x)]
Φ(−x) = 2Φ(x)−1,
where Φ(x) =
Method II This method is longer for the problem at hand, but it uses mixture probabilities and the
fZ(z)dz denotes the CDF of the standard Gaussian random variable. Law of Total Probability, so it’s worth describing. In particular, we recognize that
Using the Law of Total Probability, we can write the PDF for X as a mixture PDF—namely, fX(x) = fX|Z≥0(x)Pr(Z ≥ 0)+ fX|Z<0(x)Pr(Z < 0).
We note that Pr(Z ≥ 0) = Pr(Z < 0) = 1/2. We also recognize that for x < 0, it must be the case that fX (x) = 0. However, for x ≥ 0, we have:
π0 Let s = x2/2, so that ds = xdx. We then have
which leads to
fX(x)=fX|Z≥0(x)= fX,Z≥0(x) Pr(Z ≥ 0)
Therefore,
= fZ(x) Pr(Z ≥ 0)
2 −x2/2 =e.
2 E(X)= .
(b) Determine a reasonably simple expression for E(X), the mean of X. Place your final answer in the box below.
Answer: The mean of X is given by
x fX(x)dx 2 ∞ −x2/2
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.
Answer: If K and L arrive in Saint Petersburg randomly then their PMFs are uniform over the set {1,2,3,4,5}. Since K and L are independent, the joint PMF will be the uniform PMF over the range k ∈ {1,2,3,4,5} and l ∈ {1,2,3,4,5}:
5 if l ∈ {1,2,3,4,5}
if k ∈ {1,2,3,4,5} 0 otherwise,
551 E[|K−L|] = ∑∑ 25 |k−l|
5 8 6 4 2
= 0 25 +1 25 +2 25 +3 25 +4 25
pK,L(k,l)=
We determine the mean wait time E [|K − L|] in two different ways:
Method II Let’s define three mutually exclusive, collectively exhaustive events K > L, K < L, and K = L,
which are depicted in the figure below:
1 25 0
0 otherwise. if k,l ∈ {1,2,3,4,5}
otherwise.
It’s clear from the sample space that
P(K > L) = P(K < L) = 10/25 = 2/5 and
P(K = L) = 5/25 = 1/5.
We can then compute the expe
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com