Assume that Alice and Bob are respectively given two strings $x \in \{0,1\}^n$ and $y \in \{0,1\}^n$ such that the hamming distance between $x$ and $y$ is either $> n/2+\sqrt{n}$ or $< n/2-\sqrt{n}$.

Alice picks a set $A \subseteq \{1,...,n\}$ of size $k$ uniformly at random, and sends to Bob the set $\{(i,x_i) \mid i \in A\}$. Bob compares $x_i$ with $y_i$ for every $i \in A$ and accepts iff the majority of these indices agree. What is (asymptotically) the minimal $k$ for which this protocol succeeds (i.e. Bob accepts iff the distance is $< n/2-\sqrt{n}$) with probability at least $2/3$?

I guess that $k$ should be $\Omega(n)$, and that in order to show this we should bound the tail of the distribution (e.g. by using the Central limit theorem or something similar), but I don't see how this can be done.

  • $\begingroup$ Are you familiar with the Chernoff bound? This should give you one direction. $\endgroup$ – Yuval Filmus Apr 21 at 17:34
  • $\begingroup$ In the other direction you could use the reverse Chernoff bound, but in your case there might be a simpler way. $\endgroup$ – Yuval Filmus Apr 21 at 17:35
  • $\begingroup$ @YuvalFilmus What do you mean by two directions? also $A$ is picked uniformly at random. How do we change this to binomial distribution? $\endgroup$ – user91015 Apr 21 at 17:54
  • $\begingroup$ You need both a lower bound and an upper bound on $k$. These are the two directions. $\endgroup$ – Yuval Filmus Apr 21 at 18:00
  • $\begingroup$ As to relating it to the binomial distribution, you're right that it's more like the hypergeometric distribution (though Chernoff's bound works in this case as well). I suggest first considering what happens when instead of a set of size $k$ you draw $k$ integers from $\{1,\ldots,n\}$ with repeats. $\endgroup$ – Yuval Filmus Apr 21 at 18:01

Suppose that the Hamming distance between $x$ and $y$ is $n/2 - \sqrt{n}$. Suppose that you sample $m$ indices with replacement, and let $S$ be the number of indices on which $x$ and $y$ disagree. Then $S$ has expectation $mp$ and variance $mp(1-p)$, where $p = 1/2 - 1/\sqrt{n}$. According to the central limit theorem, for every fixed $t$ we have $$ \Pr\left[ \frac{S-mp}{\sqrt{mp(1-p)}} \leq t \right] \longrightarrow \Pr[N(0,1) \leq t]. $$ We are interested in the event $S \leq m/2$, which is the same as $S - mp \leq m(1/2-p) = m/\sqrt{n}$, or equivalently $$ \frac{S-m/p}{\sqrt{mp(1-p)}} \leq \frac{1/2-p}{\sqrt{p(1-p)}} \sqrt{m} \approx \sqrt{\frac{m}{4n}}. $$ In particular, if $m = cn$ then (following a short argument) the probability of error tends to $$ \Pr[N(0,1) > \sqrt{c/4}]. $$ For small enough $c$, this would be more than $1/3$, giving an $\Omega(n)$ lower bound for this version of your algorithm.

In your case, you choose indices without replacement. A similar argument works, using the central limit theorem for hypergeometric random variables, see for example Lahiri and Chatterjee, A Berry–Esseen theorem for hypergeometric random probabilities under minimal conditions, Theorem 2.1.

| cite | improve this answer | |
  • $\begingroup$ If you are assuming that the distance between $x$ and $y$ is $n/2-\sqrt{n}$, then why $p = 1/2- 1/\sqrt{n}$? $\endgroup$ – user12 Apr 22 at 14:12
  • $\begingroup$ Thanks, changed agree to disagree. $\endgroup$ – Yuval Filmus Apr 22 at 14:13
  • $\begingroup$ You'll have to choose the correct version of "agreement" and "disagreement" for the argument to make sense. The idea is to show that the answer is wrong with probability more than 1/3. $\endgroup$ – Yuval Filmus Apr 22 at 14:38

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.