Massachusetts Institute of Technology Handout 37 6.042J/18.062J: Mathematics for Computer Science April 14, 2000 Professors David Karger and Nancy Lynch

Mini-Quiz 10

1. Write your name:

2. (Rosen, Section 4.7, Exercise 1) Find the next largest permutation in lexicographic order after each of the following permutations.

(a) 1432

(b) 12453

(c) 6714235

(d) 54123

(e) 45231

(f) 31528764 Solution. 2134, 12534, 6714253, 54132, 45312, 31542678

□

Tutorial 10 Problems

Problem 1 In the O.J. Simpson trial, defense attorney Dershowitz observed that the fraction of wife batterers that murder their wives is 1/2000. Since the probability that a wife batterer would murder his wife is so low, Dershowitz argued that the fact that Simpson battered his wife, Nicole Brown Simpson, should be excluded from the evidence. We will develop a counter-argument to Dershowitz’, by conditioning the probability on the event that Mrs. Simpson is dead.

We have the following statistical information (all for 1994):

women  125M
married women  50M
wives battered by husband 3M
women murdered  6K
wives murdered by husband 1.5K

The number of battered wives includes those who were murdered by their husbands. Also, assume that the act of murder is enough to qualify for battering. Define the events

H ::= wife is murdered by husband
M ::= woman is murdered
B ::= wife is battered by husband

(a) Dershowitz’ statistical observation can be stated technically as

Pr(H | B) = 1/2000.

Prove it.

Solution.

Pr(H | B) = \frac{Pr(H ∩ B)}{Pr(B)} = \frac{Pr(H)}{Pr(B)} = \frac{1500/125M}{3M/125M} = \frac{1500}{3M} = 1/2000.

□

(b) Calculate Pr(H | M), i.e., the probability that a murdered woman was murdered by her husband.

Solution.

Pr(H | M) = \frac{Pr(H ∩ M)}{Pr(M)} = \frac{Pr(H)}{Pr(M)} = \frac{1500/125M}{6000/125M} = \frac{1500}{6000} = 1/4.

□

(c) Prove the identity

Pr(C | A) = Pr(C ∩ D | A) + Pr(C − D | A)

for arbitrary events A, C, D.

Solution.

Pr(C ∩ A) = Pr((C ∩ A) ∩ D) + Pr((C ∩ A) − D),
= Pr((C ∩ D) ∩ A) + Pr((C − D) ∩ A).

Now dividing both sides of this equation by Pr(A) yields the desired identity.

□

(d) Calculate Pr(H | B ∩ M), i.e., the probability that a battered, murdered woman was murdered by her husband. Assume that the the probability of a wife being murdered by someone other than her husband is not influenced by whether or not she was being battered.

Solution.

Note that

Pr(H | B ∩ M) = \frac{Pr(H ∩ B ∩ M)}{Pr(B ∩ M)} = \frac{Pr(H)}{Pr(M | B)Pr(B)}.

To evaluate Pr(M | B), we apply the identity from the previous problem part:

Pr(M | B) = Pr(M ∩ H | B) + Pr(M − H | B).

We know that being murdered by someone other than the husband is not influenced by whether the victim was battered by her husband or not, namely,

Pr(M − H | B) = Pr(M − H),

and H ∩ M = H, so

Pr(M | B) = Pr(H | B) + Pr(M − H) = \frac{1}{2000} + \frac{6K − 1.5K}{125M} .

Now we have

Pr(H | B ∩ M) = \frac{1500/125M}{(1/2000 + (6K − 1.5K)/125M)3M/125M}
= \frac{1500}{3M/2000 + 4500 · 3/125}
= \frac{1}{1 + 9/125} = \frac{125}{134} ≈ 0.93.

□

(e) How could you counter Dershowitz’ argument that evidence that a husband battered his wife should not be admitted as evidence?

Solution.

Being battered increases the probability that a murdered woman was murdered by her husband from 25% to 93%, so the fact of being battered greatly influences the probability of a husband’s guilt. Assuming it is proper for a jury to consider such probabilities – this is questionable by the way – then Dershowitz’ argument that battery is unlikely to be relevant does not hold up.

□

Problem 2 Consider playing the Lets Make a Deal, where there are three prizes: a “Gift Certificate” from Toscanini, a “Nerd Pocket Protector”, and a “Nerd Pride Button”. Your goal is to win the gift certificate.

(a) Suppose you (the contestant) happen to know that Carol always reveals the “Nerd Pocket Protector”, if you did not choose the box covering it.

Does this additional information change the odds of winning for you? Is there a better strategy? By how much (if any) does this information increase your chances of winning?

Solution.

The probability of winning the game remains the same, but now there is more than one optimal strategy. If Carol reveals the “Nerd Pride Button,” it means that you must have chosen the box covering the “Nerd Pocket Protector”. In this case, you win with probability 1 if you switch. If Carole shows you the “Nerd Pocket Protector” then there is 1/2 probability that you have picked the prize box, so you win with probability 1/2 whether you switch or not. Let NPB be the event that Carole shows the “Nerd Pride Button”, and NPP be the event that Carole shows the “Nerd Pocket Protector”. Then the total probability of winning is:

P r(win) = P r(win | NPB)P r(NPB) + P r(win | NPP)P r(NPP)
= 1 · \frac{1}{3} + \frac{1}{2} · \frac{2}{3}
= \frac{2}{3}
□

(b) You are playing according to the original assumptions, but before you make your initial choice, you happen to see Carol placing a “Nerd Pride Button” underneath Box 1. What should you do to try to win the prize (the ice cream)? What is the probability that you win?

Solution.

In this case, you should always pick Box 1. Monty will be forced to reveal the location of the other “Nerd Pride” pin. Upon switching, you will be guaranteed to win the ice cream (i.e. the probability of winning is 1). If you pick a box besides 1, Monty can always reveal Box 1 (giving you no additional information), and you will have a 1/2 chance of winning.

□

(c) You are trying one last time, with new rules. This time, you are told that Monty will reveal one of the doors you did not choose at random, whether or not it contains the prize. (In the case that the prize is revealed, you obviously lose). In this case, what is your optimal strategy and probability of winning?

Solution.

It does not matter now whether you switch or stay; you cannot increase your chances beyond 1/3. A tree diagram shows this nicely. You can also reason that 1/3 of the time, you have chosen the right door and should stay. 2/3 of the times you will choose the wrong door and be better off switching, but half of those times you will lose immediately. Thus, they do not contribute to the Pr(choice was right | did not lose yet) that we are really considering.

□

Problem 3 Consider the Lets Make a Deal game with the following assumptions on how host Monty Hall hides the prize and on how you initially choose a door. In each case, you follow the “switch strategy”, and in each case Monty reveals a loser after your initial choice. State whatever assumptions you need about how Monty reveals the loser. For each case, determine the probability that you will win the prize by listing all events in the sample space along with the probabilities that they occur.

(a) Monty Hall chooses a door to contain the prize with some non-uniform distribution – he hides the prize behind door number i with some probability p_{i}, for i = 1, 2, 3 and ∑_{i} p_{i} = 1.

You, the contestant, (not knowing the p_{i}’s) follow the strategy of selecting a door uniformly at random – you choose door i with probability 1/3.

(b) Monty Hall chooses a door behind which to hide the prize according to the uniform distribution but you the contestant select a door according to some non-uniform distribution – you select door i with some probability p_{i}, ∑_{i=1}^{3} p_{i} = 1.

Solution.

Since you always follow the “switch” strategy, the probability of winning the prize is the same as the probability that you did not choose the winning door as your first choice. In both parts, we can model this simplified problem with a sample space of nine points labeled as (w_{i}, c_{k}), with i, k ∈ {1, 2, 3}, and where (w_{i}, c_{k}) corresponds to the event that the prize is behind door i and your first choice is door k. The winning probability is then 1 − (w_{1}, c_{1}) − (w_{2}, c_{2}) − (w_{3}, c_{3})

1. In this part, we have P (w_{i}, c_{k}) = \frac{1}{3}p_{i}. So the probability of winning is 1 − \frac{1}{3} = \frac{2}{3}.

2. In this part, we have P (w_{i}, c_{k}) = \frac{1}{3}p_{i}. So the probability of winning is also \frac{2}{3}.

□