Problem We consider a noisy communication link in which the message is encoded in to binary digits (0,1) (bits) before being transmitted. We will denote the length of the encoded message by n. Since the channel is noisy, the bits can get flipped; a 0 to 1 or a 1 to 0. We will assume that each bit is flipped independently with probability p. In order to be able to detect that the received message is in error, a simple method is to add a parity bit at the transmitter. There can two types of parity – even parity and odd parity. If even (odd) parity is used , the parity bit is set such that total number of 1s in the encoded message is even (odd). For the sake of this problem, we will only consider even parity. Here are a few examples 1) message: 0001 + parity bit: 1 –> encoded message: 00011 2) message: 0101 + parity bit: 0 –> encoded message: 01010 3) message: 0111 + parity bit: 1 –> encoded message: 01111 At the receiver, the parity bit is computed from the message bits. If the received parity bit does not match the computed parity bit, then the message is flagged to be in error. For example, if the received message 1 is 10011, then it is in error. 1. Suppose n = 7 and p = 0.1, what is the probability that the received message has errors which go undetected? 2. For general n and p, write down an expression (as a sum) for the probability that the received message has errors which go undetected. 1 2 Problem Consider the following program statement consisting of a while loop while ¬B do S Assume that the Boolean expression B takes the value true with probability p and the value false with probability q. Assume that the successive test on B are independent. 1. Find the probability that the loop will be executed k times. 2. Find the expected number of times the loop will be executed. 3. Considering the same above assumptions, suppose the loop is now changed to repeat S until B What is the expected number of times that the repeat loop will be executed? 3 Problem The following problem is called the coupon collector problem and has many applications in computer science. Consider a bag that contains N different types of coupons (say coupons numbered 1 . . . N . There are infinite number of each typ of coupon. Each time a coupon is drawn from the bag, it is independent of the previous selection and equally likely to be any of the N types. Since there are infinite numbers of each type, one can view this as sampling with replacement. Let T denote the random variable that denotes the number of coupons that needs to be collected until one obtains a complete set of atleast one of each type of coupon. Write a R simulation code to compute the E(T). Plot E(T) as for N = 10, 20, 30, 40, 50, 60. We will show in class that for large N , E(T ) can be approximated by N ⇥ log(N ) + 0.577 ⇥ N + 0.5. In the same plot show the theoretical value and summarize your observation regarding the accuracy of the approximation. 4 Problem The entire human genome can be considered to a long book broken into pages. Suppose that the number of mutations on a single page of this book has a Poisson distribution with parameter = 12 . For a given page, calculate that there are atleast 2 mutations on the page? 5 Problem This question deals with the Poisson process and is formulated in terms of a subway station. It could as well be formulated in terms of a networking problem. A subway station where different train lines intersect is like switch/router in the communication network with the different train lines corresponding to what are called Labelled Switched Paths (LSPs). As for the trains, you can think of them as packets or burst of packets. One can draw this analogy also in optical networks which forms the core of the Internet backbone. Two one-way subway lines, the A train line and the B train line, intersect at a transfer station, A trains and B trains arrive at the station according to independently operating Poisson processes with rates A = 3 trains/hr and B = 6 trains/hr. We assume that passenger boarding and un-boarding occurs almost instantaneously. At a random time, Bart, a prospective passenger, arrives at the station, awaiting an A train. Page 2 [Note that the superposition of two Poisson processes with rates rate 1 + 2 .] 1 and 2 is also a Poisson process with • What is the probability that the station handles exactly 9 trains during any given hour? • If an observer counts the number of trains that the station handles each hour, starting at 8:00 A.M. on Tuesday, what is the expected number of hours until he or she will first count exactly 9 trains during an hour that commences ”on the hour”? (e.g., 9: 00 A.M., 10: 00 A.M., 2: 00 P.M.) Page 3