Let $x$ be any binary string $\in (0,1)^*.$

The majority language is given by: $$\text{MAJ}:=\{x\in (0,1)^*:\sum_{i=1}^ {|x|}x_i>\frac{|x|}{2}\},\text{where $x_i$ is the $i$-th position value(either $0$ or $1$) of $x$}.$$

The hamming weight of any given string $x\in (0,1)^*.$ is defined by, $$wt(x)=\sum_{i=1}^{|x|}x_i=|\{i\in[|x|]:x_i=1\}|.$$

Given $n\in \mathbb{N},$ define two distributions:

$$X_n=\text{uniform distribution over $n$-long strings satisfying} wt(x)=\left \lfloor \dfrac{n}{2} \right \rfloor+1$$

$$Z_n=\text{uniform distribution over $n$-long strings satisfying} wt(x)=\left \lfloor \dfrac{n}{2} \right \rfloor$$

And $$P[X_n\in \text{MAJ}]=1 \text{ and } P[Z_n\in \text{MAJ}]=0.$$

Now I want to prove the following claim: $$A:= \text{algorithm querying $n$-long sequences string in $q$ locations,then}|P[A(X_n)=1)]-P[A(Z_n)=1)]|\leq \frac{q}{n}.$$

My advisor give the following proof:

Proof: Generate $X_n$ and $Z_n$ as follows,Sample $i\in [n]$ uniformly at random($i$index of the string). Sample $y\in \{z\in (0,1)^n: wt(z) =\left \lfloor \dfrac{n}{2} \right \rfloor\ ,z_i=0\}.$ For $Z_n,$ output $y.$ For $X_n,$ output $$y \oplus 0^{i-1}10^{n-i}(\text{copy $y$ pointwise and place $1$ at $i$th entry.})$$ As long as the algorithm $A$ doesn't query the $i$th location, it behaves exactly the same on $X_n$ and $Z_n$ as it effectively queries the same values. The distribution over $i$ is uniform and so the algorithm queries this location with probability $\leq\frac{q}{n}.$

My question I don't understand the above proof, how the output for $X_n,$ becomes $$y \oplus 0^{i-1}10^{n-i}?$$ And how the probability $\leq\frac{q}{n}?$ Anybody help me to understand above the algorithm.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.