## Archive for September, 2009

### Probability and Computing: Chapter 1 Exercises (Cont. 5)

Exercise 1.9: Suppose that a fair coin is flipped $n$ times. For $k > 0$, find an upper bound on the probability that there is a sequence of $log_{2}n+k$ consecutive heads.

### Tài liệu bổ sung

Mới tìm được trang web của course về Probability and Computing do chính Michael Mitzenmacher dạy. Có lẽ từ nay sẽ tập trung làm bài tập cho trong các assignment của lớp này để tiết kiệm thời gian.

### Probability and Computing: Chapter 1 Exercises (Cont. 4)

Exercise 1.18:  We have a function $F: \{0,\ldots ,n-1\} \to \{0,\ldots ,m-1\}$.  We know that, for $0\le x,y \le n-1, F((x + y)\phantom{a}mod\phantom{a} n) = (F(x) + F(y))\phantom{a} mod\phantom{b} m$.  The only way we have for evaluating $F$ is to use a look up table that stores values of $F$. Unfortunately, an Evil Adversary has changed the value of $\frac{1}{5}$ of the table entries when we were not looking.

Describe a simple randomized algorithm that, given an input $z$, outputs a value that equals $F(z)$ with probability at least $\frac{1}{2}$. Your algorithm should work for every value of $z$, regardless what value the Adversary changed. Your algorithm should use as few lookups, and as little computation as possible.

Suppose I allow you to repeat your initial algorithm three times. What should you do in this case, and what is the probability that your enhanced algorithm returns the correct answer?

### Probability and Computing: Chapter 1 Exercises (Cont. 3)

Exercise 1.14:

Let $A$ be the event that we are equally talented,  $B$ be the event that I am slightly better, $C$ be the event that he is slightly better, $D$ be the event that the game ends up in one win for me and three wins for him.

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

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

Exercise 1.8:

Let $E_{1},E_{2},E_{3}$ be the event that the number is divisible by 4,6, and 9; respectively.

Let $E_{n,m}$ be the event that Bob’s number is $n$ and Alice ‘s number is $m$; $E$ be the event that Alice wins.