HW3 solution PDF

Preview

Summary

HW 3 Solutions...

Description

EE 351K Probability and Random Processes - Fall 2018

Homework 3

Gustavo de Veciana, Ezgi Tekgul, Kartik Patel Topics Covered: Counting, Discrete Random Variables and PMFs Homework and Exam Grading “Philosophy” Answering a question is not just about getting the right answer, but also about communicating how you got there. This means that you should carefully define your model and notation, and provide a step-by-step explanation on how you got to your answer. Communicating clearly also means your homework should be neat. Take pride in your work it will be appreciated, and you will get practice thinking clearly and communicating your approach and/or ideas. To encourage you to be neat, if your homework or exam solutions are sloppy you may NOT get full credit even if your answer is correct.

Q. 1 The English alphabet consists of 5 vowels (a, e, i, o, u) and 21 consonants. Vowels are written on blue colored beads, and consonants are written on green colored beads. In the following, the size of a subset refers to the number of items in the subset (i.e. the cardinality). 1. Determine the number of possible subsets of size 4. 2. The number of words (meaningful or meaningless) that can be made by arranging 8 beads in a circle bracelet, i.e. there is no first or last bead, but order matters. 3. The number of ways of choosing two nonempty subsets, with one subset containing only blue beads, and the other containing only green beads. 4. The number of ways of choosing two subsets, with one subset containing the bead with the vowel ’a’, and the other subset containing the bead with the consonant ’b’. 5. Number of ways of arranging the 5 green and 5 blue colored beads out of 26 beads in a line, with adjacent beads having different colors. Sol: 1. This is a combination problem, because there is no ordering of the selected beads. The number of possible subsets of size 4 is a combination of 4 out of 26 beads, which is:   26! 26 = = 14950. 4!(26 − 4)! 4 2. First we should choose 8 beads out of 26 beads, which is a combination problem and the number of ways is a combination of 8 out of 26 beads.   26! 26 = = 1562275. 8! (26 − 8)! 8 Then, we need to arrange them in a circle. Instead of arranging 8 beads in a line (which has 8! = 40320 ways), arranging in a circle only asks for different relative positions. In another word, if we arrange 8 beads sequentially, the position of the first bead does not make any difference to the final arrangement. Therefore, in total, we have 7! = 5040 ways to arrange 8 beads in a circle. So, the number of words that can be made by arranging 8 beads out of 26 beads in a circle bracelet is   26! 26 × 7! = × 7! = 7873866000. 8!(26 − 8)! 8 1

3. The number of ways of choosing one nonempty subset with all green beads is 221 − 1 = 2097151, because for each labelled green beads, it may choose to appear in the subset or not, which induces a total of 221 results for the subset. However, among them, we need to subtract the one configuration of subset being empty. Therefore, the total number of possible selections for each subset is 2097151. Due to the same reason, the number of ways of choosing one nonempty subset with all blue beads is 25 − 1 = 31. For two subsets separately choosing blue and green balls, the possible number of ways is the product of the number of possible selections in each subset, which gives us: (221 − 1) × (25 − 1) = 2097151 × 31 = 65011681. Notice here, the ordering of the subsets does not matter. 4. For all possible selection of the two subsets, we assume that bead a appears in subset A, and bead b appears in subset B. Now, the problem of counting the number of possible selection of the two subsets is equivalent to counting the number of arrangements for the rest 24 beads. For each one of the 24 beads, it can be in subset A, or in subset B, or neither. Therefore, the total number should be: 324 = 2.8243 × 1011 . 5. Arranging beads in a line with adjacent beads having different colors can only be in two modes: GBGB · ··GB or BGBG ·· · BG. Here G represents any green bead, and R represents any red bead. For the order of green beads there are 21x20x19x18x17 ways while for the order of blue beads there are 5x4x3x2x1 ways. Because there are two modes, number of ways arranging the 5 green and 5 blue colored beads is, 21! 5! × × 2 = 586051200. 16! 0!   Here is another way to solve this problem: out of 21 green beads, we should first choose 5 beads in 521 ways then we need to 5 arrange them, which is in 5! ways. For blue beads, we choose 5 beads out of 5 blue beads, in 5 and arrange them in 5! ways. And there is 2 cases as mentioned above. So, total number of ways arranging the 5 green and 5 blue colored beads is     5 21 × 5! × × 5! × 2 = 586051200. 5 5 Q. 2 Consider a city plan as in the below figure and suppose that John’s house is located at the origin. Suppose further that every weekday John leaves his home to go to work which located at the point (5,5), and at each intersection he can either go up or to the right, i.e. cannot go down or left. 1. How many paths are there from John’s house to his work?

