## 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 satisfy$F((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.