Probability and Computing: Chapter 1 Exercises (Cont. 2)

Exercise 1.11:

Let E_{n} be the event that after the n-th relay we receive the correct bit.

Pr(E_{n}) = p(1-Pr(E_{n-1}))+ (1-p)Pr(E_{n-1})

= (1-2p)Pr(E_{n-1})+p

we have a recurrence relation:

Pr(E_{n}) = (1-2p)Pr(E_{n-1})+p

2Pr(E_{n}) = (1-2p)2Pr(E_{n-1})+2p

2Pr(E_{n}) -1 = (1-2p)(2Pr(E_{n-1})-1)\phantom{12} (1)

Let U_{n } = 2Pr(E_{n})-1. We have 2Pr(E_{n-1})-1 = U_{n-1}

Thus (1) becomes U_{n} = (1-2p)U_{n-1} ,

yields U_{n}=(1-2p)^{n}.

So Pr(E_{n}) = \frac{1 + (1-2p)^{n}}{2}.

Exercise 1.12: ( the Monty Hall problem)

Assume without loss of generality that the contestant chose door 1 and Monty opened door 2 to show a goat.

Let E_{i} be the event that  the car is behind door i and B be the event that Monty opened door 2.

First we calculate the probabilities before Monty opened door 2.

Pr(E_{1}) = Pr(E_{2}) = Pr(E_{3}) = \frac{1}{3}.

What is the value of Pr(B\mid E_{1}) ? If the car is in door 1 (the door the contestant chose), Monty will choose from two remaining door which door to open uniformly at random. So we have Pr(B\mid E_{1}) = \frac{1}{2}.

What is the value of Pr(B \mid \overline{E_{1}}) ? If the car is not in door 1, it can be in either door 2 or 3 with equally probabilities. So Pr(B\mid \overline{E_{1}}) = \frac{1}{2} .

What is the value of Pr(B\mid E_{3}) ? if the car is in door 3, Monty has no other choices than open door 2(because he cant open door 1). So Pr(B\mid E_{3}) = 1 .

Thus Pr(B) = Pr(B\mid E_{1})Pr(E_{1}) + Pr(B\mid \overline{E_{1}})Pr(\overline{E_{1}}) = \frac{1}{2}\cdot \frac{1}{3}+\frac{1}{2}\cdot \frac{2}{3} = \frac{1}{2}

Now we will see how things changed after Monty opened door 2.

Apply Bayes’ Law yields:

Pr(E_{1}\mid B) = \frac{Pr(B\mid E_{1})Pr(E_{1})}{Pr(B)} = \frac{\frac{1}{2}\cdot \frac{1}{3}}{\frac{1}{2}} = \frac{1}{3}

Pr(E_{3}\mid B) = \frac{Pr(B\mid E_{3})Pr(E_{3})}{Pr(B)} = \frac{1\cdot \frac{1}{3}}{\frac{1}{2}} = \frac{2}{3}

So the contestant will double the chance if he or she chooses to switch doors.

Exercise 1.13:

Let E be the event that the person has the disorder, and B be the event that the result comes back positive.

We have: Pr(E) = 0.02, Pr(B\mid E) = 0.999, Pr(B \mid \overline{E}) = 0.005

Apply Bayes’ Law yields:

Pr(E\mid B) = \frac{Pr(B\mid E)Pr(E)}{Pr(B)} = \frac{Pr(B\mid E)Pr(E)}{Pr(B\mid E)Pr(E) + Pr(B\mid \overline{E})Pr(\overline{E})} = \frac{0.02\cdot 0.999}{0.02\cdot 0.999+0.005\cdot 0.98}= 0.803

So if a person chosen uniformly from the population is tested and the result comes back positive, the probability that the person has the disorder is 0.803.

Advertisements

One response to this post.

  1. Posted by Anonymous on May 26, 2012 at 2:36 am

    Ex1.12: P(B|E3)=1

    Reply

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: