CS5002 Discrete Structures Prof. Rachlin Spring 2022 March 30, 2022
Homework #8
Assigned: Wednesday March 30, 2022
Due: Tuesday April 5, 2022 @ 11:59pm ET/Boston −5%: Wednesday April 6, 2022 @ 11:59pm ET/Boston −10%: Thursday April 7, 2022 @ 11:59pm ET/Boston
Copyright By PowCoder代写 加微信 powcoder
Instructions:
• Homework is due on Tuesday at 11:59pm ET/Boston. Homeworks received up to 24 hours late (11:59pm ET on Wednesday) will be penalized 5 percent. Homeworks received up to 48 hours late (11:59pm ET on Thursday) will be penalized 10 percent. NO assignment will be accepted after 48 hours.
• We expect that you will study with friends and fellow students and you are welcome to verbally discuss the problems openly. However, your solution writeup should be the product of your own mind and expressed in your own words. The TAs and I will be available to answer specific questions or address speific points of confusion but we will not verify your answers prior to submission.
• Assignments should be typed using Word or LateX, or hand-written neatly. When submitting to gradescope be sure to indicate the page containing your answer to each problem, so that the TAs don’t have to search for your solution.
• To get full credit, explain your solution and show each step of the solution process! Simply writing down a correct answer will receive little or no credit. We don’t need your scratch work or draft solutions, only your final solution explaining your step-by-step reasoning. Recommendation: try to imagine you need to explain your solution to someone not in this class.
• If you think the TA made a clerical error in grading your assignment, you may submit a regrade request on Gradescope within 1 week of the publication of the grades. After 1 week of publication, ALL GRADES ARE FINAL.
Problem 1 [25 points (8,8,9)]: Conditional Probability
We are given 5 cards. 3 of the cards are black and they are numbered 1, 2, 3. The other two cards are red and they are numbered 1, 2.
We pick 2 random cards.
i. What is the probability that both cards are red?
Solution: The sample space S consists of all sets of 2 cards selected from the given 5 cards.
|S| = 5 = 10. 2
The event A = Both cards are red consists of all sets of two cards that are red, so |A| = 1. Therefore Pr[A] = 1/10
ii. What is the probability that both cards are red, if we know that at least one of them is red?
Solution: Here we have a new sample space S1 that consists of all sets of two cards with at least one red. Three sets include red1 and a black card, another three include red2 and a black card, and one includes both red cards. Thus |S1| = 7.
Therefore Pr [both red | S1] = 1/7
iii. What is the probability that both cards are red, if we know that one of them is red card
Solution: Here the new sample space S2 consists of all sets of 2 cards that include card red1.
There are 4 such sets, thus |S2| = 4 and therefore Pr[both red | S2] = 1/4.
Problem 2 [25 pts (10,15)]: At the carnival!
At a carnival, you are trying to throw four balls into 4 colored pots. The pots are colored red, blue, green, and pink. You will throw each of the four balls one at a time into these pots. Each ball lands in one of these pots or no pot at all. To make things more interesting, you must play this game blindfolded. The game pays out as follows
• $1 for each ball in the red pot
• $2 for each ball in the blue pot
• $3 for each ball in the green pot
• $4 for each ball in the pink pot
How many points do you expect to score:
i. Assuming every ball lands in some hole with equal probability? Solution: Simple approach (using indicator variables): Let R, B, G, P
ii. Assuming every ball has a 1 in 3 chance of not landing in any pot (and thus giving you no payout) but is otherwise equally likely to land in any pot?
The simplest approach (using indicator variables): We use the same events as above. Now E[R] = 23 ·4·E[R1] = 23 Then E[C] = 1·E[R]+2·E[B]+3·E[G]+4·E[P] = (1 · 32 + 2 · 23 + 3 · 32 + 4 · 32 ) = 32 · 10 = 6.66.
balls that land in the red, blue, green, or pink pots respectively. Consider the red pot. R = R1 +R2 +R3 +R4 where Ri indicates the ith ball landing in the red pot. E[R] = E[R1]+E[R2]+E[R3]+E[R4]=4·E[R1]=4·14 =1. Similarly,E[B]=E[G]=E[P]=1. Let C be the resulting payout. Then: E[C] = 1·E[R]+2·E[B]+3·E[G]+4·E[P] =
(1 + 2 + 3 + 4) = 10.
Problem 3 [25 pts (5 pts each)]: Probability
Let W(x) be the number of 1’s in the binary representation of x. For example, W(5) =
W(001012) = 2 because there are 2 1’s in the binary representation of 5. This is sometimes called the weight of the binary number. A deck of 32 cards has numbers 0 to 3110 written in 5-bit binary (000002 …111112 ).
1. What is the probability that the weight of a randomly chosen card is exactly 3? Solution: p(E) = |E|/|S| = 5/32 = 10/32
2. What is the probability that the weight of the card is 3 and the number on the card is odd, i.e., P (W = 3 ∩ Odd)?
Solution: P(W=3∩Odd)=P(W=3|Odd)P(Odd)=(42)·1 = 3 16 2 16
This follows from the fact that an odd number has a 1 in the lowest order bit and there are 4 ways to set 2 of the remaining 4 bits to 1. Also the deck contains exactly 16 even and 16
odd numbered cards, so the prior probability of picking an odd-numbered card is 21
3. Calculate P (Odd|W = 3), the probability that the card represents an odd number given that the weight of the number is 3.
Solution: Let T be the total weight of the three cards.
T = W1 + W2 + W3
By linearity of expectation: E[T ] = E[W1] + E[W2] + E[W3] = 3E[W1].
W1 =b1+b2+b3+b4+b5,wherebi isthebitvalue(0or1)atpositioni.
E[b1] = 12 · 0 + 12 · 1 = 12 because for the set of cards from 000002 to 111112, a 0 or a 1 is equally likely at each bit position.
So,E[W1]=E[b1]+…+E[b5]=5·E[b1]=5·12 =2.5.
Therefore E[T ] = 7.5
5. What is the probability that the total weight of the three cards you were dealt is equal to 13? You may leave your answer as a simple expression.
Solution: Thisrequiresbeingdealtthe31(111112)withweight5andanytwoofthe5=5
Solution: By Bayes’ theorem, P (Odd|W = 3) =
4. You are now dealt 3 random cards. What is the expected value for the total weight of your
three-card hand?
P (W =3|Odd)·P (Odd) 3 6 = 16 =
P(W=3) 10 10 32
cards with weight 4 (30, 29, 27, 23, 15). So P(W = 13) = (52) = 10 ≈ 0.002 (32) 4960
Problem 4 [25 pts (5,10,10)]: Medical Testing and Bayes
A certain virus is spreading rapidly through the population and doctors have come up with a new but imperfect test to determine if a patient is infected.
• 20 percent of the population is already infected with the virus. • 90 percent of infected patients test positive.
• 50 percent of healthy uninfected patients also test positive.
For this section, express your answer as a simple fraction or number.
1. What is the probability that a random person tests positive?
Solution: (See diagram below for a visual interpretation of these problems.)
Denote T =positive test, T ̄ =negative test, I=infected, and I ̄= not infected. ̄ ̄
P(T) = P(T|I)P(I) + P(T|I)P(I) = (0.9)(0.2) + (0.5)(0.8) = 0.18 + 0.40 = 0.58
2. What is the probability that a random person who tests positive actually has the virus?
Solution: P(I|T) = P(T|I)·P(I) = (0.90)(0.20) = .18 = 9 ≈ 0.31 P(T) 0.58 .58 29
3. Suppose an independent second test is performed on a patient that previously tested positive. This time, the test result is negative. Now what is the probability that the patient is infected with the virus?
Denote TT ̄ be the event of first testing positive and then negative for the virus. Then P (I|T T ̄) = P (T T ̄|I)P (I) = (0.9)(0.1)(0.2) = .018 =
P (T T ̄|I)P (I)+P (T T ̄|I ̄)P (I ̄) (0.9)(0.1)(0.2)+(0.5)(0.5)(0.8) .018+.200
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com