**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?

**My solution**:

Here is the algorithm:

– Choose a number uniformly random from the table.

– Determine the unique number from range satisfies .

– Output .

**Explain**:

When we compute , we have to use the lookup table times, namely when we evaluate and .

Suppose that luckily and are the genuine values.

There is only one number from range can satisfy .

Since is also a number from range and satisfy , must be .

The only case in which the algorithm may fail to give the correct answer is when or or both are not the genuine values.

Let be the event that the algorithm gives the wrong answer, be the event that or or both are not the genuine values.

We have .

Therfore .

This means the algorithm will output a value that equals to with probability at least

**Exercise 1.22**: (a) Consider the set . We generate a subset of this set as follows: a fair coin is flipped independently for each element of the set; if the coin lands heads then the elements is added to , and otherwise it is not. Argue that the resulting set is equally likely to be any one of the possible subsets.

(b) Suppose that two sets and are chosen independently and uniformly at random from all the subsets of . Determine and .

**Solution**:

(a) In order to prove that is equally likely to be any one of the possible subsets we will prove that through the defined process an arbitrary subset can be formed with probability .

An arbitrary subset can be viewed as a sequence heads-tails of length . For example, consider the set and its subset . This subset can be viewed as the sequence tails-heads-tails-heads.

Because the fair coin is flipped independently, each position has a probability of to be heads or tails. Since length of the sequence is , the sequence will be formed with probability .

(b)

Calculate :

Using the principle of deferred decision, suppose that we already chose a subset with elements(). For every subset which has elements, .

Now consider the process of choosing . There are different subsets of which has elements (), each subset is equally likely to be chosen with probability .

Therefore:

.

Calculate :

Using the same reasoning, except that in this case for every subset which has elements , we have

.

The fact that surprised me. It was completely not obvious to me from the start.

Posted by Anonymous on May 26, 2012 at 4:07 pm

Ex1.22: I think the reason why 2 probability are equal is the prob that X has all of n-a remained elements is equal to the prob that it has none of them