Figure 1: City plan

2

2. Suppose every weekday John picks one of those paths at random and one of these days there is a road maintenance on a certain part of the path which is shown below with red dashed line, what is the probability that his path will traverse the entire maintenance section?

Figure 2: City plan with road maintenance

3. Suppose now that there is a lake in the middle of the city which is shown below as a shaded region. So, John cannot pass over this shaded region but he can use the surrounding paths to reach his work. For this case, how many paths are there from John’s house to his work?

Figure 3: City plan with lake

Sol: 1. In this problem, John needs to choose 5 right and 5 up in order to reach the point (5,5) from the point (0,0). So, we need to arrange these 5 right and 5 up (10 directions in total). If they were all different, there would be 10! ways to arrange them, however, here 5 rights are the same and also 5 ups are the same so their ordering doesn’t matter. So, there are 10! = 252 5!5! paths from John’s house to his work. 2. For traversing the entire maintenance section, first he should reach to the point (2,2), which is in2!2!4! ways then he traverse the red path from (2,2) to (4,4), which is the only possible way, and finally he should reach from the point (4,4) to (5,5), which is 2! ways. So, in total, there are in 1!1!

3



   2! 4! (1) = 12 2!2! 1!1!

12 = 0.048 ways. The probability that his path will traverse the entire maintenance section is252

3. The only blocked path here is from (0,0) to (3,3) and then from (3,3) to (5,5). So, if we subtract the number of ways that this path is followed from the all possible ways from (0,0) to (5,5), we find the number of paths from John’s house to work without passing over the lake. So, there are 6! 4! 10! − = 252 − 120 = 132 5!5! 3!3! 2!2! paths from John’s house to his work if there is a lake in the shaded region. Q. 3 Let X be a random variable denoting the voltage read by a voltmeter, which has a PMF over the integers given by:   x = 1, 2, 3,...   be−x+1 px (x) = bex+1 x = −1, −2, −3,...   0 otherwise 1. Determine the value of b such that the above expression is a valid PMF. ∞ i (Hint: Recall that geometric series are summable if a ∈ (0, 1), and ∑i=0 a =

1 (1−a) .)

2. Plot the PMF of the random variable X 3. Find P(X ∈ {−1, 1, 2}) 4. Find P(X is odd) Sol: ∞ 1. To be a valid PMF ∑i=−∞ px (x) = 1. So, ∞

−∞

∑ px (x) + ∑ i=1

∞

−∞

px (x) = 1 ∑ be−x+1 + i=1

i=−1

∞ We know that geometric series are summable if a ∈ (0, 1), and ∑i=0 ai = 1 equal to 2b 1−e−1 . Then,

bex+1 = 1

∑

1 (1−a) .

If we define a = e−1 , Equation 1 becomes

2b 1−e1 −1 = 1 b=

1−e−1 2

= 0.316.

2. Plot is in Figure 4. 3. P(X ∈ −1, 1, 2) = P(X = −1) + P(X = 1) + P(X = 2) = 0.316(e0 ) + 0.316(e0 ) + 0.316(e−1 ) = 0.7483. 4. ∞

∞

P(X is odd) =

∑

0.316ex+1 +

x=−1,−3,−5,···

= =

∑

0.316e−x+1

x=1,3,5,···

(2)(0.316)(e0 + e−2 + e−4 + ·· · ) ∞ 0.632 0.632 ∑ (e−2 )i = = 0.7309 1 − e−2 i=0 4

(1)

i=−1

0.35

0.3

PMF of X (pX(x))

0.25

0.2

0.15

0.1

0.05

0 -4

-3

-2

-1

0

1

2

3

4

X

Figure 4: PMF of the random variable X

Q. 4 In an IC chip factory which everyday produces 20 IC chips, one day an error has occurred in one of the manufacturing machines. This error results in a production of a defective chip with probability 0.4, independently of other IC chips. On this day, a technician tests the IC chips, one after another, to see if they are defective. 1. What is the probability that she has to test at least 5 IC chips to find the first (if any) defective one? 2. Find the probability that on this day the error in the manufacturing machine cause at least 5 defective IC chips to be produced. Sol: 1. We need to find P(X ≥ 5), where X is the number of IC circuits tested until the first (if any) defective one is found. This is the number of trials required to see the first failure, therefore, 20

