CS 70 Discrete Mathematics and Probability TheoryFall 2011 Rao HW 9Due October 28, 11:59pmYour answer to each question should be on its own sheet of paper, and submit it to the drop box for thatquestion (i.e., your answer to question i goes into CS 70 drop box i). Print your name, discussion section,and question number on every sheet of paper.1. (16 pts.) A Very Small Example of HashingSuppose we hash three objects randomly into a table with three (labelled) entries. We are interested in thelengths of the linked lists at the three table entries.(a) List all the outcomes in the sample space of the experiment. How many of them are there?(b) Let X be the length of the linked list at entry 1 of the table. Write down X explicitly as a function onthe sample space mapping to the real line (either in a figure as in class or as a list). Compute and plotthe distribution and expectation of X.(c) Let Y be the length of the longest linked list among all three. Write down Y explicitly as a function onthe sample space mapping to the real line. Compute and plot the distribution and expectation of Y .(d) Is the expectation of X larger than, equal to or smaller than that of Y ?(e) Compute the distribution of X for the general case when m objects are hashed randomly into a table ofsize n, i.e. give an expression for the probability that X takes on each value in its range. (Computingthe distribution of Y for the general case is not so easy, so we won’t ask you to do it!)2. (17 pts.) Random Variables and Their DistributionsA biased coin with probability p landing Heads is flipped 4 times.(a) List the outcomes in the sample space and assign probabilities to them.(b) Let X be the total number of Heads in the four flips. Draw a Venn diagram showing the five eventsX = 0, X = 1,X = 2, X = 3, X = 4 as well as the sample space and the sample points.(c) Are the events X = 1 and X = 2 disjoint? Are they independent?(d) Compute the distribution and the expectation of X.(e) Let E be the event that the first flip is a Heads. Are the events X = 0 and E disjoint? Are theyindependent? How about the events X = 2 and E? Disjoint? Independent?3. (15 pts.) Packets Over the Internetn packets are sent over the Internet (n even). Consider the following probability models for the packet lossprocess:(a) Each packet is routed over a different path and is lost independently with probability p.(b) All n packets are routed along the same path, and with probability p, one of the links along the pathfails and all n packets are lost. Otherwise all packets are received.CS 70, Fall 2011, HW 9 1(c) The n packets are divided into 2 groups of n/2 packets, and each group is routed along a different pathand lost with probability p. Losses of different groups are independent events.In each of the three models, compute the distribution and the expectation of the number of packet losses.For n = 6 and p = 0.3, plot the distribution in each of the three cases. Does the distribution depend on theprobability model? Which of the three routing protocols do you prefer?4. (17 pts.) Family PlanningMr and Mrs Brown decide to continue having children until they either have their first boy or until they havefive children. Assume that each child is equally likely to be a boy or a girl, independent of all other children,and that there are no multiple births. Let B and G denote the numbers of boys and girls respectively that theBrowns have.(a) Write down the sample space together with the probability of each sample point.(b) Compute and plot the distributions of the random variables B and G.(c) Compute the expectations of B and G using a direct calculation.5. (15 pts.) GamesHere’s a game. Alice and Bob will each roll a fair, six-sided die. If Alice’s die comes up with a numberhigher than Bob’s, Alice wins $3 from Bob. If Bob’s number comes up higher, or if they tie, Bob wins $2from Alice. Is this game a good deal for Alice? Explain.(Hint: Define a random variable and compute an expectation.)6. (20 pts.) Expectations(a) In class, we define the expectation of a random variable X asE(X) :=∑ω ∈ΩX(ω )Pr[ω ],where Ω is the sample space. In the notes, the expectation is defined to beE(X) :=∑a∈AaPr[X = a],where A is the range of values that X can take on. Show that the two definitions are equivalent.(b) Given a random variable X defined on a sample space Ω, Y = X2is also a random variable defined onΩ. Why?(c) Show, from the definition of the expectation, thatE(X2) =∑a∈Aa2Pr[X = a].(You can start with the definition in class or the definition in the notes, since you have already shownin part (a) that they are equivalent.)(d) Generalize the result in part (c) to give an expression for E( f (X )), where f is an arbitrary functionfrom ℜ to ℜ. You can give your answer without proof.CS 70, Fall 2011, HW 9
View Full Document
Unlocking...