CS 70 Discrete Mathematics for CSSpring 2005 Clancy/Wagner HW 11Due Thursday, April 21Coverage: This assignment involves topics from the lecture of April 14, and from Rosen section 5.3.Administrative reminders: We will accept only unformatted text files or PDF files for homework sub-mission. Include your name, login name, section number, and partner list in your submission. Give thecommand submit hw11 to submit your solution to this assignment.Homework exercises:1. (10 pts.) Quadruply-repeated onesWe say that a string of bits has k quadruply-repeated ones if there are k positions where four consec-utive 1’s appear in a row. For example, the string 0100111110 has two quadruply-repeated ones.What is the expected number of quadruply-repeated ones in a random n-bit string, when n ≥ 3 and alln-bit strings are equally likely? Justify your answer.2. (12 pts.) Stakes well doneTwo players, Alice and Bob, each stake 32 pistoles on a three-point, winner-take-all game of chance.The game is played in rounds; at each round, one of the two players gains a point and the other gainsnone. Normally the first player to reach 3 points would win the 64 pistoles. However, it starts to rainduring the game, and play is suspended at a point where Alice has 2 points and Bob has 1 point. Aliceand Bob have to figure out how to split the money.You should assume that Alice and Bob are evenly matched, so that in each round Alice and Bob eachhave a 50% chance of winning the round. Assume also that Alice’s share should be proportionalto the maximum that she should be willing to pay to continue to the game from the point where itwas interrupted. Economics tells us1that the maximum Alice should be willing to pay is exactly theconditional expected value of her winnings (specifically, her winnings if the game were continued tothe end from this point). The same goes for Bob.Calculate a fair way to distribute the 64 pistoles using this notion of fairness. How many pistoles doesAlice receive? Bob?1This is a little bit of a simplification. We’re assuming here that Alice’s utility function is the identity function. That assumptionmight or might not be perfect in practice, but it’s probably a reasonable first approximation for low-stakes games.CS 70, Spring 2005, HW 11 13. (10 pts.) A flawed shuffleConsider the following bad method for “shuffling” (i.e. randomly permuting the elements of) a 52-element array A.(a) Initialize an array newA to contain 52 “empty” indicators.(b) For k = 0 to 51, do the following:i. Repeatedly generate a random integer j between 0 and 51 until A[ j] isn’t empty.ii. Copy A[ j] to newA[k], and set A[ j] to “empty”.(c) Copy newA, which now contains the shuffled elements, back to A.Determine the expected number of random integers j that will be generated to produce newA[k].4. (12 pts.) Elevator analysisWhen Evans Hall was first built in the 1950’s, its elevator system was more primitive than it is now.There were two elevators, which moved continuously from the top floor to the basement and back.On each floor was a single button that, if pressed, would cause the next elevator passing the floor ineither direction to stop.One of the mathematics faculty from that era, named Pat, decided to analyze the elevator systemfrom an office on the eighth floor. (Recall that Evans has floors 1-10, as well as a ground floor anda basement floor). Initially, Pat thought that the probability of an elevator going up would be 9/11,since there are two floors above the eighth and the total distance from top to bottom is 11 floors. Thedata suggested, however, that the probability that the responding elevator was going up was actuallycloser to 2/3.Find the actual probability that an elevator responding to a call on the eighth floor of Evans is goingup, and explain how you got that figure. Assume there are two independent elevators that run as justdescribed.5. (16 pts.) The martingaleConsider a fair game in a casino: on each play, you may stake any amount $S; you win or lose withprobability12each (all plays being independent); if you win you get your stake back plus $S; if youlose you lose your stake.(a) What is the expected number of plays before your first win (including the play on which youwin)?(b) The following gambling strategy, known as the “martingale,” was popular in European casinosin the 18th century: on the first play, stake $1; on the second play $2; on the third play $4; onthe kth play $2k−1. Stop (and leave the casino!) when you first win.Show that, if you follow the martingale strategy, and assuming you have unlimited funds avail-able, you will leave the casino $1 richer with probability 1. [Maybe this is why the strategy isbanned in most modern casinos.](c) To discover the catch in this seemingly infallible strategy, let X be the random variable thatmeasures your maximum loss before winning (i.e., the amount of money you have lost beforethe play on which you win). Show that E[X] = ∞. What does this imply about your ability toplay the martingale strategy in practice?(d) Colin and Diane enter the casino with $10 and $1,000,000 respectively. Both play the martingalestrategy (leaving the casino either when they first win, or when they lack sufficient funds to placethe next bet as required by the strategy). What is the probability that Colin wins? What is theprobability that Diane wins?CS 70, Spring 2005, HW 11
View Full Document
Unlocking...