## 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$.