P(5 ≤ X ≤ 20) + P({No defects found}) =

∑ (0.6)x−1 (0.4) + (0.6)20 = 0.1296. x=5

2. Let Y be the number of defective IC circuits. Each of the 20 IC circuits is either entered or not, thus Y is the number of successes in n = 20 Bernoulli trials. Hence, Y has Binomial distribution with n = 20 and p = 0.4. 20

  20 P(Y ≥ 5) = ∑ (0.4)y (0.6)20−y . y y=5 Q. 5 (Service capacity) Suppose you are the manager of a cloud computing company which is just getting started. Your company has only 10 customers each of which become active at any given time with probability 0.49. Given each active customer requires a server, what is the minimal number of servers that you should have available to ensure that the probability that you can serve all active customers is at least 0.99? Sol: Note that we can dene a RV X as the number of servers needed at a given time. X is distributed as a binomial. If we would 5

have available 10 servers, we would ensure serve all active customers with 100% probability. Since we are looking for the minimal number of servers that you should have available to ensure that the probability that you can serve all active customers is at least 0.99, we can observe that     10 10 P(X ≤ 8) = 1 − P(X = 9) − P(X = 10) = 1 − (0.49)10 ≈ 0.991. (0.49)9 (0.51) − 10 9 This ensures that by having 8 server the probability that you can serve all active customers is at least 0.99. Note that for 7 servers:       10 10 10 P(X ≤ 7) = 1 − P(X = 8) − P(X = 9) − P(X = 10) = 1 − (0.49)10 ≈ 0.952, (0.49)9 (0.51) − (0.49)8 (0.51)2 − 10 9 8 not ensuring a probability of at least 0.99. Therefore the minimal number of servers is 8. Q. 6 (Poisson approximation to the binomial) Let X Binomial(n, p) be a random variable representing the total number of successes out of n trials were each trial has probability of success p. The Law of Small Numbers (see your lecture notes) says that X can be approximated by a Poisson(np) RV if n is large and p is small. Suppose that a silicon chip can be subdivided into large number n = 10000 squares of unit area and the probability that a unit area has a defect is p = 10−5 . 1. Use the Poisson approximation to determine the likelihood a chip is produced without defects, i.e, the yield. 2. Suppose the next generation processors require increasing computational power. It is hard to make them run faster, so instead architects put more computational resources to exploit parallelism. Suppose that in doing so they double the area of the chip. Determine the likelihood that this new type of processor/chip is produced without defects, i.e, the yield. 3. Engineers have found ways to reduce the density of defects per unit area, i.e., to reduce p, through carefully controlled clean rooms, and processing of silicon. By how much would the defect density p need to be reduced for the new chips to have the same yield as the original ones?

Figure 5: (a) Chip with n squares of unit area (b) Chip with 2n squares of unit area Sol: Let the RV X denote the number of defects in the chip, modeled as X ∼ Poisson(10000 × 10−5 ) = Poisson(0.1). 1. The yield, i.e., probability of no defects, on the processor is then px (0) = e0.1 ≈ 0.9. 2. If the processors area is doubled, px (0) = e0.2 ≈ 0.82, that is a pretty huge change. 3. We need to solve e0.1 = e−20000p . Taking log in both sides: 20000p = 0.1 and therefore p = 5 × 10−6 , i.e.,half the probability. Note that all the computations used in this problem are much easier than if we were using Binomial instead of the Poisson approximation, which illustrates the usefulness of this approximation.

6

Extra Practice Problem (Not graded)

Q. 7 Suppose in a communication system, when a message is transmitted, the probability that the message will be received by the receiver is p. To be confident that a message is received at least once, a system transmits the message n times. 1. Assuming all transmissions are independent, what is the PMF of K, the number of times the message is received? 2. Assume p = 0.8. What is the minimum value of n such that the probability of receiving the message at least once is at least 0.95? Sol: 1. Each communication attempt is an independent Bernoulli trial with success probability p. The number of times K that the system receives a message is the number of successes in n Bernoulli trials and has the binomial PMF:   n  k n−k k = 0, 1, . . . n k p (1 − p) pK (k) = 0 otherwise 2. Let R denote the event that the message was received at least once. The event R has probability P[R] = P[B > 0] = 1 − P[B = 0] = 1 − (1 − p)n To ensure that P[R] ≥ 0.95 requires that n ≥ ln(0.05)/ ln(1 − p). For p = 0.8, we must have n ≥ 1.86. Thus, n = 2 messages would be necessary.

7...