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.


1 Answer 1


Ok, so you have strings $Z_n$ that are exactly half 0s and half 1s and you have $X_n$ that have exactly one more 1.

One way to generate these sorts of strings is to generate a $Z_n$ uniformly at random and then pick one 0 in it at random to change to a 1. The $\oplus$ symbol is presumably a bitwise OR, which satisfies $0\oplus 0=0$ and $1\oplus 0=1$, so it leaves the first input unchanged when the second input is 0. When the second input is 1 the output is always 1. The result is a string with one more 1 in it, and we call that $X_n$. So for any string $y$, $y\oplus 0^{i-1}10^{n-i}$ is just a complicated way to say change the value at $i$ to 1

Now we have a particular choice of $X_n$s and $Z_n$s that satisfy the definition in a nice way. A probabilist would call this a coupling of $X_n$ and $Z_n$: the distribution of each string on its own is specified by the assumptions, but the joint distribution is specially chosen so that the two strings only differ at one position.

Suppose we have an algorithm A that looks at only $q$ locations in the string. If we give it $Z_n$ and then $X_n$ generated according to this construction, it will return the same answer for both strings unless it queries a location where they are different (because it's an algorithm). There's only one location where they are different (by construction), and this location is randomly chosen, so the probability that Algorithm A queries that location is $q/n$, and otherwise it gives the same answers on the two strings.

In particular this means that an algorithm for recognising MAJ on random strings can't guarantee better than $q/n$ worst-case accuracy if it queries $q$ locations. If you want perfect accuracy you need to look at the whole string; if you need 2/3 accuracy you need to look at 2/3 of the string; if you want $>50$% accuracy you need to look at more than half the string. The coupled distributions of strings $X_n$ and $Z_n$ serve as evidence that you can't do better than this; it's still conceivable that you can't do even this well.

  • 1
    $\begingroup$ This answer beyond my expectations. Thank you, indeed. $\endgroup$
    – HDD
    Commented May 22 at 5:03

Your Answer

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

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