Massachusetts Institute of Technology Handout 6 Mathematics for Computer Science August 6, 2002 Prof. Charles E. Leiserson

Optional Homework 2

Problem 1. Two coins are given. One is fair (the probability of heads is 1/2), and the other is biased with a 2/3 probability of heads. One of the coins is tossed once, resulting in heads. The other is tossed three times, resulting in two heads. Which coin is more likely to be the biased one?

Problem 2. Anu and Bing play a game. Anu picks a 3-pattern from the 8 possible 3patterns of coin flips:

\begin{matrix}HHH & HHT & HT H & HT T \\ T HH & T HT & T T H & T T T \end{matrix}

Then, Bing picks a different 3-pattern. They now flip a fair coin as many times as it takes for one of their 3-patterns to show up as consecutive coin tosses, the winner being the person whose pattern shows up first. For example, if Anu picks HHT and Bing picks T T H, then Anu would win if the sequence of coin flips were H T H T H H \underline{H} \underline{H} \underline{T}.

Show that Bing, by picking second, can always win this game. What is the highest probability of winning that Bing can obtain if Anu makes the best-possible first choice?

Problem 3. A poker hand is made up of 5 cards from an ordinary 52-card deck. Give formulas for the probabilities of each of the following hands:

• royal flush

• straight flush

• four of a kind

• full house

• flush

• straight

• three-of-a-kind

• two pair

• one pair

Briefly explain each of your formulas, and calculate numerical values.

Problem 4. In the game of contract bridge, an ordinary 52-card deck is dealt to four players, each receiving 13 cards. Players sitting opposite each other are teammates. After the bidding phase of the game, the player winning the bid becomes the declarer and his partner becomes the dummy; the players on the other team become defenders. The defender sometimes has an easier time making his contract if a given suit is split evenly between the defenders.

(a) Compute the probability that if the defenders have five cards of a suit between them, the cards are split 3 : 2 or 2 : 3 rather than more unevenly.

(b) Compute the probability that if the defenders have four cards of a suit between them, the cards are split 2 : 2 rather than more unevenly.