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?

My solution:

Here is the algorithm:

– Choose a number \alpha uniformly random from the table.

– Determine the unique number \beta from range [1,\ldots ,m-1] satisfies  F((z + \alpha )\phantom{a}mod\phantom{a} n) = ( \beta + F(\alpha ))\phantom{a} mod\phantom{b} m.

– Output \beta = F(z).

Explain:

When we compute \beta , we have to use the lookup table 2 times, namely when we evaluate F((z + \alpha )\phantom{a}mod\phantom{a} n) and F(\alpha ).

Suppose that luckily F((z + \alpha )\phantom{a}mod\phantom{a} n) and F(\alpha ) are the genuine values.

There is only one number \beta from range [1,\ldots , m-1] can satisfyF((z + \alpha )\phantom{a}mod\phantom{a} n) = ( \beta + F(\alpha ))\phantom{a} mod\phantom{b} m .

Since F(z) is also a number from range [1,\ldots , m-1] and satisfy F((z + \alpha )\phantom{a}mod\phantom{a} n) = ( F(z) + F(\alpha ))\phantom{a} mod\phantom{b} m, \beta must be F(z).

The only case in which the algorithm may fail to give the correct answer is when  F((z + \alpha )\phantom{a}mod\phantom{a} n) or F(\alpha ) or both are not the genuine values.

Let E_{1} be the event that the algorithm gives the wrong answer, E_{2} be the event that F((z + \alpha )\phantom{a}mod\phantom{a} n) or F(\alpha ) or both are not the genuine values.

We have Pr(E_{1}) \le Pr(E_{2}).

Pr(E_{2}) \le \frac{1}{5} + \frac{1}{5} = 0.4

Therfore Pr(E_{1}) \le 0.4.

This means the algorithm will output a value that equals to F(z) with probability at least 0.6.

Exercise 1.22: (a) Consider the set \{1,\ldots ,n\}. We generate a subset X 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 X, and otherwise it is not. Argue that the resulting set X is equally likely to be any one of the 2^{n} possible subsets.

(b) Suppose that two sets X and Y are chosen independently and uniformly at random from all the 2^{n} subsets of \{1,\ldots ,n\}. Determine Pr(X \subseteq Y) and Pr(X \cup Y = \{1,\ldots ,n\}).

Solution:

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

An arbitrary subset can be viewed as a sequence heads-tails of length n. For example, consider the set \{1, 2,3,4\} and its subset \{2,4\}. 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 2^{-1} to be heads or tails. Since length of the sequence is n, the sequence will be formed with probability 2^{-n}.

(b)

Calculate Pr(X \subseteq Y) :

Using the principle of deferred decision, suppose that we already chose a subset X with a elements(a = 0, \ldots ,n). For every subset X which has a elements, Pr(X \subseteq Y) = 2^{-a}.

Now consider the process of choosing X. There are \binom{n}{a} different subsets of \{1,\ldots ,n\} which has a elements (a= 0, \ldots, n), each subset is  equally likely to be chosen with probability 2^{-n}.

Therefore:

Pr(X \subseteq Y) = 2^{-n}\sum_{a=0}^{n}\binom{n}{a}2^{-a} = 2^{-n}(\sum_{a=0}^{n}\binom{n}{a}1^{n-a}(\frac{1}{2})^{a})

=2^{-n}(1+\frac{1}{2})^{n} = 2^{-n}\cdot \frac{3^{n}}{2^{n}} = (\frac{3}{4})^{n}.

Calculate Pr(X \cup Y = \{1,\ldots ,n\}):

Using the same reasoning, except that in this case for every subset X which has a elements Pr(X \cup Y = \{1,\ldots ,n\}) = 2^{n-a}, we have

Pr(X \cup Y = \{1,\ldots ,n\}) = 2^{-n}\sum_{a=0}^{n}\binom{n}{a}2^{n-a} = 2^{-n}(1+\frac{1}{2})^n

=(\frac{3}{4})^n.

The fact that Pr(X \subseteq Y) = Pr(X \cup Y = \{1,\ldots ,n\}) surprised me. It was completely not obvious to me from the start.

Advertisements

One response to this post.

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

    Reply

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: