retagged by
805 views
5 votes
5 votes

Let $m, n$ be positive integers with $m$ a power of $2$. Let $s= 100 n^{2} \log m$. Suppose $S_{1}, S_{2},\dots ,S_{m}$ are subsets of ${1, 2, \dots, s}$ such that $ \mid S_{i} \mid= 10 n \log m$ and $ \mid S_{i} \cap S_{j} \mid \leq \log m$ for all $1 \leq i \lt j \leq m$. Such a collection of sets $S_{1},\dots ,S_{m}$ is an example of a so-called Nisan-Wigderson design. We now consider the set membership problem, where we have to store an arbitrary subset $T \subseteq \left\{1, 2,....,m\right\}, \mid T \mid = n$ as an array $A$ of $s$ bits so that given any integer $x, 1 \leq x \leq m$, we can discover whether $x \in T$  by reading only one bit of $A$. Consider the following strategy to solve this problem. Array $A$ is initialized to all zeroes. Given the set $T$ to be stored, we put a one in all the locations of $A$ indexed by the union $\cup_{t \in T}S_{t}$. Now, given the integer $x$, we read a random location in $A$ from $S_{x}$ and declare that $x \in T$ if the bit in that location is one. This strategy gives the correct answer with probability

  1. $1$ if $x \in T$ and at most $0.1$ if $x ∉ T$.
  2. At least $0.9$ if $x \in T$ and at most $0.1$ if $x ∉ T$.
  3. At least $0.9$ if $x \in T$ and at least $0.9$ if $x ∉ T$.
  4. $1$ if $x \in T$ and at least $0.9$ if $x ∉ T$.
  5. At least $0.9$ if $x \in T$ and $1$ if $x ∉ T$. 
retagged by

1 Answer

5 votes
5 votes
Option D is correct

Let $m=4(2^{2}) , n=2$ then $ s=100 \times 4 \times 2=800 \: numbers $

Let $S_1,S_2,S_3,S_4$ be subsets to $S,$ each having $(10 \times 2 \times 2=40) \: elements$.

Special condition is $ \mid S_i \cap S_j \mid \leq 2 \: (i.e \: \log m)$

Let

$ S_1= \{ 1,2, \ldots ,37,38,39,40 \} \\ S_2 = \{ 121,122, \ldots ,160 \} \\ S_3 = \{ 37,38,41,42, \dots ,78 \} \quad here \: \mid S_1 \cap S_2 \mid = 2 \\ S_4 =  \{39,40,81,82, \ldots ,118 \}  \quad \text{here also same}$.

and $A$ is an array of $800$ locations, initially $0$.

and $T  \subseteq (S_1,S_2,S_3,S_4) \: and \: \mid T \mid = 2 \: \text{( i.e n)}$

$\text{Case 1: Let T } = (S_3, S_4)$

then $A$ is like this $$\begin{array}{c|cccccccccccccccc}  & 1 & 2 & 3 & \ldots & 36 & 37 & 38 & 39 & 40 & 41 & 42 & \ldots & 78 & \ldots & 118 &  \dots & 800 \\  \hline & 0 & 0 & 0 & \ldots & 0 & 1 & 1 & 1 & 1 & 1 & 1 & \dots & 1 & \ldots & 1 & \dots & 0  \end{array}$$ $Case \: \mathrm{a} \: $: $\begin{align}& \\   & \text{If input is $3$ (i.e. $S_3$) belongs to $T$ } \\ & \text{it went to one of the $40$ locations $\{ 37 \ldots 78 \}$} \\ & \text{cmp bit.} \\ & \text{$P$ ($S_3$ present) = $\dfrac{40}{40 }= 1$ }  \end{align} $

$Case \: \mathrm{b} \: : \begin{align}& \\ & \text{If input is $1$ (i.e. $S_1$) belongs to $T$ } \\ & \text{it went to one of the $40$ locations $\{ 1 \ldots 40 \}$} \\ & \text{cmp bit} \\ & \text{$P$ ($S_1$ present) = $\dfrac{4}{40 }= \dfrac{1}{10} \: \mathsf{(wrong \: says)} $} \\ & \text{$P$ ($S_1$ not present) = $\dfrac{36}{40} = \dfrac{9}{10} = 0.9 \: \mathtt{(correct \: says)}$}  \end{align}$
edited by
Answer:

Related questions

9 votes
9 votes
5 answers
3
18 votes
18 votes
5 answers
4
makhdoom ghaya asked Nov 4, 2015
1,578 views
An unbiased die is thrown $n$ times. The probability that the product of numbers would be even is$\dfrac{1}{(2n)}$$\dfrac{1}{[(6n)!]}$$1 - 6^{-n}$$6^{-n}$None of the abov...