Detailed answers.
Problem 34.\" A spider and a y move along a straight line. At each second, the y moves a unit step to the right or to the left with equal probability p, and stays where it is with probability 1 in The spider always takes a unit step in the direction of the y. The spider and the y start D units apart, where D is a random variable taking positive integer values with a given PMF. If the spider lands on top of the y, it's the end. What is the expected value of the time it takes for this to happen? Problem 38. Alice passes through four traffic lights on her way to work, and each light is equally likely to be green or red. independent of the others. (a) What is the PMF, the mean, and the variance of the number of red lights that Alice encounters? (b) Suppose that each red light delays Alice by exactly two minutes. What is the variance of Alice's commuting time? Problem 39. Each morning, Hungry Harry eats some eggs. On any given morning. the number of eggs he eats is equally likely to be 1. 2, 3. 4, 5, or 6, independent of Problems 133 what he has done in the past. Let X be the number of eggs that Harry eats in 10 days. Find the mean and variance of X. Problem 40. A particular professor is known for his arbitrary grading policies. Each paper receives a grade from the set {A, A-, B+. B, B-, C+}, with equal probability, independent of other papers. How many papers do you expect to hand in before you receive each possible grade at least once? Problem 41. You drive to work 5 days a week for a full year (50 weeks), and with probability p = 0.02 you get a traffic ticket on any given day, independent of other days. Let X be the total number of tickets you get in the year. (a) What is the probability that the number of tickets you get is exactly equal to the expected value of X? (b) Calculate approximately the probability in (a) using a Poisson approximation. (c) Any one of the tickets is $10 or $20 or $50 with respective probabilities 0.5, 0.3, and 0.2, and independent of other tickets. Find the mean and the variance of the amount of money you pay in traffic tickets during the year. (d) Suppose you don't know the probability p of getting a ticket. but you got 5 tickets during the year, and you estimate p by the sample mean 5 p = 250 = 0.02. What is the range of possible values of p assuming that the difference between p and the sample mean p is within 5 times the standard deviation of the sample mean? Problem 42. Computational problem. Here is a probabilistic method for com- puting the area of a given subset S of the unit square. The method uses a sequence of independent random selections of points in the unit square [0, 1] x [0, 1], according to a uniform probability law. If the ith point belongs to the subset S the value of a random variable X, is set to 1, and otherwise it is set to 0. Let X1, X2, .. . be the sequence of random variables thus defined, and for any n, let Sn = XitX2 + ... + Xn n (a) Show that E[S,] is equal to the area of the subset S. and that var(S,) diminishes to 0 as n increases. (b) Show that to calculate Sn. it is sufficient to know S,-, and Xn, so the past values of Xk, k = 1, . ..,n - 1, do not need to be remembered. Give a formula. (c) Write a computer program to generate S, for n = 1,2,... ,10000, using the computer's random number generator, for the case where the subset S is the circle inscribed within the unit square. How can you use your program to measure experimentally the value of ? (d) Use a similar computer program to calculate approximately the area of the set of all (r. y) that lie within the unit square and satisfy 0 _ cos ur + sin my $ 1.Problem 46.* Entropy and uncertainty. Consider a random variable X that can take n values. I1 . . ..,In, with corresponding probabilities p1, . . . . Pn. The entropy of X is defined to be H(X) = - p; log p.. i= 1 136 Discrete Random Variables Chap. 2 (All logarithms in this problem are with respect to base two.) The entropy H(X) provides a measure of the uncertainty about the value of X. To get a sense of this. note that H(X) 2 0 and that H(X) is very close to 0 when X is "nearly deterministic," i.e., takes one of its possible values with probability very dose to 1 (since we have plog p = 0 if either p = 0 or p = 1). The notion of entropy is fundamental in information theory, which originated with C. Shannon's famous work and is described in many specialized textbooks. For example. it can be shown that H(X) is a lower bound to the average number of yes-no questions (such as "is X = x1?" or "is X p: log qi. with equality if and only if p, = q for all i. As a special case, show that H(X) 0. which holds with equality if and only if a = 1; here In a stands for the natural logarithm. (b) Let X and Y be random variables taking a finite number of values, and having joint PMF px. (r, y). Define 1(X, Y) = _ _px.x (x, y) log PX.Y (I. y) px (z)py (y) Show that /(X, Y) 2 0, and that /(X. Y) = 0 if and only if X and Y are independent. (c) Show that I(X. Y) = H(X) + H(Y) - H(X, Y). where H(X. Y) = - _ _px x (z. y) logpx.y(z.y). H(X) = - px (x) logpx(1). H(Y) = -_py(y) log py(y). (d) Show that I(X. Y) = H(X) - H(X |Y). where H(XIY) = - _pr(y) _PXIY (Ily) log pxx (z ly). [Note that H(X | Y) may be viewed as the conditional entropy of X given Y, that is. the entropy of the conditional distribution of X. given that Y = y, averaged Problems 137 over all possible values y. Thus. the quantity I(X, Y) = H(X) - H(X | Y) is the reduction in the entropy (uncertainty) on X, when Y becomes known. It can be therefore interpreted as the information about X that is conveyed by Y. and is called the mutual information of X and Y.]Problem 16. Let X be a random variable with PMF px (I) = x /a. if I= -3, -2, -1, 0, 1,2,3, otherwise. (a) Find a and E[X]. (b) What is the PMF of the random variable Z = (X - E[X])? ? (c) Using the result from part (b), find the variance of X. (d) Find the variance of X using the formula var(X ) = ). (1 - E[X]) px (x). Problem 17. A city's temperature is modeled as a random variable with mean and standard deviation both equal to 10 degrees Celsius. A day is described as "normal" if the temperature during that day ranges within one standard deviation from the mean. What would be the temperature range for a normal day if temperature were expressed in degrees Fahrenheit? Problem 18. Let a and b be positive integers with a
