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.

Continue reading

Advertisements

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?

Continue reading

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.

Continue reading

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.

Continue reading

Probability and Computing: Chapter 1 Exercises

Exercise 1.5:

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.

Continue reading