**Exercise 1.9**: Suppose that a fair coin is flipped times. For , find an upper bound on the probability that there is a sequence of consecutive heads.

## Archive for September, 2009

27 Sep

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

26 Sep

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

26 Sep

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

**Exercise 1.18**: We have a function . We know that, for . The only way we have for evaluating is to use a look up table that stores values of . Unfortunately, an Evil Adversary has changed the value of of the table entries when we were not looking.

Describe a simple randomized algorithm that, given an input , outputs a value that equals with probability at least . Your algorithm should work for every value of , 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?

26 Sep

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

**Exercise 1.14**:

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

19 Sep

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

**Exercise 1.11**:

Let be the event that after the -th relay we receive the correct bit.

we have a recurrence relation:

Let . We have

Thus becomes

yields

So

**Exercise 1.12**: ( the Monty Hall problem)

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

Let be the event that the car is behind door and be the event that Monty opened door .

First we calculate the probabilities before Monty opened door .

.

What is the value of ? If the car is in door (the door the contestant chose), Monty will choose from two remaining door which door to open uniformly at random. So we have .

What is the value of ? If the car is not in door , it can be in either door or with equally probabilities. So .

What is the value of ? if the car is in door , Monty has no other choices than open door (because he cant open door ). So .

Thus

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

Apply Bayes’ Law yields:

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:

Apply Bayes’ Law yields:

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 .

18 Sep

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

**Exercise 1.8**:

Let be the event that the number is divisible by 4,6, and 9; respectively.

17 Sep

### Probability and Computing: Chapter 1 Exercises

**Exercise 1.5**:

Let be the event that Bob’s number is and Alice ‘s number is ; be the event that Alice wins.

## Recent Comments