3
$\begingroup$

I need to show that $Disc_\mu(Disj) \geq \frac{1}{2n+1}$ for any distribution $\mu: \{0,1\}^n \times \{0,1\}^n \to [0,1]$. Disjointness is defined as

$Disj(X,Y)=\left\{ \begin{array}[ll]+1 & \text{if $X \cap Y = \emptyset$} \\ 0 & \text{otherwise}\end{array}\right.$

The discrepancy for a function is defined as $Disc_\mu(f) = \max_R \{Disc_\mu(R,f)\}$ over all rectangles $R$ and further

$$Disc_\mu(R,f) = |\Pr_\mu [(x,y) \in R \wedge f(x,y)=1] - \Pr_\mu[(x,y) \in R \wedge f(x,y) =0] |.$$

I don't understand where the $\frac{1}{2n+1}$ comes from and how to define a proper rectangle $R$.

The problem is given as an exercise without a solution in the book Communication Complexity by E. Kushilevitz and N. Nisan on page 40.

$\endgroup$
  • $\begingroup$ Can you add an image of that exercise to the question? I would like to double check if my understanding is correct. $\endgroup$ – Apass.Jack Apr 24 at 21:42
  • $\begingroup$ The exercise is only a single line without any further descriptions: Just Prove $Disc_\mu(Disj) \geq 1/(2n+1)$ for any distribution $\mu$. But $Disc_\mu$, $Disj$ and $\mu$ are all defined somewhere before. I went over your answer (took me some time) and it absolutely makes sense for me, everything you have described. Thank you very much! $\endgroup$ – cz5 Apr 25 at 16:36
1
$\begingroup$

Let me clarify the question first.

  • $\mu$ is a probability distribution over the sample space $S=\{0,1\}^n \times \{0,1\}^n$.
  • A combinatorial rectangle (or just rectangle) $R$ is a subset of $S$ of the form $A\times B$, where $A\subseteq \{0,1\}^n$ and $B\subseteq \{0,1\}^n$.
  • For all $x\in \{0,1\}^n$, we can think of $x$ as the characteristic vector of a subset of $\{1, \cdots, n\}$. That is, $x=(x_1, x_2, \cdots, x_n)$ where $x_i=1$ if and only if $i$ is in that subset. We may abuse $x$ to mean that subset.
  • We define $Disj(x, y) = 1$ for $x,y\in \{0,1\}^n$ if and only if the subset $x$ and the subset $y$ are disjoint. ($Disj(x, y) = 0$ if and only if they are not disjoint.)

For the sake of contradiction, suppose that $Disc_\mu(Disj) < \frac{1}{2n+1}$.

So, $Disc_\mu(S,Disj) = \left|\Pr_\mu [Disj(x,y)=1] - \Pr_\mu[Disj(x,y) =0] \right| < \frac{1}{2n+1}\tag{1},$ and $Disc_\mu(R_i,Disj) \lt \frac{1}{2n+1}\tag{2},$ where $R_i=X_i\times X_i$, $X_i$ is the set of all $x\in \{0,1\}^n$ that are subsets of $\{1, \cdots, n\}$ that contain $i$.

Since $Disj(x,y)=1$ means $x,y\in X_i$ for some $i$, $$\begin{aligned}\Pr_\mu [Disj(x,y)=1] &\le\sum_{i=1}^n\Pr_\mu [(x,y)\in X_i\times X_i]\\ &=\sum_{i=1}^n\left|\Pr_\mu[(x,y) \in R_i \wedge Disj(x,y)=1] - \Pr_\mu[(x,y) \in R_i \wedge Disj(x,y) =0] \right|\\ &=\sum_{i=1}^n Disc_\mu(R_i,Disj) \lt \frac{n}{2n+1} \end{aligned}$$

Combining the inequality (1), we know that $$\Pr_\mu [Disj(x,y)=0] \lt \frac {n+1}{2n+1}.$$

So $\Pr_\mu [Disj(x,y)=1] + \Pr_\mu[Disj(x,y) =0] <1$. However, the left hand side should be 1 since $Disj(x,y)$ is either 1 or 0. That is a contradiction. QED.

$\endgroup$
1
$\begingroup$

You asked two questions. I'll answer the second. A rectangle is a set $R$ of the form

$$R = \{(x_1,\dots,x_n) : \ell_1 \le x_1 \le u_1, \dots, \ell_n \le x_n \le u_n\}$$

for some $\ell_1,\dots,\ell_n,u_1,\dots,u_n$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.